Unofficial Editorials December Lunchtime

general
, , , ,
21

I know there can be many optimizations, but i happened to keep my solution simple.

And by the way, your statement proves that only those certain states will be visited where for example N = P-p+Q-q. My solution, technically won’t visit such states.

Yeah, your optimization is really helpful for reduction of dp table size, but i happened to use map, which solved my problems.

22

Very nice. But this means that the time limit is very very lenient, I wonder why.

23

@meooow, my solution would be costly had i used dp table. But by using map, i didn’t visit those states. Therefore, there might be only slight difference in runtime i guess.

24

F(A^n)=F((F(A))^n) so i calculated F(a) now only possible values of a are from 0 to 9 if it is 0 or 1 the f(a)^n will be only 0 and 1 respectively. if it is 3 ,6 or 9 the if n==1 then it will be 3,6,9 respectively else it will be 9. for 2 and 5 it repeat the patter of sum. the pattern of sum for the power’s of 2 is {2,4,8,7,5,1} ans for and sum pattern 5 is {5,7,8,4,2,1} ans similar for 7 ,8,4

25

I have explained by Combinatorics approach briefly for Too Much Sweetness below:

Let us say our sequence formed is x1y1x2y2…xkyk, where xi is the number of sweets taken out from first box in the ith turn, and similarly for yi. Notice here there are three other cases which can be similarly dealt with:

  1. y1x1y2x2…ykxk 2) x1y1x2y2…yk-1xk 3) y1x1y2x2…xk-1yk

Now we need to find the number of solutions to the equation for each k (max limit depending upon B1 and B2).

x1 + y1 + x2 + y2 + … + xk + yk = n

=> (x1 + x2 +… +xk) = n1 and (y1 + y2 +… + yk) = n - n1 such that xi ranges from 1 to S1 and yi ranges from 1 to S2.

This can be done using Multinomial and Inclusion and Exclusion. How?

Let us consider x1 + x2 + … + xk = n1, x1 can range from 1 to S1.
Now, take a substitution zi = xi - 1

So, z1 + z2 + … + zk = n1 - k, zi can range from 0 to S1 - 1(both inclusive)

Let us say there was no upper bound then by Multinomial we have number of solutions as NcR(n1 - k + k - 1, k - 1).
But there are some other solutions in which zi >= S1. So that can be removed from the answer by taking similar substitutions and Inclusion - Exclusion.

Code: https://www.codechef.com/viewsolution/16718580

10 Likes
26

I explained it as a reply as it wasn’t fitting in a comment :v

27

@taran_1407 it’s not about that, my comment was for @teja349. By his optimizations, the complexity comes to \mathcal{O}(p^3). Actually it can be reduced further to \mathcal{O}(p^2 + N^2) by considering box 1 and 2 separately as I have done in my solution (not optimal). So in the worst case iterations required is in the order of 10^4 only. Whereas there were 10 test cases with a time limit of 3 sec!

28

Oh…

I thought you was saying that about my solution.

And Yeah, i too wondered, because when i read problem statement, i expected p+q upto 1000.

29

What is the complexity for F(n) ?

30

4th problem can be solved using centroid decomposition. Let L be the lca of U and V in the centroid tree. So the path between U and V can be broken down into two parts, U to L and L to V. Also we know that the centroid tree has at most log(n) depth, so each node has atmost log(n) ancestors. We store information about the path between U and ancestors of U(say A). We store the cost of each edge between U and A in a vector v[A] and sort them. Then using binary search and prefix sums we can process each query in log(n).
Expected Time Complexity: log(n) per query with nlog(n) preprocessing.

1 Like
31

Thank you for the lovely editorials!
I too tried to memoize my recursive solution for the 3rd question, but got AC verdict only for the 1st subtask. The others were TLE and WA. Looking at your solution, I don’t find much difference in my approach. Maybe I missed a trick somewhere.Could anyone help me find the error in my code?

Here’s a link to my submission https://www.codechef.com/viewsolution/16719858

32

Thank you for the “Too Much Sweet” Editorial.

