Unofficial Editorials December Lunchtime

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[U][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

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 CodeChef: Practical coding for everyone

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 ?

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

@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

@taran_1407 Only two observations were to be made to solve the second question in O(1) time for each query.

  1. F(A^N) = F(F(A)^N)
  2. If the sum of digits of A is 1 or 9, the answer will always be the number itself. For 3 & 6, if N = 1, it will be the number itself. Else if N > 1, it will always be 9.
  3. For the remaining numbers 2, 4, 5, 7 & 8 we just needed to find the cycle after how many multiplication the sum of digits will start repeating.

Here is the link to my solution which runs in constant time for all the subtasks.

1 Like

I need some help in question “Too much sweetness”. I have implemented it in similar way as explained in editorial, but getting WA even for subtask#1.

My code is: [CodeChef: Practical coding for everyone][1]

Thanks in advance!!
[1]: CodeChef: Practical coding for everyone

@taran_1407: can u plzz explain this briefly

we can directly compute f((f(A))N). Doing this avoids the issue of overflow.

@sukhbir947 your logic and approach to the problem is wrong… it will give wrong answers in some test cases like these…

1
2 3 5
2 2
1 1

please dry run it and then check your logic… :smiley:

can someone please explain me the O(50^3) solution of 3rd problem. I had read the comments above but didn’t get it! please help.

Hii there,in the Question “Too Much Sweetness”, during the contest I tried this approach
Algo:

  • Generate all the 2^N permutations containing 1 and 2.
    -check every permutations if it satisfies all conditions
    if yes cnt++;

this approach has Time complexity = O(2^N)
for subtask 2, N=p+q<=20 so TO(2^N) = 10O(2^20) = 10^7(approximately)
so this solution should pass subtask 1 and 2.
But my solution is clearing only subtask1 and give TLE for the second.
my code :CodeChef: Practical coding for everyone
Plz help me to rectify this.

@taran_1407 ur editorials are easy to understand than most others
too much sweetness u explained in just 2 lines …

I have never implemented Persistent Segment Tree. So, it would be better if you could either share your approach in detail, possibly accompanied by implementation if possible.

PS: Thanks

Sorry i too couldn’t implement it due to lack of time,if u wanna read it refer this: https://blog.anudeep2011.com/persistent-segment-trees-explained-with-spoj-problems/

Didn’t expect a Combinatorics solution for this problem.

To understand it more clearly,u could assume that there are N segment trees for each combination (1 for each node) where N is the number of nodes in tree which store the valid edges along the path from root to that node.Persistent just helps to use previous things (as u could see for a node v the segment tree would be the same as its parent except that only edge[v][parent] is not included in parents segment)

I too tried this, but forgot to consider ans == 9 case and got many WAs.

1 Like

Can you explain the logic behind this?

Yeah,I too didn’t expect a combinatorics solution. Infact I think DP solution is quite simple.It was an overkill I suppose :stuck_out_tongue: .

Can you explain the math behind your solution? @shubhiks