Если вы используете C++, пожалуйста, выберите в качестве компилятора при отправке решения: C++14 (GCC 6-32) или C++17 (GCC 7-32). ×

Блог пользователя BledDest

Автор BledDest, история, 4 года назад, перевод, По-русски
Div2A
Div2B/Div1A
Div2C
Div2D/Div1B
Div2E/Div1C
Div2F/Div1D
Div1E
Div1F
Разбор задач Технокубок 2020 - Финал
  • Проголосовать: нравится
  • +54
  • Проголосовать: не нравится

»
4 года назад, # |
  Проголосовать: нравится -32 Проголосовать: не нравится

Nice editorial :)

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

so unlucky with problem div.2 E ;( thanks for editorials. can someone check my code and find my bug? i was debuging for 2 hours and found nothing. my code

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +2 Проголосовать: не нравится

    The test on which your code is failing is small in size(n=m=p=10) so you can use it as a counter-testcase and debug..

»
4 года назад, # |
  Проголосовать: нравится -9 Проголосовать: не нравится

I have a problem with 1321C - Remove Adjacent. I don't really understand how the answer to the first test case is $$$4$$$

According to the problem, $$$ 1 \leq i \leq |s| $$$
Let s = $$$bacabcab$$$

$$$1$$$) We remove $$$s_2$$$ = $$$a$$$ and we get $$$s$$$ = $$$bcabcab$$$
$$$2$$$) We remove $$$s_2$$$ = $$$c$$$ and we get $$$s$$$ = $$$babcab$$$
$$$3$$$) We remove $$$s_1$$$ = $$$b$$$ and we get $$$s$$$ = $$$abcab$$$
$$$4$$$) We remove $$$s_3$$$ = $$$c$$$ and we get $$$s$$$ = $$$abab$$$
$$$5$$$) We remove $$$s_3$$$ = $$$a$$$ and we get $$$s$$$ = $$$abb$$$
$$$6$$$) We remove $$$s_2$$$ = $$$b$$$ and we get $$$s$$$ = $$$ab$$$
$$$7$$$) We remove $$$s_2$$$ = $$$b$$$ and we get $$$s$$$ = $$$a$$$

Which cannot be shortened further. So we removed a total of $$$7$$$ characters. Shouldn't that be the optimal answer?

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

    'a' can never be removed as it has no previous letter (see problem statement)

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    I think you misunderstood the meaning of this problem. You should read it again carefully.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    We can't remove 'a'.it's mentioned in the problem.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Actually i got very confused so according to question b is previous element of a, or y is previous element of z,but a is not previous element of d.I wasted a lot of time in this

»
4 года назад, # |
Rev. 6   Проголосовать: нравится +4 Проголосовать: не нравится

I'm confused by the editorial for Div2F/Div1D. When I tried to implement it I seem to always get WA buried somewhere in test case 6, and I don't really know how it handles the case of odd number of consecutive ones, or the case:

$$$11010 \rightarrow 01110 \rightarrow 01011$$$

Edit: Oh, I think you meant deleting the $$$1$$$ s from the string altogether. I turned out to be converting them into $$$0$$$ s instead, which is clearly wrong

Edit 2: And now I fail at test 10. This is tough.

Edit 3: Got it. Had to add special handling for "empty" strings.

»
4 года назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

I don't understand this explanation for Div2C.

Why is it always true? Suppose we remove the maximum letter i that can be used to remove some other letter j (it is obvious that si+1=sj in such case). If there are no other letters between si and sj then si is not the maximum letter, so we got contradiction with our algorithm. Now suppose that we can remove all letters between si and sj. Then we first choose sj and only after that si by our algorithm. Consider the last case — there is at least one letter sk between si and sj. Because we cannot remove sk then there are only two cases: sk>sj+1 or sk+1<si. Then we cannot use si to remove sj at all.

Can somebody explain it please?

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +7 Проголосовать: не нравится

    For me that just proofs that for the lexicographically last letter (ie 'z') there is no letter after that one. Then it states that if such one is removed, all other possible removals still exist. So we can remove letters in reverse lexicographically order. Kind of induction.

»
4 года назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

Please, add author solutions too.

»
4 года назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

