Vovuh's blog

By Vovuh, history, 18 months ago, translation, , 976A - Minimum Binary Number

Editorial
Solution (Vovuh)

976B - Lara Croft and the New Game

Editorial
Solution (PikMike)

976C - Nested Segments

Editorial
Solution (PikMike)

976D - Degree Set

Editorial
Solution (PikMike)

976E - Well played!

Editorial
Solution (Ajosteen)

976F - Minimal k-covering

Editorial   Comments (31)
 » An nlogn solution itself gave tle for me in C.nested segments question using c++ default sort function, is there any one like this.http://codeforces.com/contest/976/submission/37770261
•  » » It is your cmpr function.
•  » » » but exactly why it created problem??
•  » » » » it can't make rgt in increasing order
•  » » I am confused too.. what's the problem here? :/ I have submitted very much the same solution as yours and I have got Correct Answer!http://codeforces.com/contest/976/submission/37790630
•  » » » See this
•  » » Never use equal sign in compare function
•  » » 18 months ago, # ^ | ← Rev. 2 →   you must use <,> operator with compare function,not <=,>=. because it can occur cycle in stl sorting.
•  » » When in doubt, read language specifications.Here is the documentation for sort. You can see that the 3rd argument needs to define a strict weak ordering. You can read about the mathematical concept, or you can go directly to the cpprefence of Compare.
 » 976D — Degree Set ,Graph for some (d1, d2, ..., dk) need to be sorted?
•  » » What do you mean by "sorted"? My checker takes the list of edges you output and calculates the degree set to compare it with the given one.
•  » » » problem Bcan You please explain why we don't consider the case, when we do -1 to k, by decreasing height of our final answer?
•  » » » » We transition from the number of steps Lara made to the number of cells she visited. You can see that she visits (m - 1) cells of the bottom row, then (m - 1) cells of the row above it and so on. And the formula tells you which one of these cells was the (k - n)-th.
 » Alternative solution for F: For a fixed degree d connect a new source vertex s with each vertex of U with capacity ∞ and demand d, and connect every vertex of V with capacity ∞ and demand d to a new sink vertex t. And then find the minimal flow as described in the e-maxx-eng article Flow with demands (add two more vertices to get rid of the demands, and do a binary search on the minimal flow value).This has a worse complexity than the editorial solution (due to the binary search and a slightly bigger network), but my implementation 37840246 still runs in under 1 second using Edmond-Karp.
 » Is anyone getting WA on test case 10 of E well played :| http://codeforces.com/contest/976/submission/37842203 here is my submission
•  » »
•  » » I getted too, you are wrong because you are trying to maximize hp[i] * 2^a — dmg[i], but its not correct. For example you have got hp[i] * 2^a — dmg[i] > hp[j] * 2^a — dmg[j], but dmg[i] + hp[j] * 2^a — dmg[j] can be larger then dmg[j] + hp[i] * 2^a — dmg[i] and you should use your a spells on j but not i.
•  » » » yeah so that is why I sorted (passed compare function sorted by first increasing hp[i] * 2^a the dec dmg[i] ?
 » How is solution for E nlogn? If we precalc powers of two it is O(n) isnt it?
•  » » You need to sort your array complexity of sorting — nlogn.
•  » » » Wow...wrote same solution after contest but now I forgot you need to sort hahaha
 » Changed >= to > om sort, and from Runtime error in test 84 got accepted.. Can someone explain why?
•  » » 18 months ago, # ^ | ← Rev. 2 →
 » Can you please add a link to this editorial that is accessible from the contest? I cannot access the editorial from here.
•  » » Done
 » first time implemented IdentityHashMap.
 » 17 months ago, # | ← Rev. 8 →   Why is this wrong for question no. D? Input 3 2 3 4 Participant's output 6 1 2 1 3 1 4 1 5 2 3 2 4
•  » » Degree of vertex 5 in your graph is 1 whereas the given degree set is {2, 3, 4}
 » In problem F, why is the complexity O((n + m)2) ?
 » how to calculate dinic's complexity in problem F?why not n*n*m?
 » ME:making 100 of test cases for B problem codeforces: a single formula for all the cases ME: pikachu face INNER ME: crying