Leaderboard

1. dfan - 7
2. bernds - 7
3. ugoertz - 6
4. Solomon - 4
5. quantumf - 1

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

Start Time: 2017-05-06 02:00:00 UTC (Fri May 5 2017 7pm PST)
Duration: 50 hours
Problems: 5
Theme: Strings

Past Rounds:

• Round 1 (April 28 2017)

I'm eagerly waiting! Though it'll be 4am here, so it'll take some time until I can check the problems

I'll join you guys Saturday or Sunday. My parents are still visiting, but they'll leave tomorrow.

We'll have a party tonight so I probably won't be in a good state to program

_________________
be immersed

Argh. I'm a little annoyed by the 3 second time requirement for problem 2 in this week's set. I wrote my solution in Python, and in what should be pretty close to the worst case scenario (10 2 million character strings with no repetition), it runs on my computer in 1.7 seconds. It's failing one of the test cases on time, though. It's hard to tell whether it's my algorithm being inefficient or Python running slowly on their machine.

Well, given the fastest time solutions are really, really fast I'm sure I can improve my algorithm. Back to the drawing board.

EDIT: Ok, I found what was likely making my program run slowly in some situations.

To add a data point, I wrote the same algorithm in both Python 3 and C++, and I was getting a TLE on test case #2 in Python 3, but got AC in C++, and it's not a long and crazy algorithm (C++ program is 50 lines long, Python program is 35 lines long). I'm sure with tricks and optimizations you could get a Python solution to squeeze in, but you'll most likely be fighting the language.

There's a mildly amusing video where in Google Code Jam 2015 World Finals, there was one participant (linguo) who was the only person using Python. On Problem A for the large input, you can see him watching his Python program crunch through the input file while the clock was ticking on the submission time deadline (once you send a request to download a large input, you only have several minutes to submit it once). He barely get it in.

There were certain types of input my program failed on terribly. I rewrote the algorithm and got .62 second (by their measurement) with a Python3 program, so my issue was definitely an algorithm problem and not a language problem. I look forward to talking about the different approaches after the contest.

Nice!

Stuck on C (and it seems like I'm not alone), so I'm going to sleep on it (I do the same for hard tsumego hah) .

For B (Java), my first attempt was apparently too slow. I then did a minor optimization (about 10%). Since there doesn't seem to be any penalty for multiple attempts (Solomon, is that true?), I re-submitted it anyway, and it worked, with a time of 1.27s. Obviously the data in their input is very different compared to mine if my 10% improvement made such a difference on their input. Is there a way to see the input after a successful submission?

After running the numbers, it looks like the penalty is 20 minute per incorrect submission. Given that the contest is over 50 hours, it shouldn't really matter. And I don't think there's a way to see the test case inputs after successful submissions, unfortunately.

i cant for the life od me figure out whats wrong with my solution to the power sum problem.
heres my code.

Temporal Lobe Epilepsy is a serious condition, but I'm not sure that Alternating Current is the answer.

_________________
The Adkins Principle:
At some point, doesn't thinking have to go on?
— Winona Adkins

Visualize whirled peas.

Everything with love. Stay safe.

My name is persistence...
After 12 tries I finally got B
The solution just seems absurd to me though... :p
(Also it seems I'm way too paranoid. I ported my solution into javascript thinking that C# Mono environment must be crap before I finally got it. That said, I was using an online .Net fiddle thing lacking any profiling or debugging capability.)

Stuck in problem 2 with TLE and then problem 3-5 look even more difficult ...

Problems 3-5 are a major jump in difficulty.

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?

_________________
be immersed

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

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.

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