awoo's blog

By awoo, history, 18 months ago, translation,

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)
• +52

| Write comment?
 » 18 months ago, # |   +17 I have become an Expert thanks to this contest! Great D by the way.
•  » » 18 months ago, # ^ |   -36 Don't worry , your new colour won't last long :D
•  » » » 15 months ago, # ^ |   +10 Despite getting a lot of downvotes, your prediction was indeed correct.
 » 18 months ago, # | ← Rev. 2 →   0 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
•  » » 18 months ago, # ^ |   0 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.
 » 18 months ago, # |   +10 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
•  » » 18 months ago, # ^ |   0 And that's why we're not there yet. You're blue, I'm green haahha
•  » » 9 months ago, # ^ |   0 I will even die
 » 18 months ago, # |   +9 I think the overall complexity of attached solution of E is $O(2^{m/2} \cdot m)$
 » 18 months ago, # |   +33 problem A-E video Editorial for Chinese:BiliBili
•  » » 18 months ago, # ^ | ← Rev. 2 →   -20 hi just a request.Please add english captions or if possible please speak in english.Thanks for such a great video.
 » 18 months ago, # |   0
 » 18 months ago, # |   +10 Problem A: ...and one of the resulting parts becomes a rectangle. It never becomes a rectangle, rather it becomes a quadrilateral.
 » 18 months ago, # |   0 Please make the editorial more understandable.
 » 18 months ago, # |   0 Most of solutions and tutorials with "mask" are pretty hard to understand.
 » 18 months ago, # |   +3 This editorial was hard to understand, please make it easier to understand next time
•  » » 18 months ago, # ^ |   0 Alas, you are right, and there are too many hard-to-understand editorials on Codeforces. Sometimes I would rather directly learn top contestants' code.
 » 17 months ago, # | ← Rev. 2 →   0 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. ProofIf we make $v$ true (which we can do safely, because all neighbors are false), such selection would be a more optimal one. Hence, current selection is not optimal.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
 » 17 months ago, # | ← Rev. 2 →   0 In problem F, in the first solution, why do we need to separate queries into light and heavy? Help, please.
 » 15 months ago, # |   0 can someone share the n^2 approach for problem C.
•  » » 12 months ago, # ^ | ← Rev. 2 →   0 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
 » 9 months ago, # | ← Rev. 3 →   0 Nice Contest. I think contests like this will reduce inflated ratings.I dont know when will I be mature enough to apperciate EduForces until then I hate EduForces.
 » 9 months ago, # |   0 when I solve it on my own I understand editorial and when i dont,when i require the editorial most I fail to understand a bit,most of the times.
 » 3 months ago, # |   0 can someone write the time complexity of problem [problem:1767D]D?
•  » » 6 weeks ago, # ^ |   0 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.
•  » » 4 weeks ago, # ^ |   0 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$.