What was this ?

general
4

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

5

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.

6

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
7

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 …

8

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
9

this and this, similar to Jealous Numbers

10

Can anyone provide solution to vCake problem? I solved all possible cases, yet it gave me “Wrong Answer!”… not sure why…

11

Here’s my solution for the VCake problem.link text
Would be helpful if someone posts the solution for the second one.

12

Can anyone give the solution for color tree ?

13

In the problem VCake can someone clarify what is meant by the line:
They want their pieces to be connected (in one piece), and rectangular in shape.
Does that mean that each piece should necessarily share its boundaries with other two pieces?

If thats the case then what is the problem with this solution?

14

Can anybody help me out with jealous number question?
I tried a lot but couldn’t crack the logic :frowning:

15

Here is my solution to 2nd problem:
Chocolate Solution

Can anybody look to my solution of VCake. It is giving me WA and I have considered every possible combination to ensure it does not miss any case. Thanks
Cake solution

16

Second question was pattern based. when n is odd, sum should be divisible by n for a ‘Yes’. If the n is even then: temp1=an+(n-1)(n)/2 and temp2=an+(n-1)(n). These are the sum of first n terms in the AP with common diff=1 and 2. Now (sum-temp1)%n or (sum-temp2)%n should be 0 for a ‘Yes’.

17

How many T-shirts will be sent?

18

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.

19

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.

20

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

21

Could you describe the approach for VCAKE plz?

22

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:

23

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 : 5TGjIZ - Online C++ Compiler & Debugging Tool - Ideone.com

1 Like