awoo's blog

Educational Codeforces Round 140 Editorial
By awoo, history, 2 years ago, translation, In English

1767A - Cut the Triangle

Idea: BledDest

Tutorial
Solution (BledDest)

1767B - Block Towers

Idea: BledDest

Tutorial
Solution (awoo)

1767C - Count Binary Strings

Idea: BledDest

Tutorial
Solution (BledDest)

1767D - Playoff

Idea: Neon

Tutorial
Solution (Neon)

1767E - Algebra Flash

Idea: BledDest

Tutorial
Solution (awoo)

1767F - Two Subtrees

Idea: shnirelman

Tutorial
Solution (shnirelman)
  • Vote: I like it
  • +52
  • Vote: I do not like it

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

I have become an Expert thanks to this contest! Great D by the way.

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

    Don't worry , your new colour won't last long :D

    → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it +10 Vote: I do not like it

      Despite getting a lot of downvotes, your prediction was indeed correct.

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

In problem A, since the first line is empty. I read it as a string and never bothered to use it. It WA'd. This is my submission 185477892 . After the contest, I didn't even bother to read the first line and used the same code as above and it got AC. I am not sure why and could use some help.185647398

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

    cin >> [whatever] doesn't work as you think. The input data is split into tokens: a token is a sequence of characters. Tokens are separated by whitespaces (incl. normal spaces and newline characters). Doing cin >> [whatever] reads the next token* and tries to convert it into the type of the variable. Doing cin >> [whatever] always skips over any spaces and newline characters. Thus, your cin >> s reads the first integer into your string, messing up the values. In order to read a full line into a single string (including all spsces, but not the newline character) you need to do the following:

    string s;
getline(cin, s);

    *doing cin >> [char] only reads the next character, but it still skips whitespaces.

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

I will have time to grow old before the moment when I completely read, understand and solve the problem F... The longest editorial I've ever seen

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

I think the overall complexity of attached solution of E is $$$O(2^{m/2} \cdot m)$$$

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

problem A-E video Editorial for Chinese:

BiliBili

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

    hi just a request.Please add english captions or if possible please speak in english.

    Thanks for such a great video.

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

    but you , my friend , you are the truly hero.

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

Full Detailed Solution with Explanation of Problem C

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

Problem A:

...and one of the resulting parts becomes a rectangle.

It never becomes a rectangle, rather it becomes a quadrilateral.

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

Please make the editorial more understandable.

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

Most of solutions and tutorials with "mask" are pretty hard to understand.

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

This editorial was hard to understand, please make it easier to understand next time

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

    Alas, you are right, and there are too many hard-to-understand editorials on Codeforces. Sometimes I would rather directly learn top contestants' code.

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

There is an alternative solution for 1767E - Algebra Flash not using meet-in-the-middle, but employing an additional observation. I suspect that it works in $$$O(2^{m/2}*m)$$$ and system tests validate this, but I could use someone's help for a complete analysis.

A general idea is to activate every color in the beginning and deactivate colors one by one — well, actually two for one (at least). Firstly, we look at the lowest unselected color — call it $$$v$$$. Two options — either make it true (Deactivated) or false (Leave as activated).

First case: we make $$$v$$$ true. Then let's look at its neighbors. If neighboring color $$$u$$$ comes before $$$v$$$ $$$(u < v)$$$, this means we already assigned it some color. Otherwise we still didn't decide on color of $$$u$$$ and have to make it false (Because $$$v$$$ and $$$u$$$ cannot be deactivated simultaneously due to the same reasons as described in the editorial).

Second case: we make $$$v$$$ false. There is an important observation to use: If $$$v$$$ is false and all of its neighbors are false too, such color selection cannot be optimal.

Proof

Now, when we set $$$v$$$ to false, at least one of the neighbors must be set to true. So let's select that neighbor and then apply a known procedure for true vertexes (mark its neighbors as false)

Partial proof of complexity.

Since we remove at least 2 vertexes at each state, the maximum depth of recursion is at most $$$m/2$$$. Also, at each state, we have two choices: either to make the lowest color $$$x$$$ true or false. In case of making $$$x$$$ true, we create at most one new state.

In case of making $$$x$$$ false, we select $$$x$$$'s neighbor $$$y$$$, which we mark as true. The number of such neighbors can be up to $$$m$$$, but let's look at each generated state individually. The state with $$$x$$$ false and $$$y$$$ true is a repeated state, which we will also cover when $$$y$$$ will be the lowest unselected color. How many times such states are visited — is something that I need a help with.

If we apply some clever memoization — then the complexity is for sure $$$O(2^{m/2}*m)$$$, but even without memoization the solution passes the System Tests quite confidently.

Note: There is an edge case to look at when marking non-deactivatable colors as false.

Submission: 189735982

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

In problem F, in the first solution, why do we need to separate queries into light and heavy? Help, please.

→ Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

can someone share the n^2 approach for problem C.

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

    n^2 solution: Code

    • dsu[i] = set no in which ith element belongs, the elements in a set must exist in same state (0 or 1) as they're connected with a[i][j] = 1.
    • c[i] = position of the nearest index j such that s[i] to s[j] must have at least 2 diff elements
    • same[i][j] = number of ways elements from i to j would be same
    • dp[i] = number of binary strings considering only rules till 0 to i
    • Hopefully, you understand
    → Reply
»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

can someone write the time complexity of problem [problem:1767D]D?

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

    o(n) + log(n), n is max 18 steps. Its only linear since we need to parse the input string, the actual algorithm part is logarithmic.

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

    It will be exponential, something of the order $$$O(2^n)$$$, that is the reason, in the constraints we have $$$n \le 18$$$ as $$$2^{18} \approx 2 \times 10^5$$$.

    → Reply