It is currently Thu Mar 28, 2024 4:56 pm

All times are UTC - 8 hours [ DST ]




Post new topic Reply to topic  [ 54 posts ]  Go to page 1, 2, 3  Next
Author Message
Offline
 Post subject: L19 Programming Problem Championship: Round 2 (Strings)
Post #1 Posted: Fri May 05, 2017 7:23 am 
Gosei
User avatar

Posts: 1848
Location: Bellevue, WA
Liked others: 90
Was liked: 837
Rank: AGA 5d
KGS: Capsule 4d
Tygem: 치킨까스 5d
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:

Top
 Profile  
 
Offline
 Post subject: Re: L19 Programming Problem Championship: Round 2
Post #2 Posted: Fri May 05, 2017 1:25 pm 
Lives with ko

Posts: 125
Liked others: 13
Was liked: 12
Rank: KGS 5 kyu
I'm eagerly waiting! Though it'll be 4am here, so it'll take some time until I can check the problems ;-)

Top
 Profile  
 
Offline
 Post subject: Re: L19 Programming Problem Championship: Round 2
Post #3 Posted: Fri May 05, 2017 4:58 pm 
Honinbo

Posts: 9545
Liked others: 1600
Was liked: 1711
KGS: Kirby
Tygem: 커비라고해
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

Top
 Profile  
 
Offline
 Post subject: Re: L19 Programming Problem Championship: Round 2
Post #4 Posted: Fri May 05, 2017 9:14 pm 
Lives in sente

Posts: 902
Location: Fort Collins, CO
Liked others: 319
Was liked: 287
Rank: AGA 3k
Universal go server handle: 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.

Top
 Profile  
 
Offline
 Post subject: Re: L19 Programming Problem Championship: Round 2
Post #5 Posted: Fri May 05, 2017 9:56 pm 
Gosei
User avatar

Posts: 1848
Location: Bellevue, WA
Liked others: 90
Was liked: 837
Rank: AGA 5d
KGS: Capsule 4d
Tygem: 치킨까스 5d
jeromie wrote:
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.

Top
 Profile  
 
Offline
 Post subject: Re: L19 Programming Problem Championship: Round 2
Post #6 Posted: Fri May 05, 2017 11:05 pm 
Lives in sente

Posts: 902
Location: Fort Collins, CO
Liked others: 319
Was liked: 287
Rank: AGA 3k
Universal go server handle: 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. :-)

Top
 Profile  
 
Offline
 Post subject: Re: L19 Programming Problem Championship: Round 2
Post #7 Posted: Fri May 05, 2017 11:06 pm 
Gosei
User avatar

Posts: 1848
Location: Bellevue, WA
Liked others: 90
Was liked: 837
Rank: AGA 5d
KGS: Capsule 4d
Tygem: 치킨까스 5d
jeromie wrote:
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! :tmbup:

Top
 Profile  
 
Offline
 Post subject: Re: L19 Programming Problem Championship: Round 2
Post #8 Posted: Fri May 05, 2017 11:24 pm 
Gosei
User avatar

Posts: 1848
Location: Bellevue, WA
Liked others: 90
Was liked: 837
Rank: AGA 5d
KGS: Capsule 4d
Tygem: 치킨까스 5d
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) :).

Top
 Profile  
 
Offline
 Post subject: Re: L19 Programming Problem Championship: Round 2
Post #9 Posted: Fri May 05, 2017 11:31 pm 
Lives in sente
User avatar

Posts: 842
Liked others: 180
Was liked: 151
Rank: 3d
GD Posts: 422
KGS: komi
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?

Top
 Profile  
 
Offline
 Post subject: Re: L19 Programming Problem Championship: Round 2
Post #10 Posted: Fri May 05, 2017 11:46 pm 
Gosei
User avatar

Posts: 1848
Location: Bellevue, WA
Liked others: 90
Was liked: 837
Rank: AGA 5d
KGS: Capsule 4d
Tygem: 치킨까스 5d
quantumf wrote:
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.

