TheScrasse's blog

By TheScrasse, 3 years ago, In English

1654A - Maximum Cake Tastiness

Author: TheScrasse
Preparation: TheScrasse

Hint 1
Solution

Official solution: 150288088

1654B - Prefix Removals

Author: emorgan
Preparation: TheScrasse

Hint 1
Hint 2
Hint 3
Solution

Official solution: 150288210

1654C - Alice and the Cake

Author: emorgan
Preparation: TheScrasse

Hint 1
Hint 2
Hint 3
Hint 4
Solution

Official solution: 150288232

1654D - Potion Brewing Class

Author: emorgan
Preparation: TheScrasse

Hint 1
Hint 2
Hint 3
Hint 4
Hint 5
Solution

Official solution: 150288255

1654E - Arithmetic Operations

Author: emorgan
Preparation: TheScrasse

Hint 1
Hint 2
Hint 3
Solution

Official solution: 150288285

1654F - Minimal String Xoration

Author: dario2994, emorgan
Preparation: dario2994, TheScrasse

Hint 1
Hint 2
Hint 3
Solution

Official solution: 150288326

1654G - Snowy Mountain

Author: emorgan
Preparation: dario2994, emorgan, TheScrasse

Hint 1
Hint 2
Hint 3
Hint 4
Solution

Official solution: 150288345

1654H - Three Minimums

Author: dario2994, TheScrasse
Preparation: dario2994, TheScrasse

Hint 1
Hint 2
Hint 3
Hint 4
Hint 5
Solution

Official solution: 150306974

  • Vote: I like it
  • +133
  • Vote: I do not like it

| Write comment?
»
3 years ago, # |
  Vote: I like it +123 Vote: I do not like it

didn't solve C :(

However I really like this kind of easy problems that high rated users might stuck on!

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

    Same here... Was second in the contest to solve F, but smh couldn't do C at all. Locked myself into trying to recover stuff in bottom-up manner rather than top-down...

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

      Aha, I was just the opposite. I solved C rather quickly, then locked myself in the top-down manner for problem F for a long time.

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

      Can I know why does bottom-up doesn't work? Even I thought of same approach, but it gives WA on TC 2 150395732

      • »
        »
        »
        »
        3 years ago, # ^ |
        Rev. 2   Vote: I like it +1 Vote: I do not like it

        Try this Testcase on your code: 1 1 1 2 2 2

        The answer should be Yes but your code will give No.

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

    Yes, good contest. Loved solving.

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

    really? it's hard to believe I was able to solve the problem that red_id ignores :v

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

    How to prove the complexity of C?

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

      Here's a rough sketch of why at most $$$O(n)$$$ iterations can happen:

      1. If we exit with an answer of YES, it's $$$O(n)$$$ iterations.

      2. Let $$$p$$$ and $$$q$$$ be the multisets in the official solution. At any point in time, all the elements of $$$p$$$ lie in an interval $$$[c, 2c+2]$$$ for some constant $$$c$$$.

      3. If we exit with an answer of NO, one step before we exited, there was an element of $$$p$$$ larger than the largest element of $$$q$$$, and $$$\sum p = \sum q$$$. Combining with fact 1, we get that $$$|p| \leq 2|q|+O(1)$$$ (this is the hardest step).

      4. So, we insert into $$$p$$$ about $$$2n$$$ times, and remove from $$$q$$$ at most $$$n$$$ times. So it's $$$O(n)$$$ in total.

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

      We can simply exit with an answer of NO as soon as we make N splits, because that'd generate N+1 numbers, so there's at most N splits and at most N "consume up both equal numbers" operations.

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

    If you have solved it now then can you provide proof (in a less mathematical way that one would come up in contest) of how it would take O(n) operations (so time complexity is O(nlogn)) in the official solution of problem C?

»
3 years ago, # |
  Vote: I like it +9 Vote: I do not like it

It's a balanced contest in terms of difficulty.

»
3 years ago, # |
  Vote: I like it +76 Vote: I do not like it

F is really awesome!

»
3 years ago, # |
  Vote: I like it +21 Vote: I do not like it

Video editorial, if anyone prefers that

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

जय हनुमान ज्ञान गुन सागर। जय कपीस तिहुं लोक उजागर।।

Nice questionset. Thanks!

