What was this ?

general
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
24

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

25

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

26

try this
4 8

27

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

28

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.

29

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.

30

How you solved the 4th one?

31

@thezodiac1994. i tried a lot, can you give link to your solution if did using linear diophantine way? My solution link: CodeChef: Practical coding for everyone

32

What is your approach to find the sum closest to sum/2. I tried the standard dp but got tle and couldnā€™t fix it until the end of contest. :confused:

33

@pranavarora - simple subset sum solution - for(i=0; i<n; i++) { for(j=MAX; j>=a[i]; jā€“) possible[j] |= possible[j-a[i]] }

34

If you donā€™t mind, can you please share the code?

35
1 Like
36
  1. make a set of east west moves. call sum of this set as sum1.
  2. make a set of north south moves. sum of this set = sum2.
  3. find closest sum of subsets to sum1/2 and sum2/2 in sets 1 and 2 and add them.
37

https://www.cs.cmu.edu/~adamchik/21-127/lectures/divisibility_5_print.pdf

Read the part on positive solutions.

my soln - CodeChef: Practical coding for everyone.

38

@giorgosgiapis For COLTREE my approach. Suppose you choose i colours to use (nCr(k,i) ways), then you need to partion the tree in i different units that can be done simply by selecting any i-1 edges (nCr(n-1,i-1) ways ) and then arranging the i colors (i! ways). Sum over this from i = 1 to i =min(k,n).
I got WA once because I sumed from i = 1 to i = k, may be that would have been the case for you as well.
Thank you.

39

Thanks! :slight_smile:

40

Can you please upload it on ideone @thezoidac1994. They have not made solution visible yet. Edit: this was my code: DsTMC7 - Online C++0x Compiler & Debugging Tool - Ideone.com