awoo's blog

Educational Codeforces Round 140 Editorial
By awoo, history, 3 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 (27)
| Write comment?
»
3 years ago, hide # |
 
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
»
3 years ago, hide # |
← 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
  • »
    »
    3 years ago, hide # ^ |
     
    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
»
3 years ago, hide # |
 
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
»
3 years ago, hide # |
 
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
»
3 years ago, hide # |
 
Vote: I like it +33 Vote: I do not like it

problem A-E video Editorial for Chinese:

BiliBili

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

Full Detailed Solution with Explanation of Problem C

→ Reply
»
3 years ago, hide # |
 
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
»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Please make the editorial more understandable.

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

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

→ Reply
»
3 years ago, hide # |
 
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
  • »
    »
    3 years ago, hide # ^ |
     
    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
»
3 years ago, hide # |
← 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 \lt 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
»
3 years ago, hide # |
← 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
»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    3 years ago, hide # ^ |
    ← 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
»
2 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

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

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

You can reduce $$$E$$$'s complexity to $$$O(2^{\frac{m}{2}} + n)$$$ by transforming the problem into finding the maximum independent set of deactivated colors (excluding the colors at platforms $$$1$$$, $$$n$$$, and any colors that are adjacent to each other in the list of platforms). Then you can change the maximum independent set problem into finding the maximum clique of the graph's complement and apply the same sort of memoization as in this problem: https://mirror.codeforces.com/contest/1105/problem/E. Or it can be done in $$$\approx O(1.38^m)$$$ with this algorithm.

→ Reply