Could you describe the approach for VCAKE plz?
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
You must agree that following conditions should hold:
- R*C = M + K + J
- One piece should have one of the dimension as R or C (think about it)
- 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
right, couldnāt proceed further or had some bugs in my code, could you please share your code.
I guess weād have to wait till they publish the editorials. The submissions arenāt public as yet.
try this
4 8
Thanks. About COLTREE i implemented nCr and factorial discarding tree structure but I got WA. What was your approach?
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.
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.
How you solved the 4th one?
@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
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.
@pranavarora - simple subset sum solution - for(i=0; i<n; i++) { for(j=MAX; j>=a[i]; jā) possible[j] |= possible[j-a[i]] }
If you donāt mind, can you please share the code?
- make a set of east west moves. call sum of this set as sum1.
- make a set of north south moves. sum of this set = sum2.
- find closest sum of subsets to sum1/2 and sum2/2 in sets 1 and 2 and add them.
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.
@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.
Thanks!
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