L19 Programming Problem Championship: Round 2 (Strings)

[Solomon]

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)

[peti29]

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

[Kirby]

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

[jeromie]

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.

[Solomon]

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.

[jeromie]

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.

[Solomon]

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!

[Solomon]

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

[quantumf]

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?

[Solomon]

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

[phillip1882]

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

Code: Select all

x = raw_input()
if x == "":
    print 0
for i in range(0,len(x)):
    check = True
    if len(x)%(i+1) == 0:
        for j in range(0,len(x)):
            if j+i+1 < len(x) and x[j] != x[j+i+1]:
                check = False
                break
    if check:
        print len(x)/(i+1)
        break

[Solomon]

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

Code: Select all

x = raw_input()
if x == "":
    print 0
for i in range(0,len(x)):
    check = True
    if len(x)%(i+1) == 0:
        for j in range(0,len(x)):
            if j+i+1 < len(x) and x[j] != x[j+i+1]:
                check = False
                break
    if check:
        print len(x)/(i+1)
        break

First, you should make sure your program is in a loop and checks for "." to break, as your program currently just accepts one string. Looking at just the algorithm though, consider this test case: aabbaabbaabbaabb

[Bill Spight]

I was getting a TLE on test case #2 in Python 3, but got AC in C++

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

[peti29]

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

[gamesorry]

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