Search found 19 matches

by pdwd
Mon Oct 04, 2010 5:37 am
Forum: Volume 101 (10100-10199)
Topic: 10118 - Free Candies
Replies: 2
Views: 2347

Re: 10118 - Free Candies

The crucial observation is the fact that at each state (i, j, k, l) - (heights of each pile) candies in a basket are assigned interchangeably.
by pdwd
Tue Sep 28, 2010 3:21 am
Forum: Volume 118 (11800-11899)
Topic: 11830 - Contract Revision
Replies: 20
Views: 4768

Re: Contract revision_11830

7 777 should be 0
by pdwd
Sun Sep 26, 2010 7:46 pm
Forum: General
Topic: Waterloo Local 2010, Fall 1
Replies: 6
Views: 4702

Re: Waterloo Local 2010, Fall 1

Password is empty, but there are no problems anyway.
by pdwd
Sun Sep 26, 2010 6:33 pm
Forum: General
Topic: Waterloo Local 2010, Fall 1
Replies: 6
Views: 4702

Waterloo Local 2010, Fall 1

Why this contest is private? I think this is a bug, because Fall 2 is open, can you unlock it please?
by pdwd
Sun Sep 26, 2010 2:46 am
Forum: Volume 118 (11800-11899)
Topic: 11830 - Contract Revision
Replies: 20
Views: 4768

Re: Contract revision_11830

You don't have answer for 7 777 in your output.
by pdwd
Thu Sep 23, 2010 10:47 pm
Forum: Volume 118 (11800-11899)
Topic: 11843 - Guessing Game
Replies: 10
Views: 3723

Re: 11843 - Guessing Game

It's enough to check k to i/2+1, because dp[k, j-1] >= dp[k, j] and dp[k1, j-1] > dp[k2, j] if k1 > k2. By checking k > i/2+1, you will always get from max dp[k-1, j-1].
I still believe there is a way to ask only 2 or 3 questions and get O(n*s) solution. Does anyone have such idea?
by pdwd
Mon Sep 20, 2010 9:02 pm
Forum: Volume 118 (11800-11899)
Topic: 11838 - Come and Go
Replies: 22
Views: 7360

Re: 11838 - Come And Go

You can use dfs to find strongly connected components and check if there is only 1 such component.
by pdwd
Mon Sep 20, 2010 8:25 pm
Forum: Volume 118 (11800-11899)
Topic: 11841 - Y-game
Replies: 3
Views: 1387

Re: 11841 - Y-game

Code: Select all

Willy
Willy
Benny
Willy
Benny
Benny
Benny
Willy
Benny
Benny
Benny
Benny
Benny
Benny
by pdwd
Sat Sep 18, 2010 3:08 am
Forum: Volume 110 (11000-11099)
Topic: 11081 - Strings
Replies: 35
Views: 19519

Re: 11081 - Strings

This is my solution: Let a - first string, b - second string, c - third string. I have dp[k] [j] - number of ways to make c[1..k] using letters from a[1..i] and b[1..j] dp[0] [j] = always 1 (there is only one way to make empty string - remove all letters from a and b) dp[k] [j] = dp[k][i-1][j] + dp[...
by pdwd
Thu Sep 16, 2010 10:52 pm
Forum: Volume 105 (10500-10599)
Topic: 10558 - A Brief Gerrymander
Replies: 6
Views: 5052

Re: 10558 - A Brief Gerrymander

Maybe this part of task could be helpful for those of you, who get WA
"The city is bounded by four roads: 1st Street (west edge), 100th Street (east edge), 1st Avenue (south edge), 100th Avenue (north edge). Clearly these four roads must represent district boundaries;".
by pdwd
Sun Sep 05, 2010 12:57 pm
Forum: General
Topic: Java
Replies: 0
Views: 3038

Java

In my opinion you should show special information in visible place during the contest about submitting java:
viewtopic.php?f=31&t=7429
Also you could give compilation errors as you do after submitting problem from problemset.
by pdwd
Thu Aug 26, 2010 7:34 am
Forum: Volume 108 (10800-10899)
Topic: 10817 - Headmaster's Headache
Replies: 25
Views: 15936

Re: 10817 - Headmaster's Headache

Can somebody explain me how to get: a) time complexity O(n*4^s) b) time complexity O(n*3^s) I have O(n*s*2^(2s)) for each masc 'M' I must compute the set 'S' for actual applicant than I can substract from this masc min(dp[M], dp[M-S]). I cannot compute 'S' at the begining of processing actual applic...
by pdwd
Wed Aug 25, 2010 2:36 am
Forum: Volume 105 (10500-10599)
Topic: 10599 - Robots(II)
Replies: 27
Views: 10142

Re: 10599 - Robots (II)

Is it possible to solve this problem faster than O(n^2*m^2) ?
by pdwd
Fri Jul 30, 2010 12:18 am
Forum: Volume 6 (600-699)
Topic: 662 - Fast Food
Replies: 22
Views: 10327

Re: 662 - Fast Food

Try to guess the space of subproblems. Some hints:
- I have dp[j], where i - number of restaurant, j - amount of depots I want to install
- Time complexity is O(n^2*k), does anyone have a better solution?

Go to advanced search