L19 Programming Problem Championship: Round 2 (Strings)

[quantumf]

Problems 3-5 are a major jump in difficulty.

[Kirby]

I spent some time on this last night and got problem 2. I had to keep a table to store information about the indexes of words to make it work. My first idea went out of memory from copying the whole strings. Problem 1 I actually did on Friday before meeting with my parents.

If I have time I might look at the others tonight, but 3 and 4 didn't look simple. Problem 5 seems possible to do if I can formalize the string pattern and construct a string given the input. With a formalized pattern that shouldn't be too hard.

I see a lot of people participating. Are they all from L19?

[peti29]

Problem C has been such a zen-like experience: I've made so much progress, still I'm running out of time at the exact same test case...

[bernds]

Problem 4 has interesting stats: few people have solved it, but pretty much all of them got it right first try. So maybe it isn't that hard, but I've not really had a breakthrough and I need to go to bed. Followed some false leads thinking that the concepts I used in problem 3 would be relevant again - that wasted a fair chunk of time.

[Solomon]

Spent the whole day at the Seattle Go Center for the Spring tournament, so unfortunately couldn't make much progress on D or E. I'll see if I can try to at least get E, since it doesn't seem to a problem with much coding and is more of a combinatorics problem (there's a particular sequence on OEIS I've been eyeing...).

[Solomon]

I see a lot of people participating. Are they all from L19?

At least 10 in this round are from L19.

[gamesorry]

Similar to what peti said about Problem C: I've made so much incremental progress in formulating it as a DP problem, but still I'm running out of time at test case 34 ...

[ugoertz]

Thanks for setting up the contest.

I had (I think) working Python solutions for C and E, but hit the time limit exceeded problem (especially frustrating for problem E since on my laptop all test cases up to n = 10^18 and varying k - which I think should be the slowest ones within the problem specification - ran in below 1 second ...). Rewriting in a compiled language would have helped, I suppose, but did not seem to be a good way to spend my time. I did not use any math/combinatorics, though, maybe I should have thought more about that.

For the curious, I put my solutions/attempts on github: https://github.com/ugoertz/l19contest. Comments welcome!

Best regards, Ulrich

[Solomon]

About to go to sleep, will post what I managed to solve in the morning and update the leaderboard. I'm thinking maybe for next round, to put up 2 easy, 2 medium, 2 hard instead of 1 easy, 1 medium, and 3 hard. What do you guys think? I'm also open to suggestions for next week's theme.

[tj86430]

BTW, is it possible to submit solutions after the round has closed and to get feedback whether the solution would have been accepted? There are some problems I'd like to try, but I don't usually (read: ever) have time to do those within set timeframe. I might try during e.g. summer vacation, though.

[peti29]

So thank you Solomon for arranging this! It was fun even though I had little time to take part. (I'd ask for an earlier start next time in order for us living in GMT+ countries to be able to start Friday night)

Spoiler from here on...

Problem B: after my initial naive approach I decided to cut the string to n pieces (n going 2,3,4,5...) and see if the pieces are identical. If yes, take the piece, drop everything else and start again. At the end multiply the result according to the pieces dropped (i.e.: if I find that cutting to 3 works and then cutting that 1/3 to 2 pieces again works, the multiplier is 6).
What was the final realization for me is that I only needed to check for prime number n-s (as there is no way a string can have 4 repetition when there is no 2). This I found a bit absurd because there is knowingly no quick way to check for primes. Still my clumsy naive implementation of prime number checking yielded the key to solve this problem.

Problem C: at first I implemented a huge recursive multi level loop to evaluate every permutation (so that order matters) of selected k items (where k is 1 to count of all items). The "))((" test case item really freaked me out and I'm so glad that it was among the examples.
Then later I came up with a formula that allowed me to verify a set of selected k items without trying all the permutations but I still needed to try out all possible sets of k items (where k is 1 to count of all items).
I then added a few optimizations (e.g. going with k from count of all items down to 1 and exiting if for whatever k I found a working set). I also noticed that I can freely drop items that (evaluating from left to right) never have fewer '('-s than ')'-s and have equal number of '('-s and ')'-s as I can always append them without ruining the balance. So I dropped them and added their length to the solution.
But then I was still running out of time on test case 3. I added a few more early checks (return 0 if every item has more '('-s than ')'-s or the other way around), improved my naive "get k of n in every permutation" loop, but then I ran out of ideas. The .net fiddle page started freezing on me, and it was 2:30AM so I called it a day, but I'm very curious what I could have missed.

[bernds]

For the curious, I put my solutions/attempts on github: https://github.com/ugoertz/l19contest. Comments welcome!

I was thinking of doing something like this after the first round, but decided against it - having the solutions googleable kind of breaks the concept of contest web sites. On the other hand, it is nice to be able to discuss each other's approaches and solutions. Hmm. (I clearly need to learn Python better, I can't even tell what you're doing in some of these.)

[bernds]

About to go to sleep, will post what I managed to solve in the morning

I'll let you go first this time and post at my thoughts later if I have anything to add. Still thinking about putting up source.

I'm thinking maybe for next round, to put up 2 easy, 2 medium, 2 hard instead of 1 easy, 1 medium, and 3 hard. What do you guys think? I'm also open to suggestions for next week's theme.

Sounds like a good plan, but to me it felt like this week we had trivial/easy/medium/hard/hard-ish. I'm not sure we need more than one instance of things like bishops or autori each week.

What themes are available?

[bernds]

What was the final realization for me is that I only needed to check for prime number n-s (as there is no way a string can have 4 repetition when there is no 2). This I found a bit absurd because there is knowingly no quick way to check for primes.

There's a well-known algorithm to generate a list of primes in advance.

[jeromie]

I thought the difficulty level was ok. Problem A was trivial. Problem B was in the sweet spot where a naive implementation would not work but optimization wasn't too difficult, so that was fun. I didn't solve problem C, but it didn't seem out of reach - just a bit hard. I've only got a few hours each evening where I can work on the problems (and I have to split that time with playing go ), so I think solving two problems is fairly reasonable.


On problem B:

My optimization was to factor the length of the input string and then only check substrings that were equal in length to one of the factors. I didn't check in advance, but the maximum number of factors of a number n can be given by the equation 2**(1.5379 * (log(n)/log(log(n)))), which comes out to a max of 4457 factors at the test case limit of 2 million. The average case will be smaller, but even in the worst case that's not too many cases to check in the allotted time.

On problem C:

Like peti29, I implemented a recursive backtracking solution that worked on small data sets but didn't handle the test input. That's actually not surprising.
A lot of problems in programming competitions like this seem like they can be solved with backtracking, but that is almost always the wrong approach. Backtracking is generally O(n!), which blows up the problem space very, very quickly unless you can find a way to severely prune the search tree. I could prune the tree significantly for the average case, but I'm sure the test cases included adversarial input designed to foil most common pruning strategies.

I suspect that there is a numeric solution that doesn't involve ordering the strings at all. I have some idea of the proper data representation (all you need to know about each string is the number of unmatched open parentheses, the number of unmatched closed parentheses, and the length of the string), and some important simplifications (the total number of open and closed parentheses must match, any substrings that consist of matched parentheses can add their length to the solution without further impacting the search space), but I never had the flash of insight that usually accompanies the discovery of the proper algorithm.