»
3 years ago, # |
Rev. 2   Vote: I like it +26 Vote: I do not like it

I solved F using hashing and xor segment tree. We can maintain a segment tree to answer queries to get the rolling hash of $$$s_{l \oplus x} s_{(l+1) \oplus x} \ldots s_{r \oplus x}$$$ so we can compare $$$2$$$ strings in $$$O(n^2)$$$ by finding the longest common prefix. I think this can be optimized to $$$O(n)$$$ if you really wanted.

Code $$$O(n^2 2^n)$$$: 150271155
Code $$$O(n 2^n)$$$: 150276264

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

    Me too. The intended solutions looks so much simpler and easier to implement tho :(

»
3 years ago, # |
Rev. 2   Vote: I like it +18 Vote: I do not like it

Problem E asks for the same condition as 1616C - Representative Edges, though the constraints make the two problems quite different. I don't think there's anything problematic here, just thought it was interesting.

Edit: There's actually an important distinction because problem E requires the sequence to consists of integers. I feel quite dumb because I failed to solve E in contest due to trying to map fractional slopes and getting TLE due to costly hashing...

»
3 years ago, # |
  Vote: I like it +18 Vote: I do not like it

Great round! Thank you.

»
3 years ago, # |
  Vote: I like it +18 Vote: I do not like it

Great problem!

»
3 years ago, # |
  Vote: I like it +21 Vote: I do not like it

Problem E: Was this simple $$$O(n \sqrt{n} \log n)$$$ (with maybe good constant) allowed?
150252654

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

The TL for problem G is suspicious.

I implemented another algorithm with $$$O(n\sqrt n)$$$ runtime: note that either the resulting height will be $$$\le W$$$, or only at most $$$W$$$ energy could accumulate and be used during the process for $$$W=\sqrt n$$$. One might find the submission here: 150268402. However, it got TLE even with setting $$$W$$$ to 105, which takes precisely $$$O(nW)$$$ time. (I passed during the contest with $$$W=25$$$)

I suspected that either the std constant was very small, or the test cases were weak such that std takes far less than $$$O(n\sqrt n)$$$ time on them.

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

    I am not understanding, so I will ask some questions:

    • What is "std"? It usually stands for "standard" or "sexually transmitted disease", here it seems like it means neither.
    • You use the letter $$$W$$$ but in the solution you linked it seems like the letter $$$W$$$ does not appear. What is $$$W$$$ in the solution you linked?
    • The solution you mention with $$$W=25$$$ shall get WA? Or it should get TLE? Or it is correct that it gets AC?
    • Your point is that you have a correct solution with complexity $$$O(n\sqrt{n})$$$ which gets TLE? If so, then you are saying the the TL is too small?
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +6 Vote: I do not like it
      1. I mean the code of standard solution. Sorry for the unclear abbreviation
      2. It appears as S and T
      3. It should get WA (and I hacked it)
      4. Yeah, I think the TL might be small, and std might take more time on stronger tests.
      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it +28 Vote: I do not like it

        Thanks a lot for the explanation, now I see the point.

        Regarding your solution getting AC instead of WA, that's unfortunate (but not for you :p). I have seen (thanks to your attempted hacks) that you seem to be the only contestant affected, so that's not too bad (for sure not for you :p).

        Regarding the TL being too small for your solution. I would guess that you have a bad constant factor, but I have not checked so I don't know (and I will not investigate further).

        Regarding the TL being too small in general and the authors not noticing because of weak tests. I don't think this is the case. The official solution's slowest behavior (i.e., when $$$z\approx 100$$$, where the letter $$$z$$$ counts the number of interesting heights) is triggered by the tests (just checked adding an assert). Moreover there is also an alternative solution (not mentioned in the editorial) with complexity $$$O(n\log(n))$$$ which fits easily in the TL and whose running time is almost independent of the structure of the tree.

»
3 years ago, # |
  Vote: I like it +37 Vote: I do not like it

Implementing E in $$$O(n\sqrt{n} \log{n})$$$:

*remembers -is-this-fft- said it is evil complexity in his last post and should be avoided at all costs

-> alright i will just use array of size 70 million

150284056

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

    Can you, please, clarify your approach?

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

      When $$$d \le \sqrt{M}$$$ it is same as in editorial, and when $$$d >\sqrt{M}$$$ you can look at my approach as:

      Consider each starting point $$$i$$$ (first element that will be "saved") and check next $$$\sqrt{M}$$$ elements and their possible $$$d$$$, reason why it is enough to check only $$$\sqrt{M}$$$ elements is because after that even when $$$a_i=0$$$, $$$a_j$$$ where $$$j>i+\sqrt{M}$$$ would must be $$$> M$$$ which isn't possible (because $$$a_j=a_i+d*(j-i)$$$)

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

I got MLE in C by popping the largest $$$b_i$$$, as in the editorial, and had to switch to a min heap to pop the smallest $$$b_i$$$ instead. Am I miss something? In this case the solution is $$$O(n\log^2n)$$$ I think.

  • »
    »
    3 years ago, # ^ |
    Rev. 3   Vote: I like it +13 Vote: I do not like it

    Your submission is $$$O(sum*\log sum)$$$

    Testcase
    Fix
»
3 years ago, # |
  Vote: I like it +6 Vote: I do not like it

Problem C was good :)

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

    The best problems are those you solve, find intuitive and clear, but the others don't

    --Not me, That guy's (that is not me) hypocritical arguments

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

