vovuh's blog

Educational Codeforces Round 43 Editorial
By vovuh, history, 7 years ago, translation, In English

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
Solution (adedalic)
  • Vote: I like it
  • +27
  • Vote: I do not like it

Comments Comments (30)
| Write comment?
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.net/contest/976/submission/37770261

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

976D — Degree Set ,Graph for some (d1, d2, ..., dk) need to be sorted?

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +17 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      problem B

      can You please explain why we don't consider the case, when we do -1 to k, by decreasing height of our final answer?

      → Reply
      • »
        »
        »
        »
        7 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

        → Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
»
7 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Is anyone getting WA on test case 10 of E well played :| http://codeforces.net/contest/976/submission/37842203 here is my submission

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Same here: http://codeforces.net/contest/976/submission/37768647

    → Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How is solution for E nlogn? If we precalc powers of two it is O(n) isnt it?

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    You need to sort your array complexity of sorting — nlogn.

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Wow...wrote same solution after contest but now I forgot you need to sort hahaha

      → Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Changed >= to > om sort, and from Runtime error in test 84 got accepted.. Can someone explain why?

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can you please add a link to this editorial that is accessible from the contest? I cannot access the editorial from here.

→ Reply
»
7 years ago, # |
← Rev. 8   Vote: I like it 0 Vote: I do not like it

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
→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Degree of vertex 5 in your graph is 1 whereas the given degree set is {2, 3, 4}

    → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem F, why is the complexity O((n + m)2) ?

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

how to calculate dinic's complexity in problem F?why not n*n*m?

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

ME:making 100 of test cases for B problem codeforces: a single formula for all the cases ME: pikachu face INNER ME: crying

→ Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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)$$$. awoo Could you please help me with it?

→ Reply