dcordb's blog

Codeforces Round #659 Editorial
By dcordb, 4 years ago, In English

We (the setters) hope you liked the problems. Here is the editorial:

Tutorial is loading...
C++ solution
Python solution

Problem idea: dcordb

Solution idea: dcordb and Devil

Tutorial is loading...
C++ solution

Problem idea: Devil

Solution idea: Devil

Tutorial is loading...
C++ solution

Problem idea: Devil

Solution idea: Devil

Tutorial is loading...
C++ solution

Problem idea: Devil

Solution idea: mnaeraxr and Devil

Tutorial is loading...
C++ solution
Python solution

Problem idea: Devil

Solution idea: Devil and dcordb

Tutorial is loading...
C++ solution

Problem idea: Devil

Solution idea: mnaeraxr

Tutorial is loading...
C++ solution

Problem idea: gilcu3

Solution idea: gilcu3 and mnaeraxr

Tutorial is loading...
C++ solution

Problem idea: Devil

Solution idea: Devil and antontrygubO_o

Tutorial is loading...
C++ solution

Problem idea: mnaeraxr

Solution idea: mnaeraxr and Devil

  • Vote: I like it
  • +125
  • Vote: I do not like it

Comments Comments (116)
| Write comment?
»
4 years ago, # |
← Rev. 2   Vote: I like it +2 Vote: I do not like it

Where are the time complexities?

I usually find understanding a solution easier when the time complexity is indicated with the solution.

Amazing contest, nonetheless.

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

