What was this ?

general
1

Am i the only one who couldn’t solve any problem :frowning:
Frustrated.

2 Likes
2

Beleive me you are not. Problem set was harder than last years without any cakewalk problem!

2 Likes
3

I solved one in 26 mins, then it took me 21 wrong tries. And it was like, “What am I doing with my life!” :stuck_out_tongue:
And the 21 went in vain.

4

I think problems weren’t hard this time but a lot trickier, even though I could solve only 2 problems (VCAKE and COLTREE) , in COLTREE only n and k were required and not the structure of the tree.

I think solutions of first 4 problems won’t be more than 10 lines of code.

5

IMO, it was easier than last year, first 2 problems were really trivial.

6

I think problems weren’t hard this time but a lot trickier, even though I could solve only 2 problems (VCAKE and COLTREE) , in COLTREE only n and k were required and not the structure of the tree.

I think solutions of first 4 problems won’t be more than 10 lines of code.

7

Can you please explain 2nd problem, could not get it even now, what I understood was, you are given sum of A.P and number of terms in the A.P and you want to know whether a positive integer A.P exists or not with such property.

8

Did anyone solve the second question , “Chocolate for Everyone” ?

Spent 2-3 hours trying euclid’s method and what not , to no avail !

1 Like
9

Well, you want to solve Nx+d*(N-1)*N/2 = C where x and d >=1, u have 2 cases if N is even or odd

10

Could you describe the approach for VCAKE plz?

11

can any one tell me how you solved 2nd one ? I formed the equation in ax+bx=c after that I used the condition
if(c% gcd(a%b) ) is true then yes …

12

Initially I subtracted n*(n+1)/2 from C to ensure that each get atleast one with common difference>=1. But still got WA. Dont know why :frowning:

13

You must agree that following conditions should hold:

  1. R*C = M + K + J
  2. One piece should have one of the dimension as R or C (think about it)
  3. Then you are left with a reduced cake with dimensions (X) * (X’ - Z/X), (X = R or C, X’ = C or R, Z = M or K or J, resp.), then apply same process as in 1 and 2 for 2 pieces.

My solution link : http://ideone.com/5TGjIZ

1 Like
14

right, couldn’t proceed further or had some bugs in my code, could you please share your code.

15

I guess we’d have to wait till they publish the editorials. The submissions aren’t public as yet.

16

try this
4 8

17

Thanks. About COLTREE i implemented nCr and factorial discarding tree structure but I got WA. What was your approach?

18

For second one you need to make sure that the solution to ax + by = c has positive values for a and b. You can solve that by modifying the linear diophantine.

19

The problems were easier than last year’s:

I solved the following:

  1. VCAKE: only 2 possible cake cuts: make cases.

  2. ARITHM: see equation of sum and cases on whether n is odd or even.

  3. COLTREE: no tree required: just f(n,k) simple DP.

  4. RWALK: subset sum - hit nearest to sum/2.

The above 4 were not more than 20 lines.

  1. SEGSUMQ - simple range sum query on persistent segtree(tedious to code)

Though I did not solve NUMSET, it should be doable by max-flow or some MIS algorithm for such special graphs.

1 Like
20

What was the approach for the third one ? I skipped that and did the 4th instead as I couldn’t make any progress and eventually had to move on.