key = (B2 + 201*(B1 + 201*( q + 201*(p+201*(N)))))*2 + prev%2)

This line of your code got me into thinking if there would be any pair of tuples ( tuple1 = (B2,B1,q,p,N,prev) and

tuple2 = (B2’,B1’,q’,p’,N’,prev’) ) will collide i.e. if tuple1 and tuple2 under any condition will yield the same key?

Also How did you came up with very hash formula ? Is there any specific norm ?

33

Thanks for the editorial. I have a couple comments:

Strange Function

We can simplify a bit further if we need to. We observe that f(A) simply maps A to its equivalence class modulo 9 (just like A \mod 9, except multiples of 9 get mapped to 9 instead of 0). This is the key to the grade-school “divisibility by 9” check, and it is the reason why f(A^N) = f(f(A)^N). However, we can simplify even further.

  • If f(A) = 9, then f(A^N) = 9 for all values of N.
  • If f(A) \in \{3,6\} and N>1, then f(A^N) = 9, since A^N will be divisible by 9.
  • The remaining remainders \{1,2,4,5,7,8\} form a cyclic-group under multiplication of order 6. Thus, if we are not in the first two categories above, we can instead calculate f(f(A)^{(N\%6)}).

TL;DR,

  • If A is divisible by 3 and N > 1, print 9
  • Otherwise, just calculate ((A \mod 9) ^ {(N \mod 6)}) \mod 9. If the answer is 0, print 9, otherwise, just print that result.

Too Much Sweetness

(Full disclosure: my programming is rusty, do I didn’t get AC during the contest and only later in the afternoon (after debugging silly mistakes))

I used what I thought was perhaps a slightly more efficient approach than the one described. I also like it because the first half is a pretty generic piece of code that can possibly be used elsewhere. I broke the problem up into two parts:

  • I used DP and precomputed the ways to split up n objects into k non-empty partitions where each partition was no bigger than s. I stored these in a 3-D array (i.e. ways[n][k][s]).
  • I then used these to solve each query with a nested for loop per query (looping over the number of candies of type 1 and then the number of trips to the first box). After fixing these two terms, the number of candies of type 2 is determined, and there are only 3 possibilities for the number of trips to the 2nd box.

The thing I liked about this was that we could reuse the same DP result for both types of candies which kept the size of the DP down. The code seemed to execute several orders of magnitude faster than the time limit.

1 Like
34

Can you explain how you’re excluding the solutions with z_i \ge S_i? Is it possible to do that by fixing some i elements such that S_i \le z_i \le p and excluding those solutions?

1 Like
35

Well, i too tried centroid decomposition but couldn’t formulate the idea properly.

Would be a lot better if you could share your implementation with us.

36

I checked the constraints of p, q, B1 and B2 and choose 201. To get a better idea, consider a grid with n rows and M columns. Each cell can be uniquely represented as i*M+j where i and j are row number and column number respectively.(0<= i <N, 0<=j<M).

I used same hash for multiple variables.

1 Like
37

Yes, ur solution for strange function is very neat and simple. But i believe its and overkill here. My approach can also be applied where F(X) is “strangely” defined, say any unique property.

I liked ur solution of too much sweetness, but it requires good knowledge of combinatorics which even i dont possess. Ur solution has better time complexity, but mine is widely applicable. :slight_smile:

38

I cannot surely say, but i suspect ur hash function to be faulty. Consider ur has function for 2 pair of values (1,111) and(11, 11) both will have hash value “1111”.

Conclusion: your hash function is poor.

1 Like
39

@taran_1407 ‘Strange Function’ can be solved with O(1) with a bit of precomputation like @bhpra said. Basically, we need to find cycle for each value from 1 to 9 inclusive.


[1]


  [1]: https://www.codechef.com/viewsolution/16705694

EDIT - Yes it's complexity O(log(log(...(n))..)
1 Like
40

Initially I thought of keeping the constraints so as to pass only solutions of order 50^3 (4 states) but then I changed it so as to pass 50^4 (5 states) also. I didnt know about the 50^2 solution and also of the combinatorics solution. Its good to see people coming up with so many different ideas.