Lost the entire interest after seeing problem statement of B1 :(

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

    That's why people moved to C

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

      C and D protected my life

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

        seriously dude, you didn't even participate.

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

          It's Beyond Science

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

          Maybe he/she uses a fake account lol

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

            I don't get the point of making many accounts. why would you make an alt account just to post bullshit?

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

          seriously dude, he didn't even tell you.

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

In Div1D, the time complexity is $$$O(nm)$$$, so the limits could have been higher as I think of it.

Was it intentional (so that one would think of it more as a $$$O(n^3)$$$, flow-like problem, for example)? Or possibly a change of mind -- maybe wrote a cubic solution, found the square one after?

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

    If you push the limits to as high as possible that will fit within TL, you may be unnecessarily giving away info to the contestants. In this case making it so that $$$O(nm)$$$ is the only complexity that fits within TL tells you that the algorithm must be of that complexity. Imo it makes sense to leave it this small so it remains ambiguous (and still doesn't let any inefficient solutions pass).

    → Reply
»
4 years ago, # |
  Vote: I like it -18 Vote: I do not like it

Long statements + weak pretests

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it -51 Vote: I do not like it

    Problem setter thinks he is very smart but he is a kid, don't know who allowed him to set problems.

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

      The contest was good and I liked it even tho I couldnt solve any problem, I enjoyed the 2 hours. Speak for yourself.

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

        It's not about solving problems, just look at the description & difficulty of the problems and points assigned to that problems, Totally unfair. C-1750, B-500/700.

        → Reply
»
4 years ago, # |
  Vote: I like it -9 Vote: I do not like it

Devil I think you made undirected graph in solution of div2C :)

→ Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    graph will be undirected only , since we need to find size of the connected component , thus we need to visit all the nodes (to mark them and thus to find size of the connected component) . It's "connected" not "strongly connected" in editorial .

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

lost interest in this round due to B problem statement

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

Graph solution for problem div2 C (div1 A) is beautiful . Can some tell other approach without using graphs.

→ Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 2   Vote: I like it +14 Vote: I do not like it

    If any character in $$$A$$$ is greater than $$$B$$$ at a particular index then it is not possible to transform $$$A$$$ to $$$B$$$.

    $$$Rule$$$ : Do not touch the indices in which $$$A$$$ and $$$B$$$ match.

    And now follow the following process

    First we look at the indices with contain $$$"a"$$$ in the string $$$A$$$ and look at the same indices in $$$B$$$ and let minimum among those indices in $$$B$$$ be $$$X$$$. Now replace characters in $$$A$$$ in those indices to $$$X$$$. Now one operation is performed. Similarly repeat the process to $$$"b"$$$, $$$"c"$$$ $$$.....$$$ $$$"t"$$$

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

    Yes,I used set to solve that problem --> Link

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

    It is obvious that, if the first string has a character with higher value than the second string in at least one position, there is no solution.

    Now for the non trivial case: If we need to transform at least one instance of character x into a higher character y, then there is no harm in transforming ALL instances of x into y (it is still going to be one move), as long as we consider the potential y characters in increasing order (otherwise we might leap over relevant characters and increase some instances of x too much). While there potentially is a benefit, i.e. reduction of the number of necessary moves in cases like the following example: for strings aab and bcc we need to transform a -> b, a -> c, b -> c, and when transforming both a's to b then both b's to c, we achieve the desired result without the need to spend an extra move for a -> c transformation. The potential x characters should be considered in increasing order too, to avoid making a move before it gains full potential accumulated from potentially transforming lower characters into x first.

    Fill a matrix M with 20 rows and 20 columns as follows M[x][y] = true, if at least on instance of the x-th character ultimately needs to be transformed into the y-th character, false otherwise. Only the half of the matrix strictly above the diagonal is of interest, because if M[x][y] = true for some x, y where x > y, then we are back at the trivial case, and if x = y, there is no transformation required.

    Now iterate over potential x-th characters in increasing order, for each iterate over potential y-th characters, where y > x. For the first encountered M[x][y] = true entry (if any), count plus one move, and iterate over the rest of the entries in the same row, i.e. over z-th characters for z > y. For each entry M[x][z] = true, make M[y][z] true, as this is simulating transforming all instances of the x-th characters into the y-th, while keeping track into what characters they need to be transformed ultimately.

    P.S. Really, this approach is not that far away from the graph solutions, since the matrix can be seen as an adjacency matrix of the graph. It is a matter of interpretation and I did not have a graph in mind when coming up with the solution.

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

    C++ std::priority_queue is also a nice way to solve this problem

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

dcordb can you please you spoiler to display editorial (blogs), it will be more convenient like previous editorials.

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

Solution of div1C only gives the answer but doesn't really explain how one might come up with that in the first place, so I'll try.

First observation is having lots of letters in the first string is bad for us, so we want to join letters as much as possible. That is, suppose the solution does operations A->B, followed by A->C. We could have changed all As to Bs in the first operation to do A->B, B->C instead. B->A followed by C->A can also be replaced by B->C, C->A.

From this, we might intuit that the solution consists of one very long chain in which we have a "snowball" collecting all original letters into the same letter.

If the graph has no cycles, then such a snowball can simply follow the topological sort of the DAG (this is div1A). If there are cycles, then some vertices will be visited more than once. If you know that a vertex is going to be visited more than once anyway, you might as well put it as the first and last vertices in the order, since this guarantees that vertex can reach/is reachable by all others.

What about the vertices you only visit once? Clearly there cannot be any cycles between them, so they are a DAG (and as we know any DAG can be solved with the topological sort). So the solution looks like: visit some set of vertices S, do topological sort on the rest, visit S again. To minimize the number of operations we want the DAG to be the maximum possible.

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

Question : C2 Koa and the Beach
Can someone explain why the below test case below should have "NO" as a answer:
20 26 32
31 27 14 7 2 23 22 21 19 27 31 12 23 31 0 11 28 20 31 30

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it +34 Vote: I do not like it

I don't like editorial of 1384B2 - Koa and the Beach (Hard Version) So I'll write my own. I think it should be easier.

Let s(p, t) is answer on question "is there way to reach position p at cycle of tide t?". I'll make numbering of tide cycle in following way [k, k-1, k-2..., 1, 0, 1, 2 ... k-1]. It will be much easier to understand later.

So, now obviously, if 0 is island, then s(0, t) is true for any t. Next, suppose some s(p, t) is true, then if we get this existing way to reach p at cycle time t and just standby there, eventually we can either drown or stay infinitely. Obviously, if we drown then it is because tide increased. This means that for all i up to some point x value of s(p, i) is also true, unless you can stand there forever. So either whole segment from i to x is true, or all s(p, t) is true for this p. Position p where you can stand forever lets call safe position similarly with editorial.

Now important part: we can drown only when tide increase, highest allowed tide is easy calculated. And that's why cycle of tide I defined in the way above, with increasing in the end. Because higher allowed tide — longer we can stay. And, this also means that cycle time with "bad" level of tide is in prefix and suffix of cycle. This all means that for any position p there is first (lowest) t for which s(p, t) is true. And, in this notation all possible cycle time for position p gives range from first time to the time when highest possible tide is reached during rise of tide. Thus, to solve the task we only need to find for each position p first t when s(p, t) is true.

Now, consider three cases:

  • if you stand on safe position p, to get earliest t in cycle for next position p+1 you should move at fall, so you move to next position at fall of tide and highest allowed tide.
  • if you stand on unsafe position p when tide is rising, you just need to move forward as soon as possible, because if now you can't move forward, then on next time you can't also move forward, but if you can right now — it's earliest moment in cycle you can reach next position.
  • if you stand on unsafe position p when tide is falling you just need to wait until you can move forward and not drown on next position p+1.

So, for each position we just update earliest t, and total time complexity is O(n). 87931302

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it -15 Vote: I do not like it

    Video Editorial of B1 and B2: Koa and the Beach

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

      I liked the way you explained it. Nice and clear. But I don't like the fact that this problem was kept at B.

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

    could you explain why test case 3: 4 3 4 0 2 4 3 has a solution(i.e Yes)?

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it 
      4 3 4
0 2 4 3

      On position 0 we can stay forever — it's island, so we should move on fall, so we move at t (cycle time) at 0 and arrive at t = 1 on position 1 because there will be 0+2 height which is less than 4. Also, at position 1 we can stay forever, so we should move at fall again. So, we will wait until t = 0 again and move at t = 0 and if we move then on next position we will have 2+2 which is alright, but we can't stay here forever because 2+3 > 4. This means that we now on falling tide and unsafe position. We need to move next as soon as possible. If we move now to position 2 we will have 4 + 1 height and drown, so we should wait once and after move we will have 4 + 0 height which is alright. Now, at position 2 we are in unsafe position and tide is rising, so we should move now (without any "if", because situation may only become worse). Now we move to position 4 and have height 3 + 1 which is alright. Similarly, on position 4 we are in unsafe position and tide is rising so we should move now, and successfully reach end. Each of this actions give earliest t for each positions, so earliest t array is: 0, 1, 3, 4, and corresponding tide: 3, 2, 0, 1.

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

Next time please try to make smaller readable problems. Appreciated your efforts.

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

The largest directed acyclic graph can be computed using dynamic programming in n*2^n.

I remember a nice CF blog on this, could anyone point it out.

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

DP solution to B1:87940952. dp[i][j]--> Can we be at location i at time j? So, if any of dp[n][j] is true, we can reach the island.

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

    i might be late, but can you just tell me how did you calculate the upper bound of second state of dp? i mean the time factor...

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

EDIT: Got it!

My Code is Exactly like Editorial's.

Can anyone Please tell me why is gives wrong for this simple case, ALTHOUGH it's giving correct output in my local Compiler.

Tese Case: 1

3

ddd

ddd

My Local Output: 0

Cf Compiler: 1

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

    You don't clear your global arrays after printing -1.

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

I found the following trick to solve Div2 B with simple implementation. The idea is like sliding window and updating the initial interval of $$$(-k, k)$$$ that corresponds to decreasing tide $$$(-k, 0)$$$ and increasing tide $$$(0, k)$$$. This way of set up simplified the implementation so much, but unfortunately, I came up with this at the end of the contest. Here's my solution

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

Kudos to testers and those who arranged the problems in order of difficulty.

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

Solution videos for people who prefer to have things explained visually are available here.

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

Can B1 use array to memory state?

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

How is my idea for Div1A different from the editorial?

→ Reply
»
4 years ago, # |
← Rev. 4   Vote: I like it +3 Vote: I do not like it

In Div2C.

For the testcase 1 4 aacb bcdd

The topological order is acbd But we can't select the each pair of consecutive nodes because c-->b is not possible.

Am i missing something?

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

    I think it's abcd.

    aacb -> bbcb -> bccc -> bcdd

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

    I don't know but gave you +1 for ma boi killua

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

Although the quality of problems is quite good, but the score distribute is not reasonable. Div2 B that cost me 1 hour time only values 500+750 score. Div2 C is quite easy, but values 1750. I solved 5 problems but get a lower rank than someone solved 4 problems because of this score distribute. Sad~

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

In the code of div1 E, the DP transition is 

dp[i] = ((dist[i] <= dist.back()) + get(0) + get(dist[i] + 1)) % mod;

I understand get(0) and get(dist[i]+1) are the two cases in the editorial, but what does (dist[i] <= dist.back()) mean ?

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

    Oh, I see. It seems that (dist[i] <= dist.back()) means let $$$w$$$ just end there !

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
      ← Rev. 2   Vote: I like it +8 Vote: I do not like it

      Yes it does that, it simply checks if string $$$s$$$ can end at $$$i$$$. For future references here is same solution that handles that part more clearly:

      Div1E C++ solution

      Here I removed zeroes at the end of $$$s$$$ (and multiply by this, plus $$$1$$$ to ans), and replaced that transition with an easier one to understand (it. checks if $$$s$$$ can end at $$$i$$$ with a $$$1$$$).

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

      Why w end there must meet this condition?

      I think i understood it, your solution is more clear.

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

I find that if s="0", the solution will RE because it visited nxt[dist[0]+1] (dist[0]+1=2) and the size of nxt is $$$2$$$ !

→ Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    Yes sorry, it will RE, it was an error modifying it to post it here, but model solution is correct.

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

In Div1E/Div2C, what is the motivation for: "and the answer is $$$2⋅n−|LDAG|−1$$$"?

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

Why the simple greedy solution isn't mentioned in editorial for Div2C?

→ Reply
»
4 years ago, # |
  Vote: I like it -13 Vote: I do not like it

If you are keeping python as a submission language then please do some homework and check the comparative time it's gonna take in python or else change codeforces to cppforces.

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

    Codeforces is already cppforces. Plenty of problems can't be solved using Python.

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

      Just tell me why can't be solved. Are there any logic that python doesn't support or recursion call stack that cannot be increased. It's all about time. You just have to increase the time limit for python in order to make python compatible for solving the same logic.

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
        ← Rev. 4   Vote: I like it +13 Vote: I do not like it

        You want to have all the benefits python offers and no drawbacks. Obviously this won't do. Python is slower and that's the price you pay for its flexibility and coding speed

        Also, learn to use pypy. I see that you used vanilla python, that's rarely a good idea in cp. Pypy is hardly ever not enough for the first d2 problems if you have a correct algorithm

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

        That's just the way things are currently, where C++ has a big advantage over other languages. I'm not saying that it's right or wrong, but until this changes you'll probably be better off switching to C++.

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

Case: x%4 == 3 if y%2=1 the first player takes one 1 and the game now is exactly the previous case with the first player as the second player. I think the author means the first player takes first 0 and then the game is exactly the previous case . Previous Case: x%4 == 3 && y%2 == 0 Or Maybe i am too naive to understand the Author's logic :)

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

Can anyone explain how we can solve Div2C using DSU?

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

IMO in Div.2 only problem C and maybe D had somewhat of a proper score allotted to it. Rest all should have had a higher score allotted to them. Especially B2.

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

For String Transformation 1, I am really struggling to understand the answer after the 2nd sentence. I would like to understand this graph solution, could anyone please explain it in more detail?

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

This is how I solved Div2B

let h be an array where h[i] = l - d[i]

Then divide h into segments [L, R] where

h[L] >= k

h[R] >= k

h[i] < k (L < i < R)

For each segment check if exist 2 indices i and j such that i + h[i] < j - h[j] then there is no solution. Otherwise, a solution exists

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it +11 Vote: I do not like it 
for mask in 1..2^n-1
   for u in mask:
      is_dag[mask] |= is_dag[mask & (1 « u)] && ((mask & reach[u]) == 0))

