TheScrasse's blog

By TheScrasse, 2 years ago,

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

• +133

| Write comment?
 » 23 months ago, # |   +123 didn't solve C :(However I really like this kind of easy problems that high rated users might stuck on!
•  » » 23 months ago, # ^ |   +37 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...
•  » » » 23 months ago, # ^ |   +11 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.
•  » » » 23 months ago, # ^ |   0 Can I know why does bottom-up doesn't work? Even I thought of same approach, but it gives WA on TC 2 150395732
•  » » » » 23 months ago, # ^ | ← Rev. 2 →   +1 Try this Testcase on your code: 1 1 1 2 2 2The answer should be Yes but your code will give No.
•  » » » » » 23 months ago, # ^ |   0 Got the reason why it fails. Thanks
•  » » 23 months ago, # ^ |   +10 Yes, good contest. Loved solving.
•  » » 23 months ago, # ^ |   +4 really? it's hard to believe I was able to solve the problem that red_id ignores :v
•  » » 23 months ago, # ^ |   0 How to prove the complexity of C?
•  » » » 23 months ago, # ^ |   0 Here's a rough sketch of why at most $O(n)$ iterations can happen: If we exit with an answer of YES, it's $O(n)$ iterations. 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$. 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). So, we insert into $p$ about $2n$ times, and remove from $q$ at most $n$ times. So it's $O(n)$ in total.
•  » » » 23 months ago, # ^ |   +13 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.
•  » » 23 months ago, # ^ |   0 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?
 » 23 months ago, # |   +9 It's a balanced contest in terms of difficulty.
 » 23 months ago, # |   +76 F is really awesome!
 » 23 months ago, # |   +21 Video editorial, if anyone prefers that
 » 23 months ago, # |   +2 जय हनुमान ज्ञान गुन सागर। जय कपीस तिहुं लोक उजागर।।Nice questionset. Thanks!
 » 23 months ago, # | ← Rev. 2 →   +26 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)$: 150271155Code $O(n 2^n)$: 150276264
•  » » 23 months ago, # ^ |   0 Me too. The intended solutions looks so much simpler and easier to implement tho :(
 » 23 months ago, # | ← Rev. 2 →   +18 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...
 » 23 months ago, # |   +18 Great round! Thank you.
 » 23 months ago, # |   +18 Great problem!
 » 23 months ago, # |   +21 Problem E: Was this simple $O(n \sqrt{n} \log n)$ (with maybe good constant) allowed?150252654
 » 23 months ago, # |   0 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.
•  » » 23 months ago, # ^ |   +9 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?
•  » » » 23 months ago, # ^ |   +6 I mean the code of standard solution. Sorry for the unclear abbreviation It appears as S and T It should get WA (and I hacked it) Yeah, I think the TL might be small, and std might take more time on stronger tests.
•  » » » » 23 months ago, # ^ |   +28 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.
 » 23 months ago, # |   +37 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
•  » » 23 months ago, # ^ |   0 Can you, please, clarify your approach?
•  » » » 23 months ago, # ^ |   0 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)$)
 » 23 months ago, # |   0 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.
•  » » 23 months ago, # ^ | ← Rev. 3 →   +13 Your submission is $O(sum*\log sum)$ Testcase1 536870911.In general, $1$ and $2^n-1$. FixExit if max in the priority queue is less than multiset. OrExit when the size of the priority queue becomes more than n.Anything should work.
 » 23 months ago, # |   +6 Problem C was good :)
•  » » 23 months ago, # ^ |   +6 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
•  » » » 23 months ago, # ^ |   +5 Yup, I agree :D
 » 23 months ago, # |   0 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?
•  » » 23 months ago, # ^ |   0 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.
•  » » » 23 months ago, # ^ |   0 Ah, I thought of exact same logic, but thought will have to check for al vertices. F
 » 23 months ago, # | ← Rev. 4 →   +4 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
 » 23 months ago, # |   +32 Wow, F is just awesome, I have never seen use of suffix array in this manner.
 » 23 months ago, # | ← Rev. 2 →   0 [Deleted]
 » 23 months ago, # |   +10 https://mirror.codeforces.com/contest/1654/submission/150245226Could someone explain why this solution work ? Isn't it has complexity $O(n^2)$ so it should be TLE ?
•  » » 23 months ago, # ^ | ← Rev. 2 →   0 It's supposed to get both WA and TLE: 150245226, 150307656.I'm wondering why it works so well on official tests.
 » 23 months ago, # |   +1 Lesson learnt rest well before contest!
 » 23 months ago, # | ← Rev. 2 →   0 C is really a good problem. I was confused at first, but when I finally solved it, the solution seems to be obvious.
 » 23 months ago, # |   +8 The editorial is amazing! I hope all the editorial have "Hints".
 » 23 months ago, # | ← Rev. 2 →   +15 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.
•  » » 23 months ago, # ^ |   0 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).
•  » » 23 months ago, # ^ |   +9 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).
•  » » 23 months ago, # ^ |   +10 Here are my thoughts. qwqFirst 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)$.
•  » » 22 months ago, # ^ |   0 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.
 » 23 months ago, # |   +3 I tried explaining my solutions for problem A,B and C . Link to the videoHope this can be of any help.
 » 23 months ago, # | ← Rev. 2 →   0 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 maximumfor (int p : factors[x]) f[p]++, cmax(wf[p], f[p]);It would be good to know where I have misunderstoodEdit — Ah I see, taking the max and multiplying by 1 is the same as taking the min and multiplying by -1.
 » 23 months ago, # |   +1 I didn't solve C. because I'm keep writting solutions of bottom-up during the contest... :(
•  » » 23 months ago, # ^ |   +8 i can 100% relate to this when testing the round D:Sometimes thinking too hard can screw you over :/
 » 23 months ago, # |   0 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. 150259381I don't know how to prove or hack this submission.If you can help me I will be very thankful :D
•  » » 23 months ago, # ^ |   0 In my submission, $x$ is the number of $s$, and $y$ is the number of $s+1$
•  » » 23 months ago, # ^ |   +15 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$.
 » 23 months ago, # |   0 I literally got stuck in C and couldn't solve C and did not try to move onAt last I lost 171 rating
 » 23 months ago, # | ← Rev. 2 →   +18 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 "=".
 » 23 months ago, # |   +40 G can also be solved in O(nlog^2n) with centroid decomposition
•  » » 23 months ago, # ^ |   +10 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
•  » » » 23 months ago, # ^ |   +25 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
 » 23 months ago, # |   0 Can someone help me with this code Solution ,I guess there is some issue due to modular operations.
•  » » 19 months ago, # ^ |   -10 modular gcd is wrong
 » 23 months ago, # |   +10 I really loves this kind of editorials. This helps soo much!
 » 23 months ago, # |   -10 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.
 » 23 months ago, # |   +10 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.
 » 22 months ago, # | ← Rev. 4 →   -11 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
•  » » 22 months ago, # ^ |   +1 I did some wrong maths, and finally understood the solution. thanks.
 » 22 months ago, # |   0 anyone please tell me my mistake in problem C 156969000
•  » » 19 months ago, # ^ | ← Rev. 3 →   0 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.