Can someone please share the approach for MONSTER problem?
Thanks a lot everyone…It was really nice learning new concept SoS dp…
For those who are also seeking answer to the same question do read http://codeforces.com/blog/entry/45223 its a nice blog on SoS dp.
1 Like
isn’t it exceeding the time limit? (q^(1/2)* (17 * 2^(17))) ~ 2^30?
@taran_1407 , @anushi how did you knew after reading MONSTER problem that it can be solved by sos dp, did you already knew sos dp technique. if not then how did you thought that it can be solved using sos dp and read about it. I was also trying to solve this problem but had no idea that this technique existed and can be solved using that. It would really helpful if you can tell what to search for while solving such problems in long contest.
1 Like
You can read about SOS DP here: http://codeforces.com/blog/entry/45223. Btw, it isn’t required to solve it.
@avi224 my doubt is not about sos dp , my doubt is how to search about relevant topics while solving a problem during long contest when you have no idea what the problem is about.
@akash_321 Filter the key words from the problem and search. You would get the relevant topics mostly on codeforces or stackoverflow(or research papers for hard problems).
For example, if you search “update subset index of x codeforces”, you’ll get the first link to SOS DP.
1 Like
what we will get by doing sos dp over each block ??
any reason why we are doing sos ??
@taran_1407 @anushi @sdssudhu