Vladosiya's blog

Codeforces Round #811 (Div. 3) Editorial
By Vladosiya, history, 2 years ago, In English

1714A - Everyone Loves to Sleep

Idea: Vladosiya

Tutorial
Solution

1714B - Remove Prefix

Idea: MikeMirzayanov

Tutorial
Solution

1714C - Minimum Varied Number

Idea: MikeMirzayanov

Tutorial
Solution

1714D - Color with Occurrences

Idea: MikeMirzayanov

Tutorial
Solution

1714E - Add Modulo 10

Idea: senjougaharin

Tutorial
Solution

1714F - Build a Tree and That Is It

Idea: MikeMirzayanov

Tutorial
Solution

1714G - Path Prefixes

Idea: MikeMirzayanov

Tutorial
Solution
  • Vote: I like it
  • +22
  • Vote: I do not like it

Comments Comments (38)
| Write comment?
»
2 years ago, # |
  Vote: I like it +23 Vote: I do not like it

Code for D is messed up a bit.

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

    I implemented it in an easier way.

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

Mike Mirzayanov thanks for awesome editorial

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

    Idk, awesome editorial in my understanding contains much more detailed and intuitive solutions with hints, this one is just ok.

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

Question D is a great problem,but why is the code for D so messy？

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

How to solve question D with DP? Can you tell me about it and share your code? If you can help me, I will thank you very much.

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

    Here is my solution: [submission:166798483]

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

      What does your dp[i] mean？

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

        dp[i] is the minimum number of steps needed to color prefix(length is i) of text t in red.

        use[i]: If an operation was done at a certain location, I recorded the selected subscript.

        from[i]: Otherwise I recorded which operation the location was affected by.

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

        dp is an array and i is the element position in the array

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

          wth is this shit man. Stop it

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

          This comment does not have enough downvotes for destroying almost the entire comment section of the editorial.

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

Indented solution of problem D from editorial:

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

"When you color a letter in red again, it stays red."

Missed this line during contest does this make the question similar to Jump game? ->where we can jump from index to any index in range (i,i+a[i])

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

The code for F: Build a Tree and That is it does not really clarify things mentioned in tutorial rather it has checks and implementations that makes it seem like the code to be working on a different idea. Can anyone either explain the tutorial or the code ? Thanks.

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

    Can you help me with G.I checked ur code, but can't understand, Can u explain ur idea ? Thanks.

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

      So, let's first make a DFS call and make array Asum[N], where Asum[u] stores the sum of all the A-values along the edges from root to node u.

      Now notice that B values of all edges are positive. Let's pick any node u. And let's say, Path[u] = [B1, B2, B3, B4, B5,.....Bx] where the Bi indicates the B-values of all edges from root to node u.

      Since Bi s are positive the prefix sum on Path[u] will only increase. Let's call the prefix sum on Path[u] as PrefixPath[u].

      Since we want to know maximum prefix path that doesnt go beyond all A values sum in the path from root to u, the final answer for node u will be

      Answer[u] = Largest index k in PrefixPath[u] such that PrefixPath[k] > Asum[u].

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

    I can explain my idea of solution if it can help you.

    Let's place $$$1,2$$$ and $$$3$$$ nodes. There is $$$4$$$ possible ways to do it: link to image

    1. The first case: $$$d_{23} = d_{31} + d_{12}$$$. Let's check it, if it is right, then let's build our tree like in image.

    2. The second case: $$$d_{31} = d_{23} + d_{12}$$$. Let's check it, if it is right, then let's build our tree like in image.

    3. The third case: $$$d_{12} = d_{23} + d_{31}$$$. Let's check it, if it is right, then let's build our tree like in image.

    4. The last case: let's see that $$$d_{12} + d_{23} + d_{31} \le n$$$, let's get loop for $$$d_{14} = [1..n]$$$ (sum of $$$n$$$ for all cases is $$$\le 10^5$$$ so we can do it), now we know $$$d_{34} = d_{31} - d_{14}$$$ etc. If all this right, then let's build our tree like in image.

    If all cases are wrong, answer is NO.

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

      Woah...Thank you so much. The image actually made your idea very clear. upvote_plus_plus

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

My Editorial for the problems I solved

A
B
C
D
E
→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

It was a very good contest D was interesting but i think you should reorder the problem like this B C A E D G F

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

I read the solution "Thus, we will apply the operation to each element of the array until its remainder modulo 10 becomes, for example, 2, and then check that the array does not contain both remainders 2 and 12 modulo 20." I don't know why do we need to check that "the aray does not contain both remainders 2 and 12 modulo 20". Why do we have to do that. Can you explain for me. Thanks

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

    There are only 2 possible cycles when considered modulo 20 (2 -> 4 -> 8 -> 16 -> 2) and (12 -> 14 -> 18 -> 6 -> 12). If members of both cycles are present, you can never make all the numbers the same.

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

Code for $$$Problem D$$$ should be posted like this :

Solution

I think Vladosiya has forgotten to write </spoiler> at the end.

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

In problem E, why flag12 and flag2 should not be true for the answer to be YES?

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

    Remainders 2, 4, 6, 8 cycles and in that cycle number increases by 20. So difference between every two elements must divide by 20 (and these elements must have the same remainder modulo 20).

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

Why I got TLE ? What's wrong with my code[submission:166546367]

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

Is there a way to solve G using binary lifting

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

Could someone explain why this submission for G of mine get TLE ? I know it's inefficient but I still don't get why it doesn't work

First I do a dfs to precompute all prefix sums for a and b. Then for each leaf I find the path from it to the root, reverse the path, and use binary search for each vertices on the path to get the answer.

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

Hi can anyone help me figure out why my code for D is wrong? Thanks a lot! Basically I have tried to iteratively find the places with maximum coverage. However, it gives WA on a later TC.

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

    Take a look at Ticket 16127 from CF Stress for a counter example.

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

      Thanks! However, I am also interested to know why the editorial solution won't face the same problem as my solution.

      → Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Why in Problem D ,why does the algorithm in which selecting the word from which maximum red letters occurs in string s in a given step doesn't work.. According to my understanding .. If we don't pickup the substring of s in which maximum occurence of red happens in a step , then we can always pick it up later if the substrings of current picking doesn't intersect with the substring in which the maximum red occurence happens in a particular step. And if the substring intersect , then still we can swap the positions of picking of a substring in which maximum red characters appear in a step , the number of reds will decrease by the same. But , if one string is a substring in the strings in which we have to make it red. then picking the string with maximum red happens in a step is still optimal .. So , at each step just applying the operation with the string k[i] (1 <= i <= k) , in which the maximum new red characters which happen in a operation in string s is wrong.

Implementation of the Algorithm :- In the submission Link.

Wrong Submission Link :- 242502092

Question Id :- 1714D - Color with Occurrences

→ Reply