Important Update: Our friends have noticed that the upcoming round collides with their contest and also weekend is full of many another contests, so the round is now moved to Monday, 29 August 2016 15:05 MSK. We are sorry for the inconvenience caused and hope that you'll understand us.
Hi everyone!
Codeforces Round #369 (Div. 2) will take place on 27 August 2016 at 16:05 MSK. As usual, Div.1 participants can join out of competition.
I would like to thank danilka.pro for helping me with the preparation of the round, MikeMirzayanov for the amazing Codeforces and Polygon platforms and also Phyto for testing the problems.
I am the author of all the problems, and danilka.pro also helped making one of the problems harder. This is my first round on Codeforces! Hope everyone will enjoy the problems and find them interesting. It is advisable to read all the problems ;)
In this round, you will help ZS the Coder and Chris the Baboon while they are on an adventure in Udayland. Can you help them solve their problems? :)
Good luck, have fun, and wish everyone many Accepted Solutions. :)
UPD : Also thanks to IlyaLos and HellKitsune for testing the problems too.
UPD 2 : There will be 5 problems and the scoring is standard : 500-1000-1500-2000-2500.
UPD 3 : Editorial
UPD 4 :
Congratulations to the winners :
Div. 1 winners :
Div. 2 Winners :
Timing although nice collides with Codechef lunchtime (•_•)
The time has been changed to not collide with the lunchtime round.
Now it's 3pm in timezone of most participants. Is it possible to launch round as usual?
You can't say "most participant". The usual staring time isn't good for some countries too. There just cannot be a starting time which is good for everyone.
That's because the Earth is a sphere. However, I think the time before Russia changed the time zone will be better than now.
And still >7k participants. It seems there are people who like this time.
Registrants, for now. With 44 min remaining, < 4k participants.
Or love contest :/
Since it's impossible for everyone to have a positive rating change, I wish high rating for everyone who deserves it and has been working hard.
so you are wishing low rating for the lazy ones.. :(
yes, they deserve that :)
We are all lazy. It's why we became programmers.
Not sure how you did it, but your wish has been granted in the past
Good to see zscoder start writing regular rounds now. I wonder what interesting problems he has in stock.
I wish not to see "unrated user" in top_10
Auto comment: topic has been updated by zscoder (previous revision, new revision, compare).
Auto comment: topic has been updated by zscoder (previous revision, new revision, compare).
Time not collide with contest lunchtime... Please don't play with my feelings.
UPD : Nevermind, Thanks for update...
Could you please postpone the contest a little bit? Something like 19:00 MSK would be great for everyone, because some of us are still working at 15:05 MSK.
And another part of us are not able to participate in evening. It is like rating updates — even if everyone have solved all problems, it is impossible to increase everyone's rating. For someone it will be bad, for another it will be good
No, it's not like that.
19:35 MSK in my local time is 00:35,it's difficult to please everyone ：）
It is a great time for East Asia time zone though, it's roughly 21:05 over here. You can't imagine how thankful I am to see and participate a round ending before the clock hits 12.
Things are not always same.. ... I will be thankful if the contest starts after 22:00.... We all have some job to do :)
More or less I think we can agree that starting before 00:35(the usual time) is a great idea. =D
Is the contest delayed for 3 days or is this a bug/mistake ?
I think it's a feature.
Reading the announcement before posting a comment would be a great idea.
There is a bold Important Update which means you should read it and it's important
This post was made right after the time was switched. It probably done while/right after the author made the post. I believe at the time of posting it there was no update.
Will problems be in russian language?
I think if a contest is in russian, they will say it in announcement ... and why should it be ?! author of contest is not from russia.. and a lot of people don't know russian !
UPD : I am so sorry about what I said... I didn't mean something bad ... It's just because I don't know English well...
The problems are always translated in russian or english by the coordonator,you can read them in both languages.
contest time change .....:(
The first thing that I saw here was arithmetic-progression tag :/
3, 6, 9, ...
Where is contest tomorrow?!
Thanks a lot zscoder i was just wondering how i would be able to give 3 contests with time colloiding with each other in a single day + i have an annual day also tomorrow of cse society and as last contest cost me too much -ve rating and i want to become expert again so can't afford to miss a regular round....
U solved my problem and also of many i think...so thank u so much zscoder:)
Thanks, Monday is better!!
Hopefully not a stupid question. What contests are there overlapping?
https://www.codechef.com/LTIME39
https://www.hackerrank.com/contests/world-codesprint-6/challenges
https://www.hackerearth.com/august-circuits/
http://codeforces.com/blog/entry/46790
https://atcoder.jp/
Look at them !!!
Also Atcoder!
mentioned :)
Isn't it a day later?
List of Contest, if someone need (^_^)
Oh now I won't be able to participate anymore :( sadlife
"wish everyone many Accepted Solutions", that's a joke right !?
why change the contest to 8.29？？？？？？excuse?
This is because of the many contests that are being held in this weekend (one of which clashes with the original time) so this is to allow everyone to have a chance to participate in all of them instead of being forced to choose between the clashing contests.
your problems in educational round are always among the most interesting problems I've ever met. Hope your round will be interesting too! 710E - Generate a String 691E - Xor-sequences 665E - Beautiful Subarrays 678D - Iterated Linear Function
I'm glad that you like my problems :) Just pointing out that 678E - Another Sith Tournament is not by me but is actually by dalex. My proposal for that round is 678D - Iterated Linear Function. Anyway, hope you enjoy this round too!
Please try to give a constant time for next rounds...
this guy has 2 Bronze medal in IMO
his results
so...
So, we should wait for lots of math problems :P
Why this round delay?
1.29 August 2016 15:05 MSK.
2.27 August 2016 at 16:05 MSK.
3. Aug/29/2016 18:05UTC+6.
Which is perfect time??????
Perfect timing of a contest...:-) thanks for shifting the contest.
List of Contest, if someone need (^_^)
Awful time. It's a middle of working day in Europe!
Where is our Gleb? :P
Auto comment: topic has been updated by zscoder (previous revision, new revision, compare).
Great , I'm so happy , Monday I can participate !!
كل تاخيره و فيها خيره :D
Chinese people will be glad to participate this round. It's on 20:05! The earrrrly time means we can almost see the rating changes!
I love arithmetic-progression :D
can U please put the contest 2 hour later? i and 37 of my friends are in class in this time and we really want to participate in this contest! thanks!
well, he can't satisfy all the pepole :p
Why people use this argument? Is it possible to check the distribution of participants among countries and answer that question once and for all?
Fine, go ask 40,000 users about their preferred time :3
Is it the only way that comes to your mind?
People specify the region in their's profile. For example, you are from Lattakia in Syria. Lattakia has the time UTC+02:00 which is the same as in Moscow (I didn't know that before :) ).
But Moscow is UTC+3
Yes, but current time is still the same — that is what I found interesting.
Keeping the previous problems in mind which are provided by the problemesetter zscoder in various educational round , i hope that today's round is going to be fantastic, wish you all positive rating change :)
Again 7k+ contestants :) i hope there won't be long queue!
Probably many registered for the previous date and won't be able to attend the contest.
Contest time is so bad, I hope change it to the usual Codeforces rounds time :(
(there is electricity outages in Syria in this time :p)
pray for being specialist .!
doesn't help always . saying from experience :/
it helps i you worked hard and pray in the same time ..not just a pray
Doesn't help if you're an expert :p
I meant my "praying for becoming a candidate master" didnt work . :P
In fact I got a -128 instead of +11 that i needed xD
Wow! *__*
yes it help if you are an expert..but if you are not it won't help
Auto comment: topic has been updated by zscoder (previous revision, new revision, compare).
7.5k regitered users, hope there won't be a large queue..
> 8k XD
8.3k till now, the queue will be sooooo large, I hope the servers won't break :\
could you delay the contest till i finish my ice cream
First round exceeds 8k
Check the following ratio after the contest:
.
This number is more important :)
They are important both :)
How many people feeling lazy for contest?
More than 1000 unrated users :/
WOW!! 8000+ contestant already registered.
8385 registration !!! Is it the highest ever ? WOW... way to go CF.. Love this platform.
Now is 8670 registration.
Very cool problems. (I liked problem C and D more)
I can't solve D, but my mind is same!
can u please explain how to solve C and D
c dp[n][m][k], where n-the number? we want to paint, m-color,k-how pretty ! dp[i][j][x]=min(dp[i-1][j][x],dp[i-1][1..m!=j][x-1) if color[j]!=0; else dp[i][j][x]=min(dp[i-1][1..m!=j][x-1);
D:
Let ans = 1 Count number of cycles and store in what cycle is a vertex. If a vertex doesn't belong to any cycle then reversing the edge won't matter so that contributes ans = ans*2 to the answer
Now if there is a cycle that contains k different vertex, then you have to reverse any of its edge so possibilities are 2**k — 2 (1 for no reversal and 1 for all reversal) So ans = ans * (2**k — 2)
Do this for every vertex that is not part of any cycle and for every cycle
Isn't it possible that when you flip edges not in a cycle you end up with another cycle?
No it isn't. It is a functional graph (just one edge from each vertex) So if you suppose have a edge u->v and if you reverse it to v->u then any path going through v will just stop at u and won't move any further.
No it isn't. It is a functional graph (just one edge from each vertex) So if you suppose have a edge u->v and if you reverse it to v->u then any path going through v will just stop at u and won't move any further.Here is my dp solution: 20251359.
I think, it's hard to explain :)
Could you explain it to me?
If my solution is correct answer is Product((2^cycle_len — 2)) * 2^unused.
unused = vericles outside cycle.
cycle_len = length of cycle.
i tried that and got wrong on 9
Strange, mine passed pretests. Maybe you have bugs?
cycles = strongly connected components?
No, just simple cycles like 1->2->3->4->1.
that`s what i did wrong
What is Product? And if we have many cycles?
There is at most 1 cycle in the graph. I just realized it post contest -_-
No, e.g.
There may be many but they are disjoint.
Please explain how to solve those two problems
Problem C :
DP[i][j][k] = minimum cost to color first 'i' trees such that the color of the ith tree is 'j' and beauty is k .
transitions are easy to think .
how did you solved D, i tried finding all strongly connected components and then and then using formula (2^k1-2)*(2^k2-2)*....*(2^kx-2) where x is the number of strongly connected components, ki — size of the k-th component and if a component has size 1 i multiply it with 2
I came up with the same idea but got that you have to consider the opposite edges and it makes that all the vertices are in the same scc :(
Can someone confirm your solution or prove its correctness? my solution was something similar.
let's wait and see how many div2 B solutions will fail at test n = 1
test 4 was n=1 . so no solution would fail i guess
I think in the case 4 n! = 1
Weird, I took care of that specific case and I got passed it immediate.
I think none, I saw like 10 solutions in my room and everyone checked for n = 1. (Maybe it was in pretests?)
I got hacked for it
not possible
How to solve E ?
Wilsons theorem ?
Div1E:
The denominator (B) is a power of 2, so for it you just need to count how many 2s you need to remove both from A and B (using modular inverse!). For (B-A), you can compute it straightforwardly in a loop but early break if you get 0.
how did you come up with that ?
It is quite straightforward. First one goes to any place, the second one can go to 2N - 1 places to avoid collision, third one has 2N - 2 free places, etc.
I meant how did you derive the formula ?
Consider the amount of days and the chances of any two of the people in the set doesn't have the same birthday. Do some maths and you will end up with this formula.
I had the same idea but i didn't know how to find the numerator ?! how ?
Wait... but (2^N-1 % MOD)(2^N-2 % MOD)...(2^N-K+1 % MOD) doesn't have the same amount of 2s as the values that are not under %MOD right....?
why the formula is
, but not 
, or why do we say that order here matters?
I get hit by pretest 4 so I probably missed out some exceptions in my last few minutes, but I strongly believe that my approach is correct.
For B, the value is (2^n)^k (before modulo 1e6+3, of course), it is not hard to prove, since there are (2^n) days and k people in the set, so this is the total case.
Denote A' as B-A, this value is (2^n)! / (2^n-k)! as we consider that the days are not clashing with each other.
To calculate A', you can just use a for loop from (2^n-k+1) to (2^n) to get the value, note that since MOD = 1e6+3, when you hit something that is divisible by MOD, just return 0.
The only part I failed is to make A' co-prime with B by counting the 2's in the for loop, but note that I am using values that are under modulo MOD so the amount of 2's are not exactly correct.
The combinatoric(probabilistic) problem wasn't too hard.
Answer is
The real problem i think is compute this value modulo mod.
Notice than when k > = mod the term that involves factorials is equal to 0, so answer isn't that hard in that case, but remains the problem of reduce the fraction. The only prime factor of the denominator is 2, so you need to find the biggest p such that 2p divides the numerator. Then multiply both num and den for the multiplicative inverse of this number and voila...
Hats off to zscoder for such an awesome problemset, especially problem D :)
can you explain your solution?
For each component of the graph, because it has x vertices and x edges, there exists exactly one cycle. In this cycle, by switching edges, the only way you can end up with another cycle is if you don't switch any edges, or you switch all of them. So if the cycle has y vertices, you have (2^y — 2) valid sets of edge switches. And it's not hard to find the cycle length with a simple dfs.
You can also notice that for every other edge it doesn't matter if you switch it or not, so for a component of size x with a cycle length of y, the answer is (2^y — 2) * 2^(x — y). All that's left is to multiply the answers for every component of the graph.
Hope I helped.
Edit:
Submission: http://codeforces.com/contest/711/submission/20253554
Complexity is O(n)
Wow! It was one of those problems where the difficult part is that you have to make important observations and the rest is easy.
How to solve D? My solution used strongly connected component. Got WA in testcase 4 -__-
Could you explain yours? I tried to find the cycles with some special properties of the problem within the designated time but can't find the solution :(
I solved A , B in 16 minutes and didn't solve C. It seems like it is very easy as a lot of people solved it. But how did you handle something like that ? (3 3 3)
(0 0 0)
(1 200 200)
(1 1 1)
(1 200 200)
With my approach it was so hard to be handled because after the putting the colors that will give me the minimum cost I start to change the current beauty to be beauty + 1 or beauty -1 in every step until I reach set == k.
But this case will require from me to change the beauty by 2.
dont really know what you mean by "set" , but it can be solved by dynamic programming .
I thought about solving it with DP , but the problem was that I need to save which colors I have used so Far which cannot be saved as it will be 2 ^ (colors)
You can use each color multiple times.
For an index i, you only need to know what color was on i-1 index. So you could do dp with (n, no of segments, lastcolor) as states. You can choose any of noofcolors for index i if it is not colored.
So complexity: O(n*segments*color*color)
I just hope it don't give tle if there are no prunings done :|
Thank you very much , I understood something wrongly :)
You only need to store the color of the last element to know if you increase the number of groups or not.
Couldn't submit D because the servers were slow during the last 60 seconds ;_;
*Reads Problem E
*Notices a way to calculate large factorial is needed
*Ready to rant for requiring knowledge about an algorithm that I probably won't need it again.
*Notices that since MOD is only 1e6+3 so things could be simplified at the last minutes
*QWERTYUIOPLKJHGFDSAZXCVBNM obviously didn't coded quick enough and fail
Keep on observing till the last moment guys...
This is a pretty decent problem set anyways, I'm lovin it. =]
What was pretest 7 at D?
I tried to hack this 20246021 twice, as it uses
intbut he gives the correct output and no overflow happened!!could anyone explain why that happened?!
Your hack is wrong, I guess. Operations on 32 bit integers normally wrap around. Can you share your hack with us?
the 1st hack the 2nd hack
what do you mean by "Operations on 32 bit integers normally wrap around", could you explain that?
Take a look at this. Normally the result of addition, subtraction and multiplication on ints will still be correct modulo 232. And if the final solution is less than 231, the calculated value will be correct.
The problem with the second code is that the compiler is able to deduce that the loop will result in undefined behavior, so the compiler can basically do whatever it wants. In the first code, the compiler cannot deduce anything (because of user input) and no weird "optimizations" will occur. The machine code generated will simply use the ADD x86 instruction (or perhaps the MUL instruction), which on x86 produce the correct result modulo 232.
I warned everyone not to expect such crazy undefined behavior (for example when hacking solutions) but I got booed off
10
0 536870913 536870913 536870913 536870913 536870913 536870913 536870913 536870913 1
536870913 1 536870913 536870913 536870913 536870913 536870913 536870913 1 536870913
536870913 536870913 1 536870913 536870913 536870913 536870913 1 536870913 536870913
536870913 536870913 536870913 1 536870913 536870913 1 536870913 536870913 536870913
536870913 536870913 536870913 536870913 1 1 536870913 536870913 536870913 536870913
536870913 536870913 536870913 536870913 1 1 536870913 536870913 536870913 536870913
536870913 536870913 536870913 1 536870913 536870913 1 536870913 536870913 536870913
536870913 536870913 1 536870913 536870913 536870913 536870913 1 536870913 536870913
536870913 1 536870913 536870913 536870913 536870913 536870913 536870913 1 536870913
1 536870913 536870913 536870913 536870913 536870913 536870913 536870913 536870913 1
This is the case I found.
Would it be possible to get test case #117 for this problem? My solution for some reason did not pass it :(submission/20233549
I figured out the solution for problem D. Unluckily couldn't complete the code on time.
It is easy using DFS to find the number of edges that form the circle, let's name it cEdge.
Notice that if we choose the sets that contain the circle edges, after flipping, the circle remains.
So the answer = Number_of_all_subset — Number_of_subset_doesn't_contain_all_circle_edge = Pow(2,n) — 2*Pow(2, n — cEdge).
It this solution were right, I would be a little bit sad. Cause this is the first time I was this close to problem D.
You're correct, but note that you can have multiple weakly connected components and thus multiple circles:
Thanks. Found my bug.
It's right, but you need to do this not once, but for every connected component of the graph, and multiply these answers.
Please help me with the second question (Div. 2) and tell me what I did wrong? http://ideone.com/6HDQwQ
your solution gives -1 in : 1 0
Check:
3
3 3 3
3 0 3
3 3 3
answer is 3, you are printing -1
Wasted a lot of time on B and C, I think I could have solved D if I was a little faster :(
Auto comment: topic has been updated by zscoder (previous revision, new revision, compare).
Almost everyone has implemented a O(n^4) dp for problem C,I just hope it doesn't pass else it would be very unfair..how could 10^8 iterations pass...there are many problems on codeforces where a similar complexity has given TLE.
It's a Div2C for a reason man.
I can show a variety of Div-2C problems where such a complexity has given a TLE, MAN!!!
Calm down. I mean it is not meant to be extremely challenging.
Sorry if you feel that you are offended by my previous comment.
Send me problems where there is no high constant factor, and 10^8 fails on CF servers.
(No sarcasm intended). 10^8 just always pass.
TLE: 2 seconds. Also codeforces servers are pretty fast + almost no constant factor.
The only thing i worry is all operations are on long long int though
usually you can pass 10^8 iterations! you can even 10^8 * 5 of them! but I think there is a O(n^3) dp!
There is indeed an O(nmk) solution.
Yes, the inner loop iterates on colors. When you want to break the previous group and start the new one, you need to compute the two minimum costs over all possible colors of the previous group. And then iterate again on possible colors of new group and use one of the two minimum costs.
That is, you make two consequent loops instead of two nested.
...and I didn't have the balls to do the extra work, and I still failed regardless of the optimization.
Didn't actually try O(n^4). I thought it might blow up. So I tried for MORE THAN AN HOUR to bring the complexity down to O(n^3). (Using subtle techniques. Thus difficult to debug.) Consequently, I didn't have time for Problem D and E.
Can anyone explain C ?
Use a dp array
dp[tree][color][set_count]
Just handle the transfer between states carefully and you are set. (Note that the constraints are VERY small)
Can it run in O(1e8) ? I used 4 for loop. Hope it'll pass
Yes, it's fast for cf
normally what's the limit?
It's about 1e9/s. Usually TL won't be that tight since there are constant factors so consider 1e8/s.
I remember, when i can't hack solution with 1e9 operations!
That is true — "1e9" takes here around 1s (anyway it depends on complexity of operations)
Some simple iteration + summing would do that, anyway I doubt 1e9 load/store operation would be that successful.
Anyway 1e8 shall be OK with much complex operation (especially considering it might be considerably reduced by a constant)
Have nice day ^_^
Thanks, you too!
How can we know in general the number of iterations we can do ? For instance 1GHz means how many iterations ? Thanks :)
Do you know asymptotic(o())? So the number of iterations is the max possible asimptotic! As example, if n=1000 and o(n^2) then number of iterations near 1000000
If you mean time complexity yes I know. I was just asking how can we know in general how many iterations we could do.
Because here I had the solution for C in O(nkm^2) but I thought that I could do only 10^6 operations so I didn't even try to submit it
Here you can make above 2e9 primitive operations!
Thanks.
So what is a primitive operation ?
For instance addition, comparison,.. are worth how many primitive operations ?
=,+=,-=,*=,&,|,^,-,+,*,<<,>>,all comparison! I think it's all
Thanks !
You're welcome!
http://codeforces.com/contest/711/submission/20254708 Some one please tell me why this timed out ?
Good day to you,
it became "stuck" in your "do-while" cycle
Try following input
Good Luck ~ Have nice day
Я видимо один в B проявил фантазию и написал:
Rant: Hate it when forgot to uncomment a line that i commented out during debugging
But atleast it shows up in pretests xD and i could fix it :D
C was the first DP problem that I've solved during the contest thank you zscoder
self-confident level is rising.
Same here :D
Finally, I am going to be blue! :D
Problem B was so tricky
Pain is solving 4 problems and then getting "WA on 105" _/_
Не, ну я так не играю. Полчаса думал, как div2::C за куб решать, а в итоге и за 4 степень у всех зашло :(
Auto comment: topic has been updated by zscoder (previous revision, new revision, compare).
Can someone tell why did I get WA on 105.
http://codeforces.com/contest/711/submission/20244876
Its not clear from the test case what's wrong.
Not sure if that's the reason.
But here you call answer by reference, but you don't save it in the memo table in the first if condition. I think this should cause TLE and not WA though.
Yups I saw that. But WA isn't the outcome of it.
It looks like your submission is being re-judged ? It's re-running test 1 again.
Edit : It is accepted. I guess that makes you x100 happier now. Congrats!
Rejudged. Congrats! Ratings will be adjusted tonight.
Thanks. I almost cried seeing your comment.
What was the reason behind it Mike?
Can someone tell me what's wrong with my code? 20239552
You are doing a[x][y]=(r[(x+1)%n]-r[x]); what if 0 is in last row. r[x + 1] = 0 in that case.
vector< long int> r(n),c(n);should bevector< long long int> r(n),c(n);long int d1=0,d2=0,s=0;should belong long int d1=0,d2=0,s=0;Those sums can reach 500*10^9=5*10^11 which overflows 32-bit integer. UPD:
a[x][y]=(r[(x+1)%n]-r[x]);t=a[x][y]also causes overflow.Change it to
t=(r[(x+1)%n]-r[x]);Yes!!!! Specialist finally...next target :- Expert
O(n*k*m^2) in C! Really? 10^8? I didn't believe that it will pass all the tests and wrote something strange... Now I don't understand how my code passed pretests. Anyway, problems were very nice. Thank you
10^8 with simple operations can pass with only 1s
they gave you 2 seconds
anyway, if they want you to solve it in o(n^3) complexity then they would give 500 for n and just 1 second
I didn't know this before. It is usual for me, that test system can't pass more than 10^7 operations, so it was a good lesson :-)
I like the problem c,my dp is weak.i didn't solve it in contest,the problem c help me improve my mind,and the time is really really nice, thanks a lot
Hi.
This is about Problem B. I'm stuck at the test 93, and the test data is:
3
1 15 5
11 7 3
9 0 13
The correct answer is 1. However I think the answer should be -1.
Could anybody explain this for me?
Thx.
Nope.
Sum across second diagonal = 21
Sum in last row = 23
ans = abs(stdSumI — tSumI);
Wow...Sorry...I submit the wrong file after the contest...
The correct answer is -1. As can be seen in 20259409
Wow...Sorry...I submit the wrong file after the contest...
Problem C I though n*k*m^2 couldn't pass so I didn't do the solution. New lesson of analyzing bigO notation
I have a tendency of writing recursive solutions for DP problems. Will that be cause any problem in near future? Here is my accepted solution for DIV 2C (Complexity O(NKM2)). Can anyone help how to modify the same recursive solution so that complexity is reduced to O(NKM).
I have been told that it is always better to have an iterative code because it is easier to make sure you don't compute the same thing twice and you can have stack overflow with a recursive function. But I am no expert if someone knows it better ...
Good day to you!
I think it is (in MOST cases) up to you [what fits you better].
The advantages of "iterative" method are, that is is faster (by a constant — not that much but it is SOMETHING).
The "stack problem" is usually on, only if it is "1D" Dynamic Programming with N greater than 10^5 — anyway it can be prevented by executing DP a few times (you can execute the recursion with 10^5,2*10^5,3*10^5...etc in a loop, so there won't be more than 10^5 depth {or you can do this with custom depth — it doesn't cost any asymptotic complexity :) })
The same thing will never be computed twice (in any of the methods), anyway a "thing" might be asked more than once in recursive form (anyway as it is computed it ends in O(1) )
I (personally) prefer recursive method over iterative [it is easier for me to see the solution] — but as I said, it is personal matter.
An advantage of recursive DP is, that it is more easy to do a DP, in which the whole "state-space" doesn't fit into array, but you will use only "part" of it [with assist of "map"]. Also it is more easier, whenever the parents are somehow "variable" — not fixed :)
So the asymptotic complexity of both methods is same, and most of the things can be (somehow) converted to other method to make it working — so unless you are (for a reason) hunting every "ms", then it is only matter of personal preferences!
Good Luck & Have Nice Day :)
nice
Is there a bug in the contest ?!
Rating changes are removed !! zscoder MikeMirzayanov
UPD : The bug is fixed now.
My rating changes are returned. :) You can try to refresh the pages.
did the round become unrated ?! or is it just a bug ?
No Man Sorry
11 days till the next contest !:/
Great, now at least my exams will be over :D
and it collides with icpc first phase in south america :(
it's really frustrating that next contest is 10 days away.