Top
 Profile  
 
Offline
 Post subject: Re: L19 Programming Problem Championship: Round 2
Post #11 Posted: Sat May 06, 2017 9:04 am 
Lives in gote

Posts: 319
Liked others: 4
Was liked: 39
Rank: 6k
GD Posts: 25
OGS: phillip1882
i cant for the life od me figure out whats wrong with my solution to the power sum problem.
heres my code.
Code:
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

Top
 Profile  
 
Offline
 Post subject: Re: L19 Programming Problem Championship: Round 2
Post #12 Posted: Sat May 06, 2017 9:23 am 
Gosei
User avatar

Posts: 1848
Location: Bellevue, WA
Liked others: 90
Was liked: 837
Rank: AGA 5d
KGS: Capsule 4d
Tygem: 치킨까스 5d
phillip1882 wrote:
i cant for the life od me figure out whats wrong with my solution to the power sum problem.
heres my code.
Code:
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

Top
 Profile  
 
Offline
 Post subject: Re: L19 Programming Problem Championship: Round 2
Post #13 Posted: Sat May 06, 2017 12:15 pm 
Honinbo

Posts: 10905
Liked others: 3651
Was liked: 3374
Solomon wrote:
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.

;)

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

Visualize whirled peas.

Everything with love. Stay safe.

Top
 Profile  
 
Offline
 Post subject: Re: L19 Programming Problem Championship: Round 2
Post #14 Posted: Sat May 06, 2017 5:57 pm 
Lives with ko

Posts: 125
Liked others: 13
Was liked: 12
Rank: KGS 5 kyu
My name is persistence...
After 12 tries I finally got B :salute:
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.)


This post by peti29 was liked by 3 people: Bill Spight, gamesorry, Solomon
Top
 Profile  
 
Offline
 Post subject: Re: L19 Programming Problem Championship: Round 2
Post #15 Posted: Sat May 06, 2017 7:41 pm 
Lives with ko

Posts: 149
Liked others: 276
Was liked: 49
Rank: 3d
KGS: 3d
DGS: 3d
OGS: 3d
Stuck in problem 2 with TLE :cry: and then problem 3-5 look even more difficult ...

Top
 Profile  
 
Offline
 Post subject: Re: L19 Programming Problem Championship: Round 2
Post #16 Posted: Sun May 07, 2017 11:17 am 
Lives in sente
User avatar

Posts: 842
Liked others: 180
Was liked: 151
Rank: 3d
GD Posts: 422
KGS: komi
Problems 3-5 are a major jump in difficulty.

Top
 Profile  
 
Offline
 Post subject: Re: L19 Programming Problem Championship: Round 2
Post #17 Posted: Sun May 07, 2017 11:17 am 
Honinbo

Posts: 9545
Liked others: 1600
Was liked: 1711
KGS: Kirby
Tygem: 커비라고해
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

Top
 Profile  
 
Offline
 Post subject: Re: L19 Programming Problem Championship: Round 2
Post #18 Posted: Sun May 07, 2017 3:40 pm 
Lives with ko

Posts: 125
Liked others: 13
Was liked: 12
Rank: KGS 5 kyu
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...

Top
 Profile  
 
Offline
 Post subject: Re: L19 Programming Problem Championship: Round 2
Post #19 Posted: Sun May 07, 2017 3:47 pm 
Lives with ko

Posts: 259
Liked others: 46
Was liked: 116
Rank: 2d
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.

Top
 Profile  
 
Offline
 Post subject: Re: L19 Programming Problem Championship: Round 2
Post #20 Posted: Sun May 07, 2017 5:30 pm 
Gosei
User avatar

Posts: 1848
Location: Bellevue, WA
Liked others: 90
Was liked: 837
Rank: AGA 5d
KGS: Capsule 4d
Tygem: 치킨까스 5d
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...).

Top
 Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 54 posts ]  Go to page 1, 2, 3  Next

All times are UTC - 8 hours [ DST ]


Who is online

Users browsing this forum: No registered users and 1 guest


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