What was this ?

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