Shayan's blog

Codeforces Round 964 (Div. 4) — Video Tutorial
By Shayan, 3 months ago, In English

1999A — A+B Again?

Video

1999B — Card Game

Video

1999C — Showering

Video

1999D — Slavic's Exam

Video

1999E — Triple Operation

Video

1999F — Expected Median

Video

1999G1 — Ruler (easy version)

Video

1999G2 — Ruler (hard version)

Video
  • Vote: I like it
  • +24
  • Vote: I do not like it

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Thanks for the editorial, especially the video. These are much more comprehendible than written ones. I also saw your discussion video, "Codeforces Round 963 (Div 2)—Solution Discussion." However, I noticed that the sound is occasionally a bit low in both of them, and this editorial video is much lower compared to the "Codeforces Round 963 (Div 2)—Solution Discussion."

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

thank you so much brother

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

i have a doubt in D, if we approach it greedily then for ever '?' we would sub it by the t string char, but what if after ?, there is some different character, other than then answer would be

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

    I had a similar concern while thinking about this, but it doesn't matter.

    If I understood your question correctly, do you mean for example:

    ?dackk? acx

    In this example, if we change the first ? into an 'a', it's the same thing as not changing it at all. We'll simply ignore the second a, and still come to the same conclusion. Basically, it is always better to use the ? than not, which is why the greedy approach works

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

      but if we always use the question mark and if our counter of the substring does become == to length of substring we post YES as the solution but it could also lead to a case like

      string — ?xxyapof?? substrin-xax

      int this case according to the greedy algo we will get a YES as answer coz ? would increase substring length, then a would increase its length and then the next ? would increase its length, while we can clearly see that the substring will never be formed in the given string

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

        Hi, sorry I think there's a misunderstanding here. What makes you say we can clearly see the substring will never be formed?

        The example you gave will post a YES, because we can get a xax from that string, in multiple ways. First of all, since we have a number of question marks (3) that are >= the length of the substring (3), this is automatically a yes lol. Since we can change each question mark to fit the letter.

        Or, we can take the first question mark as x, take the middle a, and one of the last two question marks as x. Or, take one of the x's, the a, and an x from the end of the string. Either way, this testcase is definitely a yes.

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

          wait, im very dumb, i just read the question correctly and got to know substring need not be continious , T.T , sorry for wasting your time

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

            hahaha no worries, I've done similar stuff as well. Always fun to think about these questions :)

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

why E gives tle for O(N) solution?

Java 275163443 C++ 275165193

Shayan

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

    It is not mentioned in the problem statement that sum of (r-l) <= 2e5 or something like that , So you need to precompute and solve

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

Thanks so much, I am able to learn only because of this. Thank you very much.

→ Reply