In question D, the same solution can be done for node 2,3 and all. So why should we not take max of all of them. In other words, why taking node 1 as lcm of denom and setting others accordingly works?

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

    If you start DFS from any node $$$s$$$, the result is already the minimum possible, so you would get the same result for any node.

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

      Ah, I thought of exact same logic, but thought will have to check for al vertices. F

»
3 years ago, # |
Rev. 4   Vote: I like it +4 Vote: I do not like it

My Approach for Problem C:

Perform BFS starting from the total sum of the given weights(root node). There can be maximum of two child nodes of a parent node. Child Nodes are $$$ceil(p/2)$$$ and $$$floor(p/2)$$$, where $$$p$$$ is a parent node.

Only explore those child nodes which are not present in the given weight array.Reason for this is, because If we have already found a weight(value of the child node) which is present in the input weight array, we should not divide it further, instead we will count this weight in our answer.

(Exploring means cutting a piece of cake, Or dividing the child node into 2 halves.)

For example, If both child nodes of a particular parent node are $$$64$$$ and If $$$64$$$ is present in the input array ($$$1$$$ time), then we will explore only one child node.If its present more than $$$1$$$ time, we will not explore these $$$2$$$ child nodes, because we will be counting these $$$2$$$ child nodes in our answer.

Note- You can draw a tree on a paper, It will be more clear.Start from sum of all given weights, and divide it further, It will look like a binary tree.

If we have explored $$$n-1$$$ nodes, that means we have performed $$$n-1$$$ cuts to the cake.Hence we have divided the cake into $$$n$$$ weights.

Answer will be YES, If we found all the input weights in our binary tree.Otherwise, It will be NO.

Time Complexity — $$$O(n)$$$, where $$$n$$$ is number of input weights (size of the array). Reason being, BFS will stop as soon as we explored $$$(n-1)$$$ nodes.

My AC Solution-Click Here

»
3 years ago, # |
  Vote: I like it +32 Vote: I do not like it

Wow, F is just awesome, I have never seen use of suffix array in this manner.

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

[Deleted]

»
3 years ago, # |
  Vote: I like it +10 Vote: I do not like it

https://codeforces.net/contest/1654/submission/150245226

Could someone explain why this solution work ? Isn't it has complexity $$$O(n^2)$$$ so it should be TLE ?

»
3 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Lesson learnt rest well before contest!

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

C is really a good problem. I was confused at first, but when I finally solved it, the solution seems to be obvious.

»
3 years ago, # |
  Vote: I like it +8 Vote: I do not like it

The editorial is amazing! I hope all the editorial have "Hints".

»
3 years ago, # |
Rev. 2   Vote: I like it +15 Vote: I do not like it

In problem G, there is

The largest possible value of $$$\sum\limits_{v\in S}h_v$$$ is $$$O(n)$$$.

I don't know why, can anyone help me?

