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:

• Round 6 (June 9 2017)
• Round 5 (June 2 2017)
• Round 4 (May 19 2017)
• Round 3 (May 12 2017)
• Round 2 (May 6 2017)
• Round 1 (April 28 2017)

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.

_________________
be immersed

Nice, but don't worry I made sure they're all distinct .

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

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),


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

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.

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!

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.

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 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?

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 .