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?
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.
@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.
@taran_1407 Only two observations were to be made to solve the second question in O(1) time for each query.
F(A^N) = F(F(A)^N)
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.
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.
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.
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.
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)