It is currently Fri Sep 22, 2017 10:50 pm

All times are UTC - 8 hours [ DST ]




Post new topic Reply to topic  [ 12 posts ] 
Author Message
Offline
 Post subject: L19 Programming Problem Championship: Round 7 (Palindromes)
Post #1 Posted: Wed Jun 14, 2017 10:51 am 
Gosei
User avatar

Posts: 1833
Location: Bellevue, WA
Liked others: 89
Was liked: 819
Rank: AGA 5d
KGS: Capsule 4d
Tygem: 치킨까스 5d
Leaderboard

  1. bernds - 28
  2. ugoertz - 21
  3. gamesorry - 19
  4. Solomon - 18
  5. dfan - 9
  6. peti29 - 8
  7. quantumf - 7
  8. jeromie - 5
  9. Kirby - 3

Contest Link: https://open.kattis.com/contests/q29pfw

Start Time: 2017-06-16 17:00:00 UTC (Fri June 16 2017 10am PST, 19:00 CEST)
Duration: 60 hours
Problems: 6
Theme: Palindromes

Past Rounds:


This post by Solomon was liked by 2 people: bernds, gamesorry
Top
 Profile  
 
Offline
 Post subject: Re: L19 Programming Problem Championship: Round 7 (Palindrom
Post #2 Posted: Wed Jun 14, 2017 11:56 am 
Dies in gote

Posts: 46
Liked others: 5
Was liked: 7
Rank: 2d
Solomon wrote:
Theme: Palindromes
There's a whole theme for that? Now I'm curious.

Top
 Profile  
 
Offline
 Post subject: Re: L19 Programming Problem Championship: Round 7 (Palindrom
Post #3 Posted: Wed Jun 14, 2017 1:33 pm 
Judan

Posts: 7527
Liked others: 1371
Was liked: 1155
KGS: Kirby
Tygem: 커비라고해
bernds wrote:
Solomon wrote:
Theme: Palindromes
There's a whole theme for that? Now I'm curious.


Yes, but there are actually only three distinct problems: Problem A is the same as Problem F, Problem B is the same as Problem E, and Problem C is the same as Problem D.

_________________
Discipline is remembering what you want. -David Campbell

Top
 Profile  
 
Offline
 Post subject: Re: L19 Programming Problem Championship: Round 7 (Palindrom
Post #4 Posted: Fri Jun 16, 2017 8:33 am 
Gosei
User avatar

Posts: 1833
Location: Bellevue, WA
Liked others: 89
Was liked: 819
Rank: AGA 5d
KGS: Capsule 4d
Tygem: 치킨까스 5d
Kirby wrote:
bernds wrote:
Solomon wrote:
Theme: Palindromes
There's a whole theme for that? Now I'm curious.


Yes, but there are actually only three distinct problems: Problem A is the same as Problem F, Problem B is the same as Problem E, and Problem C is the same as Problem D.
Nice, but don't worry I made sure they're all distinct :).

Top
 Profile  
 
Offline
 Post subject: Re: L19 Programming Problem Championship: Round 7 (Palindrom
Post #5 Posted: Sat Jun 17, 2017 11:32 am 
Dies in gote

Posts: 46
Liked others: 5
Was liked: 7
Rank: 2d
Stuck on the crosswords. Once again the kind of situation where your program passes all the tests you can devise, but gets WA as soon as it gets to the first hidden testcase :sad:

Top
 Profile  
 
Offline
 Post subject: Re: L19 Programming Problem Championship: Round 7 (Palindrom
Post #6 Posted: Sun Jun 18, 2017 10:34 pm 
Lives with ko

Posts: 135
Liked others: 170
Was liked: 41
Rank: Chinese 3d
KGS: 3d
DGS: 3d
OGS: 3d
Thanks @Solomon again for the contest - didn't expect Palindrome problems can have so many variations :)

Got WA on problem E and only found the mistake 10 minutes after the contest ends: I failed to check for the negative result during calculation (thought the calculation was always positive but forgot the modulus can make numbers small),
//DP
Code:
for (int l = 2 ; l < n ; l++) {
   for (int i = 0 ; i < n - l ; i++) {
      d[i][i+l] = d[i][i+l-1] + d[i+1][i+l];
      
      if (s[i] == s[i+l]) {
         d[i][i+l]++;
      } else {
         d[i][i+l] -= d[i+1][i+l-1];
      }
      while (d[i][i+l] < 0) d[i][i+l] += 1000000007; //Need to check for negative result!!!
      d[i][i+l] %= 1000000007;
      //cout<<i<<","<<i+l<<" : "<<d[i][i+l]<<endl;
   }
}

Test case by my random typing:
fdsafsajdfhasufdhisadfsfdiaufhisaudhfisahfahfhsuiadhfiassadhfiisa

Debugging information:
...
1,63 : 687665752
2,64 : 890350140
0,63 : 15869387
1,64 : 39513617
0,64 : -632282748
-632282748


For Problem F, I used BFS on non-repeated state (x1, y1, x2, y2) where (x1, y1) and (x2, y2) are the two ends of the palindrome, but my solution gets TLE on the second test case. When testing on local machine it seems that it's ok for n=50 but too slow for n=100. Hope bernds/ugoertz can shed some light on it :salute:

Top
 Profile  
 
Offline
 Post subject: Re: L19 Programming Problem Championship: Round 7 (Palindrom
Post #7 Posted: Mon Jun 19, 2017 6:35 am 
Dies in gote

Posts: 46
Liked others: 5
Was liked: 7
Rank: 2d
Once again, thanks to Solomon for setting things up.

Problem A: For any string of a given length, we can calculate the number of letters we need to change to make it palindromic. We iterate over the number of characters to add (starting with zero); we know exactly which ones to add since we just take them from the front of the string in reverse order.

Problem B: We can find palindromes by starting at any given character (or pair of identical characters) and searching outwards. Once found, enter them into a hash table (I reused the one I made for the "make" problem in the graphs round).

Problem C: If we just look at the lower bits of any base-2 palindrome, we'll see that bit 0 is always 1 (since the upper bit must be 1), and the bits 1-(n/2) assume every possible pattern. So that's a way to count the number of palindromes for a given length; we can use that to determine the length in bits of the output. While doing so, we subtract the numbers for lower lengths, leaving us with the bit pattern to place into the two halves.

Problem D: Didn't solve it yet. By giving us subsets that must be palindromic, it implies certain groups of letters that must be identical. I reused a portion of the "chess" code here to compute these groups. We can look at all characters in such a group and see which set of final characters can be achieved - if only one, we found the solution for this group, if zero we've shown the problem is unsolvable. If solutions we've found made us change adjacent letters, the problem is also unsolvable. Finally there's a brute-force step which seems to take too long. I probably need to add a few more clever steps first.

Problem E: I used DP as well, although apparently a different strategy than gamesorry. I never had to deal with negative numbers and I haven't looked at yours long enough to figure out how you're doing it. I kept four numbers for every position/length pair: the number of palindromes which use both endpoint characters, the number of right- and left-justified ones, and the number which doesn't include either. I found this makes it quite easy to build up the longer-length numbers from the shorter ones. Then I messed up a few times forgetting the modulo requirement, and not finding the one spot where I was looking at "left" numbers where I should have been looking at "right".

Problem F: Similar to problem B: we start at a given location and search outwards. The trick here is that the number of palindromes can be way too large, but we're not actually interested in all of them. All we need to keep track of is for any two pairs (x1, y1) and (x2, y2) whether there's at least one palindrome between them. So, start a recursive search at every position, and if we come to a letter pair where we've already been, stop the search. As a slight optimization, start looking for longer-length palindromes first (the longer the palindrome, the more starting positions are included). If the length you're looking for drops below the best one you found, you can also terminate the program. My silly issue for this problem was that somehow I'd convinced myself the longest palindrome could be 100 letters so I could store the directions to take in a 64 bit number. Of course, only the longest half can be 100 characters. Fortunately there's __uint128_t these days.


This post by bernds was liked by: gamesorry
Top
 Profile  
 
Offline
 Post subject: Re: L19 Programming Problem Championship: Round 7 (Palindrom
Post #8 Posted: Mon Jun 19, 2017 8:29 am 
Gosei
User avatar

Posts: 1833
Location: Bellevue, WA
Liked others: 89
Was liked: 819
Rank: AGA 5d
KGS: Capsule 4d
Tygem: 치킨까스 5d
Was sick most of the weekend except on Father's Day, so I felt like I only had a few hours yesterday to work on the problems. Regardless, I was pretty disappointed with my attempt at A, which by difficulty rating was considered the easiest and yet it was the hardest out of A, B, and C for me. The approach I took for that problem was bottom up DP variation of Levenshtein's distance, but I'm pretty sure my states weren't correct and I'll be probably distracting myself with upsolving A and the rest of the problems today and tomorrow. Based on bernds's description it sounds like I went overboard. Thank you everyone for participating; next week I'll be busy, so see you guys in 2 weeks for the next round!

Top
 Profile  
 
Offline
 Post subject: Re: L19 Programming Problem Championship: Round 7 (Palindrom
Post #9 Posted: Mon Jun 19, 2017 8:43 am 
Dies in gote

Posts: 46
Liked others: 5
Was liked: 7
Rank: 2d
Solomon wrote:
Regardless, I was pretty disappointed with my attempt at A, which by difficulty rating was considered the easiest and yet it was the hardest out of A, B, and C for me. The approach I took for that problem was bottom up DP variation of Levenshtein's distance, but I'm pretty sure my states weren't correct and I'll be probably distracting myself with upsolving A and the rest of the problems today and tomorrow. Based on bernds's description it sounds like I went overboard.
That sort of thing kind of happened to me last week with the factorial digits. I should have known to use the sum of logarithms but for some reason I blanked out.

Top
 Profile  
 
Offline
 Post subject: Re: L19 Programming Problem Championship: Round 7 (Palindrom
Post #10 Posted: Mon Jun 19, 2017 8:45 am 
Dies in gote
User avatar

Posts: 60
Liked others: 0
Was liked: 40
Thanks, Solomon, for setting up the contest!

As to my solutions, I do not have much to add to what Bernd said - for A, B, C, and F, I did roughly the same as he described. I did not spend much time on D, it also looked like a graph theory problem to me, with the edges encoding that two entries are forced to be equal, or that one has to be "increased more" than the other. But in the end some backtracking is required, as far as i could see, and all in all it appeared quite complicated to implement all of it.

For me, E was the hardest among the problems I solved. I still do not really get the hang of Dynamic Programming, I guess. In many cases my naive approximation of "backtracking + caching all computations" is enough, but in this case my first approach was way too slow despite caching. After some further thought, I noticed that a palindrome with center at position i is the same as a common subsequence of the strings s[:i] and reversed(s[i+1:]) (where s denotes the string we are given). So the task can be translated into counting the number of common subsequences of prefixes of s and reversed(s), and this can be done in O(len(s)**2) time using some standard (it seems ...) DP pattern. It is a little more complicated to deal with the even length palindromes, but not too much. This gives a pretty fast solution, but the Python implementation still was not fast enough. This time I decided to rewrite things in C++. (Which was not actually too much work, but sure enough, with C++ I also got bitten by the sign problem which gamesorry mentioned ...) Anyway, this problem was definitively instructive for me.

Best, Ulrich

_________________
u-go.net


This post by ugoertz was liked by: gamesorry
Top
 Profile  
 
Offline
 Post subject: Re: L19 Programming Problem Championship: Round 7 (Palindrom
Post #11 Posted: Thu Jul 20, 2017 10:54 am 
Dies in gote

Posts: 46
Liked others: 5
Was liked: 7
Rank: 2d
Solomon wrote:
Thank you everyone for participating; next week I'll be busy, so see you guys in 2 weeks for the next round!
This seems to have stalled, which is a shame as I've found it a lot of fun. Have you been unavailable, or have you lost interest - and would you mind if someone else organized a few more rounds? Are other folks still interested in this?

Top
 Profile  
 
Offline
 Post subject: Re: L19 Programming Problem Championship: Round 7 (Palindrom
Post #12 Posted: Tue Aug 01, 2017 1:36 pm 
Gosei
User avatar

Posts: 1833
Location: Bellevue, WA
Liked others: 89
Was liked: 819
Rank: AGA 5d
KGS: Capsule 4d
Tygem: 치킨까스 5d
Sorry bernds, I got distracted with other things unrelated to Go and haven't visited the forums much for the past few weeks. I also miss these contests, so I will be starting them up again this Thursday :).


This post by Solomon was liked by 2 people: bernds, gamesorry
Top
 Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 12 posts ] 

All times are UTC - 8 hours [ DST ]


Who is online

Users browsing this forum: No registered users and 2 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group