vovuh's blog

By vovuh, history, 21 month(s) 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

• +27

 » 21 month(s) ago, # |   0 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
•  » » 21 month(s) ago, # ^ |   +6 It is your cmpr function.
•  » » » 21 month(s) ago, # ^ |   0 but exactly why it created problem??
•  » » » » 21 month(s) ago, # ^ |   0 it can't make rgt in increasing order
•  » » 21 month(s) ago, # ^ |   0 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
•  » » » 21 month(s) ago, # ^ |   0 See this
•  » » 21 month(s) ago, # ^ |   +8 Never use equal sign in compare function
•  » » 21 month(s) ago, # ^ | ← Rev. 2 →   +13 you must use <,> operator with compare function,not <=,>=. because it can occur cycle in stl sorting.
•  » » 21 month(s) ago, # ^ |   0 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.
 » 21 month(s) ago, # |   0 976D — Degree Set ,Graph for some (d1, d2, ..., dk) need to be sorted?
•  » » 21 month(s) ago, # ^ |   +17 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.
•  » » » 21 month(s) ago, # ^ |   0 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?
•  » » » » 21 month(s) ago, # ^ |   0 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.
 » 21 month(s) ago, # |   0 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.
 » 21 month(s) ago, # |   +1 Is anyone getting WA on test case 10 of E well played :| http://codeforces.com/contest/976/submission/37842203 here is my submission
•  » » 21 month(s) ago, # ^ |   0
•  » » 21 month(s) ago, # ^ |   0 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.
•  » » » 21 month(s) ago, # ^ |   0 yeah so that is why I sorted (passed compare function sorted by first increasing hp[i] * 2^a the dec dmg[i] ?
 » 21 month(s) ago, # |   0 How is solution for E nlogn? If we precalc powers of two it is O(n) isnt it?
•  » » 21 month(s) ago, # ^ |   +8 You need to sort your array complexity of sorting — nlogn.
•  » » » 21 month(s) ago, # ^ |   0 Wow...wrote same solution after contest but now I forgot you need to sort hahaha
 » 21 month(s) ago, # |   0 Changed >= to > om sort, and from Runtime error in test 84 got accepted.. Can someone explain why?
•  » » 21 month(s) ago, # ^ | ← Rev. 2 →   +1
 » 21 month(s) ago, # |   0 Can you please add a link to this editorial that is accessible from the contest? I cannot access the editorial from here.
•  » » 21 month(s) ago, # ^ |   0 Done
 » 20 months ago, # |   0 first time implemented IdentityHashMap.
 » 20 months ago, # | ← Rev. 8 →   0 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 
•  » » 20 months ago, # ^ |   0 Degree of vertex 5 in your graph is 1 whereas the given degree set is {2, 3, 4}
 » 16 months ago, # |   0 In problem F, why is the complexity O((n + m)2) ?
 » 7 months ago, # |   0 how to calculate dinic's complexity in problem F?why not n*n*m?
 » 5 months ago, # |   0 ME:making 100 of test cases for B problem codeforces: a single formula for all the cases ME: pikachu face INNER ME: crying
 » 2 months ago, # | ← Rev. 2 →   0 I do not understand the correctness of proof of problem D. How do we know that there is a solution for the sub-problem $(d_2 - d_1, d_3 - d_1, \cdots, d_{k - 1} - d_1)$. PikMike Could you please help me with it?