Unofficial Editorials December Lunchtime

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

Great editorials btw! :smiley:

Thanks @chant_coder

@bhpra its not O(1) I guess it is O(logn) .

To be frank, i didn’t think about time complexity, but implemented it because i had an intuition that this will be accepted.

Theoretically, worst case complexity should be around 50^4, but i don’t think this limit is actually achieved in any test case.

@beginner_1111 can you explain how

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.