Thanks in advance.

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

    I dont have a rigorous proof of this fact, but I believe this can be obtained by giving a lower bound for the number of vertices with height $$$i$$$ given the number of flippable vertices with greater or equal height (for example, lower bounded by half of this quantity).

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

    I am not able to prove strict linear dependency but it is very close. Let's have an array{X1,X2,X3...,Xn} which denotes the frequency of flippable vertex for each height. Then let S = X1*1+ X2*2 ...+ Xn*n The S is amount of nodes that will be needed generate all flippable vertex. For example, flippable vertex with H=3 will require 3 vertex with H=0,1 and 2. There will be overcounting. Specifically, a node can be contribute to multiple flippable vertex. Let O be that value. We then have S-O <= n. We can use small to large to proof that there will atmost Logn flippable nodes that a single node can contribute to.That gives O <= Nlogn. Thus we have S<= N(Logn + 1).

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

    Here are my thoughts. qwq

    First root the tree at a base lodge. Consider a BFS cover process below.

    BFS from the root and we can find some nearest base lodges.

    A pair of "flippable points" must exist at the midpoint of the path from these lodges to the root. We pair the lower endpoints of each point pair with certain nearset lodge and cover the path between them.

    In addition, there are no other flippable point pairs on the merge of paths from these lodges to the root (blue area in the figure).

    So we delete blue area and the original tree is divided into several subtrees with roots. We can do similar process in each subtree.

    Finally, we can see the coverage areas do not intersect so half of $$$\sum\limits_{v\in S}h_v$$$ is $$$O(n)$$$.

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

    I figured out another proof of this. First, we can group the vertices in a way that each vertex and its nearest base lodge are in the same group. Let $$$k$$$ denote the number of base lodges. Then we get $$$k$$$ group. Each group forms a tree, let $$$T_i$$$ denote the $$$i$$$-th tree, $$$|T_i|$$$ denote the number of vertices in the $$$i$$$-th tree.

    Besides the edges inside every tree, there are $$$k-1$$$ cross-tree edges, each of which connects two vertices in different trees. The difference of the height of two vertices of a cross-tree edge is no more than 1. If the height is equal, then the two vertices form a pair of flippable vertices. Since we want to make the sum of these height as large as possible, we can assume that all $$$k-1$$$ cross-tree edges connect equal-height vertices. In other words, we have $$$k-1$$$ pair of flippable vertices.

    For a pair of flippable vertices with height $$$h$$$, if they belong to $$$T_A$$$ and $$$T_B$$$ respectively, then we can get $$$h \leq |T_A|, h \leq|T_B|$$$.

    If we compress each tree $$$T_i$$$ as a single vertex, and all $$$T_i$$$ and the $$$k-1$$$ cross-tree edges will form an abstract tree. We can let $$$T_1$$$ be the root of this tree, then the edges of the tree can be listed as $$$(T_2, p(T_2)), (T_3, p(T_3))... (T_k, p(T_k))$$$, where $$$p(x)$$$ is the parent of $$$x$$$.

    Thus, $$$\sum h \leq 2(|T_2| + |T_3| + ... + |T_k|) \leq 2n$$$.

    Q.E.D.

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

I tried explaining my solutions for problem A,B and C . Link to the video

Hope this can be of any help.

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

D claims that to recover LCM it takes the minimum of all powers for each prime p over DFS. This claim does not make sense to me — and in the code itself it seems like it takes the maximum

for (int p : factors[x]) f[p]++, cmax(wf[p], f[p]);

It would be good to know where I have misunderstood

Edit — Ah I see, taking the max and multiplying by 1 is the same as taking the min and multiplying by -1.

»
3 years ago, # |
  Vote: I like it +1 Vote: I do not like it