Should it be:

for mask in 1..2^n-1
   for u in mask:
      is_dag[mask] |= is_dag[mask ^ (1 « u)] && ((mask & reach[u]) == 0))
→ Reply
»
4 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

For DIV2C/DIV1 A

For this sample input

1

7 dgdfjjk

lhejkkl

We can transform in just 5 steps,but author's solution is showing 6.

Operations 3-e

2-h

4-j

1,5,6 — k

1,7 — l

am I missing something?

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

Can someone please explain me the graph solution of problem 3. I am not able to understand it from the editorial.

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

div 2 C seems to be a standard ques!! if yes then can you plz tell me more about this type of question!

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

For C1 my approach seems to be different from what the comments are mentioning. (*I also don't seem to have a proper proof for it but it seems to work intuitively and would be nice if someone wants to look into this*)

I took characters of string B and sorted them in the increasing order. (Let's call the smallest value of such a sorted sequence as SML)

My claim is that if we try to change the characters of string A whose character in the corresponding same position in B is same as SML or once such character is found then every occurence of the same character in A will be changed to SML and the number of such distinct characters which were changed to SML will be added to our final answer.

Now first turn is over SML will pick the next smallest element and will redo the above again.

Finally all characters in A will be changed to the ones in B and the answer will be minimum.

I used set of pairs to implement it.

If there are any counters to the above explanation they are most welcome. (Since I am not sure why my approach actually works besides few samples I checked with pen and paper)

https://codeforces.me/contest/1384/submission/88045399

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

In Div.1F, the time limit seems so tight after some very strong hack testcases were added, and it's so difficult to pass them.

By the way, can anyone tell me how to get max flows quickly.

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it +6 Vote: I do not like it

I have some questions on 1383B - GameGame : why we dont have to consider higher bits when we're processing the first bit that the number of ones is odd? (or : why we can turn these numbers into an array of $$$x$$$ ones and $$$y$$$ zeros? should we consider the influences of higher bits (though their number of ones is even) ?)

i'll appreciate it if you can explain these questions to me :)

→ Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 2   Vote: I like it +16 Vote: I do not like it

    If number of ones is even for any higher bits. Then irrespective of distribution, both players will have either odd or both players will have even number of bits . So both will end up having same value(because of same parity) for that bit. This is the explanation I gave to Myself .

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

    If the number of $$$1$$$ is even for a bit, then the final result could be only:

    1. Both two players take even count from it, they both get $$$0$$$ on that bit.
    2. Both two players take odd count from it, they both get $$$1$$$ on that bit.

    which will always make a tie on that bit. The order doesn't matter.

    It could be confusing, so you can have a simulation.

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

In div 1 E editorial, I don't understand this part:

"if the $$$(j+1)$$$-th character in $$$w$$$ is 0, and we have $$$k$$$ zeros after the last 1 in $$$w$$$ find the next block of $$$k+1$$$ zeros in $$$s$$$, (ie first $$$i'>i$$$ such that for each ($$$0\le k'<k$$$) $$$s_{i'-k'}=0$$$)"

Why do we look for a block of $$$k+1$$$ zeros if we only need $$$k$$$ zeros? Also, the part in the parenthesis contradicts this because there $$$0\le k'<k$$$ is an interval with only $$$k$$$ numbers in it. However, the model implementation uses get(dist[i]+1) which is also $$$k+1$$$. So which one is it and why?

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

    Oh that was a typo, as it says in editorial and as you can see in sample solution, if you have a block of $$$k$$$ zeros, and you want another $$$0$$$, you should search for first block of at least $$$k+1$$$ zeros.

    For example: $$$s = ...100\underline{0}100000$$$ you are on the underline (suppose $$$w = ...1000$$$) and you want another zero, for this you can merge $$$0001$$$ with some previous $$$1$$$ (remember we ensured that one always exists) and search for next block of at least $$$4$$$ zeros (the merge would look like $$$...10001|0000...$$$). In this way you would have $$$w = ...10000$$$.

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

      Thanks, I understand the greedy part now but am now having trouble understanding the DP. The editorial says

      "Let $$$dp(i)$$$ be the number of strings that we can obtain using the last $$$n-i$$$ characters from $$$s$$$"

      However, running the model code tells me the dp states used in it are not exactly the same. It gives the following values for these suffixes:

      s:  0 1 1 1 0 0
dp: 9 9 6 3 2 1

      Note that the actual number of things you can construct from 011100 is 18, not 9. It should be double the number of things you can construct from 11100 because you can choose whether or not to put the 0 at the beginning. Could you explain what the dp states in the solution actually represent? Thanks!

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

        Yes, the dp is well defined in each one, remember that at the end we use $$$dp(i)$$$ where $$$i$$$ is the position of the first one.

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

        If it helps, try thinking about it in this other way (this is how I first solved):

        Let $$$dp(i, c)$$$ be the number of strings we can obtain from last $$$n - i$$$ characters of $$$s$$$ such that they start with exactly $$$c$$$ ($$$c \ge 0$$$) zeros. The transitions are the ones in editorial.

        Then you can notice that you don't need second state if at the transition you force to add $$$k$$$ ($$$k \ge 0$$$) zeros and then a $$$1$$$.

        Oh and about dp giving $$$9$$$, well remember you had a zero before first $$$1$$$, so you should multiply by a $$$2$$$ (ie. ans is $$$dp(2) \cdot 2$$$).

        → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
        ← Rev. 3   Vote: I like it +8 Vote: I do not like it

        I have a feeling that we might misunderstand that text for dp[i]. A better example of explaining the mismatch would be:

        i   0  1  2  3  4 5 6 7 8 9
s   0  1  1  1  0 0 1 0 0 0
dp 47 40 28 16 11 6 4 3 2 1

        Notice i=5, s[i]=0, according to the text, it is the number of string we could make using last n-i=10-5=5 characters. This number should be 8 instead of 6 (following the def. of dp)

        I think a better way to explain dp[i] is the following:

        dp[i] is the number of strings that you make where you must keep all preceding consecutive 0s when s[i] = 0, otherwise (if s[i]=1), it's the number of string that you can make to so that you keep this s[i] = 1.

        This explanation is kind of echoing with the greedy method in the tutorial.

        In the example above, dp[5] is the number of extensions where you must keep s[4] and s[5] and you try to extend this with a 1 or a 0 (corresponding to the get(0) and the get(dist[i]+1) component). More specifically, when s[i] is not followed by a 0 (like in the case for s[5]), you have to seek for the consecutive 0 block that is large enough. And finally, you can extend it with nothing if the ending 0 block is large enough or you are extending a 1. That's the dist[i] <= dist.back() component.

        This is what dcordb was talking about for the leading 0s I believe.

        I hope the tutorial is technically clearer for the ignorant like me :P. But I think the problem and the solution are both quite good and I very much appreciate the efforts of the problem setter.

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

In the solution for b1 what does this code correspond to? function<bool(int, int, bool)> go I mean, I understand the meaning but I haven't seen this kind of syntax till now.......

→ Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 2   Vote: I like it -10 Vote: I do not like it

    It is the return type of a lambda expression.

    → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it -10 Vote: I do not like it

    It's a lambda function in C++. Read about them Here.

    → Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 2   Vote: I like it +52 Vote: I do not like it

    Despite what the other commenters say it's actually not a lambda! It's a std::function.

    A std::function does type erasure magic and you can assign lambdas, function pointers, and callable structs (anything that is callable) to it. This type erasure comes at a cost.

    To actually have a lambda function you need to assign it to an auto variable. The type of the lambda is generated at compile time and you can't know it/type it yourself.

    Edit: For clarity. The right hand side of the assignment is a lambda function. But it gets converted to a std::function in the assignment.

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

Problem B1 : How the depth increased by time t = (t % 2k) ?? If so then the depth can be increased more than k which is not possible according to the statement. Help please...

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

    its more like depth increases by A[t], where t = (t%2k), take for example k = 3 array A = [0,1,2,3,2,1] so at time t = 0, depth increases by A[t%2k] = A[0]. similary at t = 4, depth increases by A[4%6] = A[4] = 2.

    → Reply
»
4 years ago, # |
  Vote: I like it -27 Vote: I do not like it

include<bits/stdc++.h>

using namespace std;

typedef long long ll ;

set<tuple<ll, ll, bool>> mark ;

bool dfs(ll n, ll pos, ll &tide, bool &down , vector &d , ll k , ll l) {

if(pos > n) return true ;

if(mark.find({pos,tide,down}) != mark.end()){
    return false;
}

mark.insert({pos,tide,down}) ;

tide += down ? -1 : +1 ;

if(tide == 0) down = false ;
if(tide == k ) down = true ;

if(d[pos] + tide <= l && dfs(n , pos, tide , down , d, k , l)) return true ;
if(d[pos+1] + tide <= l && dfs(n , pos+1 , tide , down , d , k , l)) return true ;

return false;

}

int main(){ ll t ; cin>>t ; while(t--){ 

mark.clear() ;

    ll n  , k , l;

    cin>>n >> k >> l ;

    vector<int> d(n+2 , -k ) ; 

    for(int i=1 ; i<=n ; i++) {
        cin >> d[i] ;
    }

    ll tide = 0;
    bool down = false;

    if( dfs(n,0 , tide, down , d, k, l) ) cout<<"Yes"<<'\n' ;
    else cout<<"No" << '\n' ;   
}

return  0;

}

I am struggling why my code is showing wrong ans

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

    next time post submission link and what task

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

my dp solution for B1 using 2 states — https://codeforces.me/contest/1384/submission/88165283

I want to verify time complexity — I think it should be n * k as for every index k times are possible i.e. earliest you could reach is i + 1 and latest you could reach is i + k

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

1383E - Strange Operation I think my understanding of DP is very good. But even I had trouble with editorial even thought I solved it in the first place! So, for those who want to learn all that magic few people understand, I'll try to explain it as much as I can.

Horrible wall of text
→ Reply
»
4 years ago, # |
← Rev. 4   Vote: I like it +101 Vote: I do not like it

I might be too late to the party, but I am presenting my own solution for 1E anyway.

Let's solve the problem where the first and last character are both 1, because the beginning and ending zeros can be counted and multiplied into the final answer trivially.

Between any two consecutive 1's, let's count the number of 0's, and store it in an array a. So we can "compress" our string into $$$\texttt{1 } a_1 \texttt{ 1 } a_2 \texttt{ 1 ... 1 } a_k \texttt{ 1}$$$, where $$$a_i$$$ is the occurrence of 0's between the $$$i^{th}$$$ 1 character and the $$$(i + 1)^{th}$$$ 1 character. The problem can be then transformed into: for each element $$$a_i$$$, replace it with a value from $$$0$$$ to $$$a_i$$$, or remove the element from the array completely. Count the number of possible arrays that can be made this way.

I denote $$$dp_i$$$ to be the number of different arrays that end in the value $$$i$$$, and denote $$$tot$$$ to be the total number of different arrays. Clearly $$$tot$$$ would be our answer, and $$$tot = (\sum{dp_i}) + 1$$$. Let's maintain this $$$dp$$$ and $$$tot$$$.

Iterate over $$$a$$$. When we loop over $$$a_i$$$, clearly only $$$dp_j$$$ where $$$0 \leq j \leq a_i$$$ change, so let's see how they change. We have two cases of what to do with $$$a_i$$$:

  1. Remove this element completely. $$$dp_j$$$ does not change.
  2. Replace $$$a_i$$$ with $$$j$$$. We can make $$$tot - dp_j$$$ new arrays this way, since we create $$$tot$$$ arrays from appending $$$j$$$ to the previously existing arrays, but $$$dp_j$$$ of them has appeared before.

Therefore, $$$dp_j = dp_j + tot - dp_j = tot$$$. In other words, when we loop over $$$a_i$$$, we assign $$$dp_j = tot$$$ for all $$$0 \leq j \leq a_i$$$, then update our $$$tot$$$. The complexity would still be $$$O(|s|)$$$.

However, I think this solution is much more interesting because this can solve the problem if you are given the string in a compressed manner. When a block of $$$0$$$'s comes, update the $$$dp$$$ like mentioned. When a block of $$$1$$$'s comes, calculate what $$$dp_0$$$ would be after processing all the $$$1$$$'s. We can use a stack to implement this in $$$O(|compress(s)|)$$$.

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

Div 2 D/Div 1 B was beautiful, thanks

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

on the problem string transformation 1, I think the test is really week. My solution is o(n^2+nlogn) but still accepted.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it 
    #include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
long long solve()
{
	vector <long long > f[300];
	long long n; cin >> n;
	string a,b;
	cin >> a;
	cin >> b;
	for (int i=0;i<n;i++)
	if (a[i] > b[i]) return -1;
	vector <pair<char, char>> dp;
	for (int i=0;i<n;i++)
	{
		dp.push_back({b[i],a[i]});
	}
	sort(dp.begin(),dp.end());
	for (int i=0;i<n;i++)
	{
		b[i]=dp[i].first;
		a[i]=dp[i].second;
	}
	//cout << a << endl << b << endl;
	long long res =0;
	for (int i=0;i<n;i++)
	{
		if (a[i]==b[i]) continue;
		res++;
		long long j=i+1;
		char tam = a[i];
		a[i]=b[i];
		while (j<n)
		{ 
			if (a[j]==tam) a[j]=b[i];
			j++;
		}
	}
	return res;
}
int main()
{
	long long t;
	cin >> t;
	while (t--)
	{
		cout << solve() << endl;
	}
	return 0;
}
    → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

What's with all those hacks in div1F?

→ Reply