Hey, is there anyone here knows other problems that need to use the tree compression trick like D1E? I learned it before but I forgot :(

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can someone explain div1D please? I just can't get the point of what the tutorial is saying...

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    In short, the tuition is like this. Since you have the transformation is to change "011" to "110" and vice versa, the parity of the number of "1" between any two consecutive "0"s remains. Therefore, if there is any "11" in our original string, the fact that you delete it would not change anything. Just delete all "11" in the original string, and you obtain a shorter new string. To answer queries, just pick the substrings of the new string that correspond to the substrings in the original, and compare if they are the same.

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

In div2E as per my understanding we need to implement segment tree to support max query over cumulative sum. Am I right?

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

In problem div2 D how is the minimum rebuild in example 3 0? why is not 1?

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    If you make the transposed graph (basically all edges in opposite direction) and calculate the shortest distance from the last node, you'll see that the given path is indeed the shortest path from 8 to 1. Therefore, if I take this path on node 8, I can continue with this. Question asked rebuilds not builds so first build is excluded.

»
4 года назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Can anyone help me find which test case my code for DIV2-B fails.

  • »
    »
    4 года назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    You have an error in overflowing values. The maximum value for n is 2*10^5, for each number 4*10^5. Multiplying these numbers we get 8*10^10. While int can store data up to 2*10^9. Replace the int with long long. P.S. And in general, I would recommend doing this task the way it is editorial, because on big tests you will get TL.

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I couldn't understand the editorial of Div2C .It will be great if someone explain it to me. Moreover,I cannot figure out which case i am missing.here is my code:https://codeforces.com/contest/1321/submission/72240578

  • »
    »
    4 года назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    It is something as follow: We first try to remove occurrences of 'z'. Now if there any 'z' remaining that can't be removed. Then we remove occurrences of 'y' wherever possible. and so on.

    And here in each pass you can scan entire array. As there are only about 100 characters.

    Now, you may ask why we are not starting with 'a' then 'b' then 'c' and so on...?

    Because suppose you have following string — 'cbca'. Then if we had tried to remove 'b' then it would not be remove after it's pass gets over. But after removing 'c' string becomes 'ba'. So, we find out that we can also remove 'b'.

    And if you think a little bit than you will see that in our approach of removing characters in reverse alphabetical order once we find that we can't remove given character then we will never be able to remove that character in future.

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Div2C also has a $$$O(n^3)$$$ dp solution https://codeforces.com/contest/1321/submission/74736147

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    can you explain it's states?

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      $$$dp[i][j][c]$$$ is whether we can use some sequence of moves to reduce the substring $$$s[i..j]$$$ to the character $$$c$$$ or not. After that $$$dp2[i]$$$ is the minumum length we can obtain on the prefix after some sequence of moves

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Is it necessary to use lazy propagation in div1 C? Thanks

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Apologies, for div2D, this is failing on test 7 and I can't figure out what's up, could anyone look through and maybe see the logic? My # of possible cases is more than that of the test's.

https://codeforces.com/contest/1320/submission/76050423

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can't figure out what's wrong:

https://codeforces.com/contest/1321/submission/77013730

Basically, I compute shortest paths in the transposed graph in a table dist. dist[X] is the shortest path length from node X to node P[K].

Then, looping I = 2 to K (i.e 2nd to last node):

I check if p[I - 1] to p[I] is an edge in some shortest path from P[I - 1] to the last node (i.e. P[K]. I check this by checking dist[P[I]] == dist[P[I - 1]] - 1.

  • If the check fails, then both max and min increase by 1, because in both cases, we need to rebuild because we transitioned to a non shortest-path edge.

  • If the check succeeds, then I check if how many outgoing edges does P[I - 1] have that's part of some shortest path:

    • if there's more than one, then I increment max only because the worst case is when the navigation system suggested a different path.
    • if there's only one, then max and min doesn't change.

Maybe my bfs is wrong

  • »
    »
    4 года назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    Lol yep, my bfs is wrong.

    In my implementation, it's possible that's nodes can be pushed twice in the queue. This should not be the case when counting paths. I got AC after fixing this.

»
4 года назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

Codeforces Round 625 div2 D wa4。 I can not make sense. https://codeforces.com/contest/1321/submission/82265166

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can anyone please explain me the editorial of div2E/div1C?

  • »
    »
    4 года назад, # ^ |
    Rev. 2   Проголосовать: нравится +12 Проголосовать: не нравится

    Let's represent all the monsters as the points at the coordinate plane: a monster with $$$x$$$ toughness, $$$y$$$ power, and $$$z$$$ coins is represented by the point $$$(x,y)$$$ with value $$$z$$$. For each pair of a sword with power $$$x_0$$$ and a shield with toughness $$$y_0$$$, the result is the sum of values over the points which belong to the rectangle $$$0 \leqslant x < x_0, 0 \leqslant y < y_0$$$ minus their costs.
    Let's now apply the scanline technique: we will process the events of two types: a new monster and a new sword. Let's build a segment tree over the (sorted by toughness) list of shields and define the current set of monsters (initially empty) as $$$S$$$. For each shield with toughness $$$y_0$$$ and cost $$$c$$$, a leaf value in the segment tree stores

    $$$-c+\sum\limits_{\substack{m \in S \\ y(m) < y_0}} z(m)$$$

    Let's sort an array of events by $$$x$$$. If some sword has the same power as some monster's toughness, then the sword is processed before. For each event in the sorted order:
    - If it's a monster with power $$$y$$$ and value $$$z$$$, then for each shield with the higher toughness add $$$z$$$, which means adding on some suffix segment of the segment tree. That monster is added to $$$S$$$;
    - If it's a sword with power $$$y$$$, then you need to find the shield with the biggest value in the segment tree. The final answer is the biggest value among the values of these pairs.

»
4 года назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

can anyone tell me why i am getting TLE in div1-A. Here's my submission 87744808

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

DP solution for journey planning is giving TLE. O(n^2) isn't fast enough even for 2 second time limit?

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

1320D — Reachable Strings can be solved in O(n) with hashes without a segment tree. I have put Submission for reference.

»
7 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

can anyone please explain for problem A how ceil[(y+1)/x] can be answer.x can be any integer right adding 1 to y will necessarily not increase the answer by 1 right . BledDest

»
5 месяцев назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

can anyone help me how to dij in div1E ??