I didn't solve C. because I'm keep writting solutions of bottom-up during the contest... :(

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

    i can 100% relate to this when testing the round D:

    Sometimes thinking too hard can screw you over :/

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

Problem C, my solution is based on something that I can't prove...

I guessed that if the initial value is $$$k$$$,then the numbers we can get by spliting $$$k$$$ is like $$$\frac{k}{2^w}$$$ and $$$\frac{k}{2^w}+1$$$.

according to this conclusion, I passed this problem. 150259381

I don't know how to prove or hack this submission.If you can help me I will be very thankful :D

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

    In my submission, $$$x$$$ is the number of $$$s$$$, and $$$y$$$ is the number of $$$s+1$$$

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

    Your claim is true. In fact, if you define $$$f(x) = \lfloor \frac{x}{2} \rfloor$$$, $$$g(x) = \lceil \frac{x}{2} \rceil$$$, you get $$$f^w(x) = \lfloor \frac{x}{2^w} \rfloor$$$, $$$g^w(x) = \lceil \frac{x}{2^w} \rceil$$$.

    Sketch of proof:
    Let $$$x = 2^w \cdot \lfloor \frac{x}{2^w} \rfloor + b_0$$$ ($$$0 \leq b_0 < 2^w$$$). Then, $$$f^v(x) = 2^{w-v} \cdot \lfloor \frac{x}{2^w} \rfloor + b_v$$$.
    $$$b_v = \lfloor \frac{b_{v-1}}{2} \rfloor$$$, so $$$b_w = 0$$$ and $$$f^w(x) = \lfloor \frac{x}{2^w} \rfloor$$$.
    Same proof for $$$g$$$.

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

I literally got stuck in C and couldn't solve C and did not try to move on

At last I lost 171 rating

»
3 years ago, # |
Rev. 2   Vote: I like it +18 Vote: I do not like it

I think in the Hint 5 of the editorial of H, the ODE should be:

$$$y'(t)=a(t)y(t)+b(t)$$$

In the current version, the ODE has 2 "+", without any "=".

»
3 years ago, # |
  Vote: I like it +40 Vote: I do not like it

G can also be solved in O(nlog^2n) with centroid decomposition

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

    It's also possible to improve this to $$$\mathcal{O}(n \log n)$$$, since the positions of the segment tree you need to update and query are bounded by the current centroid's subtree size, so you can simply use an array with prefix minimums. Code: 150307419

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

      I realized that I don't even need a segment tree since I am also only checking the maximum number in the complete segment tree and not a subrange.Can just maintain the maximum in one variable.Code

»
3 years ago, # |
Rev. 3   Vote: I like it -10 Vote: I do not like it

I solved C using BFS .. multiset and queue ..and got AC ..you can see my simple code here: https://codeforces.net/contest/1654/submission/150350334

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

Can someone help me with this code Solution ,I guess there is some issue due to modular operations.

»
3 years ago, # |
  Vote: I like it +10 Vote: I do not like it

I really loves this kind of editorials. This helps soo much!

»
3 years ago, # |
  Vote: I like it -10 Vote: I do not like it

I am trying to solve D by running DFS twice: First Bottom-Up and then Top-Down.
The solution seems to be working fine on smaller test-cases (5-6 edges) but its output slightly differs on the pretest's 3rd test-case, which is difficult to analyze.
Submission.

»
3 years ago, # |
  Vote: I like it +10 Vote: I do not like it

The editorial with serveral hints was great help to me! It can always help me understand how to come up with the correct ideas. And the solutions are also very comfortable to read and easy to understand.

»
3 years ago, # |
Rev. 4   Vote: I like it -11 Vote: I do not like it

Problem C editorial solution will get TLE for bellow case:

1
200000
1000000000 1000000000 1000000000 1000000000 1000000000 ... all 2*10^k element of a is 10^9

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

    I did some wrong maths, and finally understood the solution. thanks.

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

anyone please tell me my mistake in problem C 156969000

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

    It's a really silly error, but in line 52, you wrote bb.top() when you actually meant bb.pop(). This led to time/memory limit exceeded because if you enter that case even once, then it would perpetually add new elements forever while the top remains unchanged.

    For future reference, to better identify the mistakes you made, my suggestion is to:

    • try the sample input first
    • if that fails, try running only one test case at a time, for each test case in the sample input. This will allow you to identify which test case breaks your program.
    • For the problematic test case, try to trace through what happens in your program for this specific case, carefully reading each line that is executed and writing out intermediate values and so on. This should reveal why the output differs from your expectations (or why the time/memory limit was exceeded).

    (if the sample input passes, then you'd want to construct edge cases or tricky cases that do not seem to be covered in the sample input, and follow the same steps)

    By the way, I only tested your code on the sample input, and the correction was sufficient. However, I don't actually know if the rest of your code is actually correct.

    Yes, I know this is like, two months late, but I understand the frustration of not knowing why your code is failing, so hopefully this may be a little comforting and can help you avoid similar errors in the future, with proper debugging.