### wuhudsm's blog

By wuhudsm, history, 4 weeks ago,

Thank you for participation and we hope you enjoy this round :)

Additionally, we sincerely invite you to join the unofficial round of TheForces Community tomorrow. Compete alongside many high-rated participants and earn your own rating in a our own rating system(TheForces Rating System)!

For more details, pls read https://mirror.codeforces.com/blog/entry/131733.

hint1
hint2
solution 1
solution 2
code(solution 1)

hint1
hint2
solution
Bonus
code

hint1
hint2
hint3
solution
code
fun fact

hint1
hint2
hint3
solution
code(greedy)
code(DP)

#### E Catch the Mole

hint1
hint2
hint3
hint4
solution1
solution2
bonus
code(hard version)

#### F Polygonal Segments

solution1
solution2
code(solution 1)
code(solution 2)
• +92

 » 4 weeks ago, # | ← Rev. 3 →   0 firstCan someone please tell me what the bait was for A? Was it that people thought the $\ge$ was $>$ so the answer is always yes?Nvm, I think I got it. Did people only count the frequency of the max number?
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   +10 I bit the bait.Got a WA just in first few minutes......(Yes,Only counting the largest number)
•  » » 4 weeks ago, # ^ |   +7 same here, at first only considered frequency of max number (;
•  » » » 4 weeks ago, # ^ |   0 oh wow! This was my first contest ever and I felt stupid after just ensuring that the max appears odd times. Same thing happened with B. Got the initial idea but couldn't combine the prefix and suffix sum construction. Is it down to just lack of practice? Any resources for me to start on :) ?
•  » » » » 4 weeks ago, # ^ |   0 Practice more and Think more:)
•  » » » » » 4 weeks ago, # ^ |   +3 LeetCode should learn to set contests like the way CodeForces do. 0 solved by chatGPT :)
 » 4 weeks ago, # |   0 anyone done C ...Can you tell where 271597372 nd 271626656 is wrong ??
•  » » 4 weeks ago, # ^ |   0 N<=2e5, your solution repeats at most N times the code in while-loop and you make 1 for-loop inside while-loop and another for-loop inside the first for-loop, so the time complexity is O(N^3) which is obviously too slow.
•  » » » 4 weeks ago, # ^ | ← Rev. 2 →   0 you use map inside the loops so the complexity is even O(N^3logN) not O(N^3)
•  » » » » 4 weeks ago, # ^ |   0 but in the second one its giving wrong answer not even TLE or I would have think of some other logic . also in second one I think the TC is good no ?? Can you tell me where the logic is wrong in second one ??
•  » » » » » 4 weeks ago, # ^ |   0 for(int i=1;i
•  » » » » » » 4 weeks ago, # ^ |   0 Thanks brooo..
•  » » » » » » » 4 weeks ago, # ^ | ← Rev. 2 →   0 You are welcome
 » 4 weeks ago, # | ← Rev. 5 →   -14 okay, i accept defeat
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   0 In the case that the sum becomes <= -1 at point x or y. Then the first time the sum is equal to the maximum will be at 1 or n instead of x or y. That's why you need to alternate between -1 and 1.
•  » » » 4 weeks ago, # ^ |   0 yeah got it, i had the intuition and had implemented it in one of my soln but my way of implementation was just unnecessarily complex and i am dumb so got it WA. anw bad day it was. thank you for your explanation.
 » 4 weeks ago, # |   -27 Nice brain teasers. Now where are the problems?
•  » » 4 weeks ago, # ^ |   +16 buddy, you got — ve contribution, 0 contests, has 1 problem solution, wtf? Brain teasers are the one for you (of course if you got one (brain)).
•  » » » 4 weeks ago, # ^ |   -10 you are green after 42 contests
•  » » » » 4 weeks ago, # ^ |   +6 Yeah its my original acc.
 » 4 weeks ago, # |   0 Thanks for editorial! I really liked problem C :)
•  » » 4 weeks ago, # ^ |   0 same here, C was good one, but can you please simply explain to me why we cannot get the answer if we perform the operation on array only once and then using one for loop and maths we calculate the answer.
•  » » » 4 weeks ago, # ^ |   0 The main reason is that we can only directly calculate the answer when the MAD operation is performed on a sorted array, since performing it on unsorted arrays leads to things like this: (as is evident, it doesn't work out)The main reason for this is because when we perform the MAD operation on an unsorted array, the resulting array may not follow the "rules" of the calculations (mainly that each value appears at least twice), whereas it will definitely follow the rules with a sorted array:It intuitively makes sense why this is, since in order for a new value to appear in any MAD array, it must appear at least twice in the original array. Since the input array is sorted, a new value must only appear strictly after its first appearance in the original array. So, each number in the MAD array must appear twice, which requires that the input array be sorted. Only once we know that each value appears twice can we use the trick to calculate the answer.Hope this helps! :)
•  » » » » 4 weeks ago, # ^ |   0 Thanks mate, got it now.
 » 4 weeks ago, # |   0 For E solution 2, I think it should say spoiler$\leq 70$ chains instead of $\geq 70$?
 » 4 weeks ago, # | ← Rev. 4 →   +45 Here is another solution for E (actually, I think there are a lot of ways to solve it): SolutionThe goal will be to find a path from the root to some leaf such that the mole definitely lies on this path. After that, you can binary search the location of the mole. Also, fix a constant $S$ and after constructing the path make some dummy queries such that the mole moved up at least $S$ times. Let's say we have constructed some of the path and the last node we added is $u$ — we will look at the children of $u$: If the height of a child $v$'s subtree is smaller than $S$ and the mole is initially there, then by the end the mole will definitely have moved up past $u$ and onto the already constructed path, so we don't care about it and we discard it If there is only one child that we didn't discard, we can add it to the path and continue Otherwise, query the relevant children sequentially. If the query's result is $0$, we discard the child (note that this can happen at most $\dfrac{N}{S}$ times, since the number of nodes in its' subtree is bigger than $S$), else we add it to the path and discard the rest of the children The final number of queries will be $max(S, \dfrac{N}{S}) + log_2 n$. By choosing $S = \sqrt n$ it becomes $\sqrt n + log_2 n$.Edit: After some thinking, the above calculation is a bit incorrect in some limit cases ( so it is slightly more than 100 :( ), but I think with randomization and choosing $S$ a bit lower than $\sqrt n$ it could be better. Anyways, there is still an upper bound of $2\sqrt n + log_2 n$.
 » 4 weeks ago, # |   0 For D, I have a binary search solution: 271626468
•  » » 4 weeks ago, # ^ |   0 Binary search works for problem E as well
 » 4 weeks ago, # |   +12 I had a different approach to E which I don't have proof for, but it managed to pass tests with $\le 160$ queries. СпойлерLet all nodes be "alive" or "dead" — initially, all are alive. Start at the root, and while the current node has exactly one alive child, go to that child. If it has no alive children, terminate this process. Otherwise, use dfs to find the subtree of the current node with the fewest alive children and query that subtree. If the mole is there, set the current node to that subtree, otherwise mark that subtree and all leaves in all other subtrees as dead (since the mole cannot be in any of those). I don't have proof that this guarantees a low number of queries (something like $\sqrt{n}$), but it seemed intuitively correct.At the end you are left with a path of possible locations for the mole, so it can then be caught with binary search.
•  » » 4 weeks ago, # ^ |   0 Isn't it right since $d \times w \le n$ where d = depth, w = width, and your algorithm would be $O(min(d, w))$ which is less than $\sqrt n$?
•  » » 4 weeks ago, # ^ |   +8 when you say using dfs to find the subtree of the current node with the fewest alive children you mean the subtree of a direct child right?
 » 4 weeks ago, # | ← Rev. 2 →   0 For Problem B, Can anyone please help me understand why my construction is wrong for the case 5 2 1my construction : 1 1 -1 -1 -1. Prefix max is at 2 and suffix max is at 1.Thank you.
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   +4 Suffix sum is max at 5 and 1 both so it will consider 5
•  » » » 4 weeks ago, # ^ |   0 Thank you so much. :facepalm:
•  » » 4 weeks ago, # ^ |   +3 the suffix max is -1and it occurs at indices 1, 5y should be the greatest index that satisfies $a_i+\ldots +a_n=\max_{j=1}^{n}(a_j+\ldots+a_n)$but the index 5 is the greatest here, that is why your solution is wrong
•  » » » 4 weeks ago, # ^ |   +1 Yes I got it. Thank you for the explanation.
•  » » » » 4 weeks ago, # ^ |   +1 you're welcome ^_^
•  » » 4 weeks ago, # ^ |   +1 Suffix is max at 1 and 5 also, and since we need to return maximum such index, so index 5 will be considered not 1.Hope you Understands
•  » » 4 weeks ago, # ^ |   0 I had the same doubt, and I think I did the same implementation as you, making the index >x and index < y all -1 and remaining other 1; Idk what was the issue until I saw this comment
 » 4 weeks ago, # |   0 Can someone tell me why is this wrong for B? 271591444
•  » » 4 weeks ago, # ^ |   0 For 5 2 1 you print 1 1 -1 -1 -1 Suffix max should be at 1 but here it's at 5
•  » » 4 weeks ago, # ^ |   0 consider this test case (from the above comment)n = 5, x = 2, y = 1your code outputs: 1 1 -1 -1 -1and this is wrong because the maximum suffix occurs on indices 1 and 5, while it should be occurs only in the index 1
•  » » » 4 weeks ago, # ^ |   0 Oh gotcha
 » 4 weeks ago, # |   +4 I find it interesting that a theforces organizer was 2nd place in div2. What are the odds some of the problems were proposed or seen for some theforces rounds? Not accusing anyone though. Just an observation.
 » 4 weeks ago, # |   0 In question A, how is it possible that the maximum number does not get condisered ? Foe Example if the numbers were 1 2 2 2 3 3. Then, Alice won cause there are 3 2s. But what if Alice chose 2 and then Bob chose 3. In the operations mentioned, we can choose a[i]>= what the opponent chose.Why is that Bob only chooses equal to Alicw?
•  » » 4 weeks ago, # ^ |   0 Alice chose 2 then Bob chose 3 Then again Alice chose 3 See?
•  » » 4 weeks ago, # ^ |   0 justice for bob xD.
•  » » 4 weeks ago, # ^ |   0 if every number occurs even number of times then, any number Alice will choose, Bob can mimic it and choose it againif there is a number that appears odd number of times, then Alice can choose it, forcing Bob to choose a number that occurs even number of times, now Alice can mimic Bob choices and win
•  » » » 4 weeks ago, # ^ |   0 Yeah but why should Bob even mimic. I mean its not even mentioned anywhere that Bob plays optimally. There DOES exist a winning strategy for Alice
•  » » » » 4 weeks ago, # ^ |   0 well, there does not exist a winning strategy for Alice, if she cannot win using this strategy somehow.let's say that bob won't play optimally, but he still can mimic Alice choices, right ?while there is a chance to Bob to win in Alice's winning strategy, then it won't be considered as a winning strategyI don't know why would Bob not to play optimally btw :)
•  » » » » » 4 weeks ago, # ^ |   0 Yeah I mean fair enough to assume that, but a special case IS a possible one too :)
•  » » » » » 4 weeks ago, # ^ |   0 exactly. this thought kept me from trying what actually the question wanted. maybe i'm thinking too much
•  » » 4 weeks ago, # ^ |   0 just another case 1 2 2 2 3. bob could have won in this but alice will win lmao!!I'm not trying to oppose anyone, just a curious doubt!!
•  » » » 4 weeks ago, # ^ |   0 No bob can't win cause alice will pick 3 directly.
 » 4 weeks ago, # |   0 What about this approach for E: SpoilerQuery centroid. If you get 1, solve recursively with centroid as root. If you get 0, remove subtree of centroid, and solve recursively from parent of current node (because mole could move up from where you are). You can also remove all current leaves (don't know if necessary).Won't this use approx log(n) queries?
•  » » 4 weeks ago, # ^ |   0 Consider a star graph, you never make progress
•  » » » 4 weeks ago, # ^ |   0 Hmm true. Then I got AC by having bad centroid code
 » 4 weeks ago, # | ← Rev. 2 →   0 I solved E by deleting a half of tree each query, so there is $O(\log(n))$ queries.In each query find a subtree with closest size to a half of the current tree. From current root, go to subtree with maximum size while the current subtree size is greater than a half. Query this subtree.Response 1. Set this subtree as a current tree.Response 0. Delete this subtree and all leaves from the current tree. Then add a parent of the root to the tree. This can be done in $O(n)$, so total complexity is $O(n\log(n))$.CODE
•  » » 4 weeks ago, # ^ |   0 Yes I realized this ended up being my solution, but in my head I thought of the subtree you find as the centroid. I wonder what kind of bound they potentially could have set for the number of queries.
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   +84 I think the problem is unsolvable in less than $O(\sqrt{n})$ queries. Consider the tree with the root having $\sqrt{n}$ chains of length $\sqrt{n} + 1$ attached to it. You have to at least know in which chain the mole is in, so you have to query each chain at least once, since the mole won't get to the root in $\sqrt{n}$ queries.
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   +11 this code works in sqrt(n) queries in the worst case this case is 4901 nodes adj[1]={2,3,...,71} adj[i]={i-70,i+70} for all i in [72,4831] adj[i]={i-70} for all in [4832,4901] and at each query you ask for a child between 2 and 71 and the response is 0 at the 70'th query you get the response you guess the correct answer in the some testcases in the 25-th test at 70 queries
 » 4 weeks ago, # |   +14 My solution 271646773 for E passes tests in $\le 100$ queries but I don't know why. I would appreciate it if anyone could prove some upper bound on the number of queries or provide a counter-example.The idea is to greedily choose a node that results in the minimum number of candidates in the worst case. Specifically, querying $x$ results in size[x] candidates if the answer is $1$ and (size[0] - leaf[0]) - (size[x] - leaf[x]) candidates if the answer is $0$. Here size[x] is the number of candidates in the subtree of $x$ and leaf[x] is the number of leaf candidates in the subtree of $x$.It's easy to compute these numbers for all $x$ with a simple dfs, after which I pick $x$ with the minimum value of max(size[x], (size[0] - leaf[0]) - (size[x] - leaf[x])). Finally, I repeat this process until only one candidate is remaining,
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   +3 Lemma 1: if B <= size[x] <= n - B for some $B$ then querying $x$ removes at least $B$ candidates, where $n$ is the current number of candidates. To prove it formally, note that (size[0] - leaf[0]) - (size[x] - leaf[x]) = = (size[0] - size[x]) - (leaf[0] - leaf[x]) <= size[0] - size[x] <= n - B Lemma 2: if size[x] < B or size[x] > n - B for all $x$ then there exists a node $p$ with size[p] > n - B and size[c] < B for every child $c$ of $p$. To prove it, note that the subtree size of the root is $n > n - B$ and the subtree size of any leaf is $1 < B$, so there must be a transition point in between.Lemma 3: if size[x] < B or size[x] > n - B for all $x$ then the tree has at least $\lceil\frac{n}{B}-1\rceil$ leaves. To prove it, consider node $p$ from lemma 2. It has at least $\frac{n-B}{B-1}$ children because its subtree size is large but all children have small subtree sizes so there must be quite a few of them. $\frac{n-B}{B-1} > \frac{n-B}{B} = \frac{n}{B} - 1$. All numbers are integers so we can take $\lceil \cdot \rceil$ of the last expression.Lemma 4: if there are at least $C$ leaves then querying one of them removes at least $C$ candidates. If the response is $1$ then we found the mole, and if the response is $0$ then all $C$ leaves are no longer valid candidates.Choosing $B = \sqrt{n}$ means that we remove roughly $\sqrt{n}$ nodes per query (where $n$ is the current number of candidates), and hence the greedy process results in $O(\sqrt{n})$ queries overall.
 » 4 weeks ago, # | ← Rev. 2 →   0 Can anyone explain me how to solve B plzz :(, i might have lost my mind after today's contest
•  » » 4 weeks ago, # ^ | ← Rev. 3 →   0 x is the first time we have sum as max from start and y is first time we have sum as max from end .so after x and before y keep -1 to ensure max sum wont increase if you make sum as 0 or -1 for indices which are not in x,y then your done
•  » » » 4 weeks ago, # ^ |   0 Oh thanks now i got it
•  » » 4 weeks ago, # ^ |   0
•  » » 4 weeks ago, # ^ |   0 look onto my submission for B
 » 4 weeks ago, # | ← Rev. 2 →   +11 Personal Editorial that focuses mostly on intuitionA:Basically, Alice can always pick the largest element a_i such that count[a_i]%2==1. No matter what Bob picks, Alice still wins. If that element doesn't exist Alice loses. This was a pretty hard Div 2 A in my opinion.B: I started by thinking that we want to limit the maximum sum or in other words we don't want the prefix sum to get any larger after X or the suffix sum to get any larger before Y. The obvious construction is [-1,-1,...,y,1,1,...,x,-1,-1,...] The problem is that it might be the case that the prefix sum of -1 (the first element) is the larger than the first x elements (the same might be true for the suffix sum). To avoid that, we notice that we can alternate between -1 and 1 at the ends. The construction is as follows: [...,-1,1,-1,Y,1,1,...,1,1,X,-1,1,-1,...] This solves both problems.C: We try testing the operation on the array to see what happens. The two key observations are that the first operation makes the array increasing, and the second operation shifts the array to the right by 1. The solution then becomes pretty much just math. We use the operation once, and then we use math to calculate the answer. D: I didn't have time to write the AC code during the contest, but the approach is actually very simple — too simple in my opinion for a Div 2 D. The key observation is realizing that if a[i] is large the only operation that makes sense is to fill the whole row. If it takes more than two operations to fill a row with white with 2x2 squares, we might as well just fill both the ith and the ith+1 row with white. We also notice that there are two cases where using 2x2 squares are beneficial. Case 1: a[i] <=2 and a[i+1]<=2 Case 2: a[i]<=2 and there is an even number of 3 <= a_x[i] <=4 followed by an a_y[i] <=2. In both cases our answer goes up by one.
•  » » 4 weeks ago, # ^ |   +12 Why the negative contribution? I'm genuinely curious. I'm gonna write them either way because it helps me get better at explaining things, an important life and interview skill, and also because it might help some people.
•  » » 4 weeks ago, # ^ |   +1 I genuinely thank u for sharing the way you think. I am suck at thinking constructive problems and your comment really helps me to build a certain way to think. Keep contributing! Don't let these downvotes upset u.
•  » » 4 weeks ago, # ^ |   +2 In problem B, actually i came up with only [-1,-1,...,y,1,1,...,x,-1,-1,...] this and can't able to think further. Btw now understood completely thanks :)
 » 4 weeks ago, # |   0 For B problem if test is 5 2 1 is [ 1 1 -1 -1 -1] consider to be wrong answer ?
•  » » 4 weeks ago, # ^ |   0 yes, because the maximum suffix position of the array that you have given is 5
•  » » » 4 weeks ago, # ^ |   0 Yes, but this test case satisfies the condition for maximum subarray sum, doesn't it?
•  » » » 4 weeks ago, # ^ |   0 Thanks it was annoying me
 » 4 weeks ago, # |   0 For F solution2, I think the pseudocode should have 2a[mxp] <= instead of 2a[mxp] >=.
 » 4 weeks ago, # | ← Rev. 2 →   +6 I am here to provide yet another solution to E that I cannot prove the query ammount. SolutionIf you choose a node and the answer is 0 you can ignore that node, its subtree and after that all the leaves. If the answer is 0 then in the end the mole will be either in its subtree or the path to the root, so you can remove all the other nodes.This idea would lead to searching for a centroid like node that reduces the tree as much as possible. Intuitively there should always be a node that reduces the tree to about $\frac12$ of the original size.I think it comes up to $O(\log N)$ queries, and $O(N)$ time if implemented correctly. (edit: After checking other comments I can see why $O(\log N)$ queries is impossible)
•  » » 4 weeks ago, # ^ |   0 Yay, I had the same solution =)But I added an additional condition: if you can't find the centroid — 'the node with the smallest subtree size that contains at least half of the remaining nodes of the current node's subtree and is not equal to the current node' — I chose the biggest child of the current node.current node — the last node that contained the answer in it's subtree.
 » 4 weeks ago, # |   +33 E2 with $100$ queries hint 1You can cut down (at least) $101-i$ vertices in the $i$-th query. Then, $\sum^{100}_{k=1} k = 5050 \ge n$. hint 2(almost the solution)You can cut down a subtree with the depth of $100-i$ in the $i$-th query. answerChoose a subtree with the depth of $100-i$ (at least $101-i$ vertices in there) in the $i$-th query. If you found, ask the same root until not found. If not, cut down the subtree. If there are no such trees, you must choose the root and ask them. Finally, the mole reachs the root before using up of the query. bonus 2How less queries can we go?
•  » » 4 weeks ago, # ^ | ← Rev. 3 →   +20 i solved the problem in at most 70 queries (sqrt(n)) if we denote by size[node] the number of possible location in the subtree of "node" and we denote by size_valid the number of possible locations if we ask about the node that minimizes abs(size[node]-size_valid/2) if the response was 1 : so size_valid will be size[node] because the location will be in the subtree of node if the response was 0 : so size_valid will be size_valid — the number of possible locations that hasn't any child that can be possible + 1 if the lca of all possible nodes isn't the root in the worst case childs of the lca of the possible nodes has the same size: size[node] in the worst case size[node] will be sqrt(size_valid) for sqrt(size_valid) nodes and size_valid after each query will decrease by at least 2*sqrt(size_valid)-1 (sqrt(size_valid) for the subtree of the choosen node and sqrt(size_valid)-1 for the nodes that hasn't any child that can be possible location else it will decrease by x+size_valid/x-1 with the same logic ) so if n can be solved in sqrt(n) than n-2*sqrt(n)+1 can be solved in sqrt(n-2*sqrt(n)+1)=sqrt(n)-1 so for n=5000 only 70 queries can be enough
•  » » 4 weeks ago, # ^ |   0 If you found, ask the same root until not found. How do you do this? If the answer to a query is $1$ then the mole doesn't move
•  » » » 4 weeks ago, # ^ | ← Rev. 2 →   0 sorry, please consider subtree as strictly subtreeUPD: I was wrong, fixed my solution is under the reply tree.
•  » » 3 weeks ago, # ^ |   0 Could you explain in detail that how we can 'ask the same root until not found'? Thanks! My question is the mole doesn't just stop at the root you pick, so we have to use binary search for the real position.
•  » » » 3 weeks ago, # ^ |   0 During asking the same node, if the result changes 1 to 0, the mole will be in the parer of the node, so answer there.
•  » » » » 3 weeks ago, # ^ |   0 But the mole doesn't move if the result is 1. So how can the result become 0 if we keep asking the same node?
•  » » » » » 3 weeks ago, # ^ | ← Rev. 2 →   0 Sorry, I answered as the inverted version(originally the outcome was inverted, but during testing the outcome is current style).If the answer is 0, cutting down the subtree is the same.(In this step, we can also cut all the leaves) If the answer is 1, now we have a tree atmost depth $100-i$, rooted by $v$.Now, ask sons in the order of decreasing the depth. If we receive 1, do the same thing. Note that, if we receive 0, all leaves are disappeared so we shouldn't care about small subtrees and we must look up atmost $O(\sqrt{n})$ sons.Finally, if we gets lost(no such subtree found), we can identify the path the mole is in(from $v$ to the parents), so do binary search.I think this fits in $100$ queries, but sorry if I'm wrong.
 » 4 weeks ago, # |   +6 I'm still traumatized from A
 » 4 weeks ago, # |   +1 Could anyone explain why 271582281 fails on the 3rd test case?
•  » » 4 weeks ago, # ^ |   +1 Never mind, I got it.
 » 4 weeks ago, # |   0 I am really confused. I have used the even and odd approaches. If the n is odd then it is clear that Alice will win. example: 1 2 3 4 5 5 6 A B A B A B AIf n is even, then there would be 2 cases:Case 1: The frequency of maximum numbers is odd. example: 1 2 3 5 5 5 A B A Hence, Alice will win.Case 2: The frequency of the maximum number is even. example: 1 2 3 4 5 5 A B Hence, Alice will lose.This is the approach I applied but I got the wrong answer. Could you guys please tell me, what is wrong with my approach?
•  » » 4 weeks ago, # ^ | ← Rev. 3 →   0 Your reasoning for case 1 is correct.Your reasoning is faulty in case 2. Take the test case:1 2 3 3 3 3 You would say that Alice would lose because N is even and the frequency of the maximum element is even. However, if Alice chooses 2 in her first move she can win because then Bob goes first and they alternate picking 3s.Alice loses iff the frequency of all elements is even because as explained in the editorial Bob can mirror all her moves. In any other case Alice can force Bob into this situation if there is at least one odd frequency element by selecting the last odd element as her first move.
•  » » » 4 weeks ago, # ^ |   0 Thank you!I should have practiced more.
 » 4 weeks ago, # |   0 orz round
 » 4 weeks ago, # |   +1 C, D is brilliant!
 » 4 weeks ago, # |   0 Got baited by A, thought that only the parity of frequency of maximum element mattered.
 » 4 weeks ago, # | ← Rev. 2 →   0 Can anyone please explain why this code 271651820 for problem C giving wrong answer. I tried to do it with one operation and after this if mad value appears more than once , it will right shift in further operation otherwise if mad value appears only once, it will add once to the answer.
•  » » 4 weeks ago, # ^ |   0 If a mad value appears only once, it will not only add once to the answer but also turn into its neighbor on the left during the consequent operations.
•  » » » 4 weeks ago, # ^ |   0 hey, i'm facing the same problem as him, can you provide testcase for this mad value only once case please. I didn't understood.
•  » » » » 4 weeks ago, # ^ |   0 Try this testcase : 4 3 1 1 1 3 4 5
•  » » » » » 4 weeks ago, # ^ |   0 yeah, i got it. Thank you very much!
 » 4 weeks ago, # |   0 I have another solution for E1. my solution in chinese :)
 » 4 weeks ago, # |   +19 In problem F, solution 1: We notice that a local maximal polygon segment $[l,r]$ must satisfy $\min(a_l−1,a_r+1)\ge \mathbf{2}(a_l+...+a_r)$. (or $l=1,r=n$). shouldn't it be: ...must satisfy $\min(a_l−1,a_r+1)\ge (a_l+...+a_r)$. Is the extra "2" a typo?
•  » » 4 weeks ago, # ^ |   +5 Can you please explain this formula? How can we transform: a(l) + a(l + 1) + .. + a(r) > 2 * max(a[l..r]) (original condition to form a polygon I guess?) to that? Thanks
•  » » 4 weeks ago, # ^ |   0 I am so confused about this, it that $\min(a_l-1,a_r+1)$ but not $\min(a_{l-1},a_{r+1})$? The author writes the latter. However, I still think both of them are confusing. I think $(a_l+\cdots +a_r)>2\max{a_l,\cdots,a_r}$ works.
•  » » » 3 weeks ago, # ^ |   0 The condition in the editorial is neccesary but not sufficient. However, since there are only $\log V$ "key points", it is quite enough for us to use.
•  » » 3 weeks ago, # ^ | ← Rev. 2 →   +5 I think so. The necessary and sufficient condition for judging whether ${a_1,\ldots,a_n}$ is a "polygonal segment" is $\forall 1\le i\le n, a_i< \left( \sum_{j=1}^{n}a_j \right) -a_i$. We can obtain the necessary and sufficient condition for the "polygonal segment" $[l, r]$ to not be further expanded as $\left[\left(l=1\right) \vee \left(a_{l-1}\ge \sum_{i=l}^{r} a_i\right)\right] \wedge \left[\left(r=n\right) \vee \left(a_{r+1}\ge \sum_{i=l}^{r} a_i\right)\right]$.
 » 4 weeks ago, # |   0 In problem B, I don't understand why the first construction doesn't work. i.e. 1 in the common range, and -1 in the remaining positions. The condition was simply that the prefix sum should be maximum at position x and not any position greater than x, and the suffix sum should be maximum at position y and not any position smaller than y. This construction satisfies it perfectly. What is the need for alternating -1 and 1?
•  » » 4 weeks ago, # ^ |   0 Ah nevermind, the sum might not ever become positive, in which case the condition isn't satisfied.
 » 4 weeks ago, # |   0 I need help in C, What am i missing 271697251
 » 4 weeks ago, # |   0 LeetCode should learn to set contests like the way CodeForces do. 0 solved by chatGPT :)
 » 4 weeks ago, # | ← Rev. 2 →   0 done
 » 4 weeks ago, # |   0 can someone explain the funfact on c?
•  » » 4 weeks ago, # ^ |   +3 Maybe it's referring to doing the naive 'mad' simulation twice, and then just summing up once.
 » 4 weeks ago, # | ← Rev. 2 →   0 can someone please tell me why is this code giving tle for problem c? link
 » 4 weeks ago, # | ← Rev. 2 →   0 How to solve B if The maximum prefix position of b is the largest index i that satisfies ... The maximum suffix position of b is the smallest index i that satisfies ...
 » 4 weeks ago, # |   +1 I think I've solved E in 100 queries,heres my submission:submission.
 » 4 weeks ago, # |   0 Amazing Fun Fact about Task3
 » 4 weeks ago, # | ← Rev. 3 →   0 Can anyone explain the solution 1 of F which store some information in one node in Segment Tree? I don't really understand what we have to store, and how we use it to get the answer.
•  » » 10 days ago, # ^ |   0 Hello! I just finished upsolving it, here's my code: 274583614. Search for prefix_t to skip the template.Let's call an element prefix peak if it is greater than a corresponding prefix sum. Define suffix peaks similarly. Pad the subarray with positive infinities on both ends, they are also peaks. Store a tuple (prefix length, sum, maximum, peak) for each peak. Let's call a vector of such tuples prefix info. Define suffix info similarly. You need a few operations: extend prefix info of the left segment with prefix info of the right segment to form prefix info of the combined segment; extend suffix info of the right segment with suffix info of the left segment to form suffix info of the combined segment (same as 1); combine suffix info of the left segment with prefix info of the right segment to update the answer. Operation 3 can be tricky to implement in linear time ($log^2$ overall) with two pointers, so I implemented it naively in quadratic time ($\log^3$ overall) to stress test but it passed comfortably in 3 seconds :| Disappointing preparation from the setter considering that most solutions are within a factor of 4 of my execution time whereas $\log = 40$.
 » 4 weeks ago, # |   0 For Problem B:Question says : It can be proven that such an array always exists under the given conditions. How do we prove that answer always exists ? Can someone help me understand this ? Thanks in Advance.
 » 4 weeks ago, # |   0 Can someone please explain the alternate solution for A using dp? Also, what does the author mean when he writes =∼? Thanks!
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   0 For dp[i], Alice is faced with the array a[1:i], where a is non-increasing. Transition Let the indices of the last occurrences of the elements in array a[1:i] from left to right be {i_dk,....,i_d2,i_d1,i_d0}. This is according to the editorial's notation. Also, note that i_d0 = i. Think of the picks Alice (1st player) can make. If he picks any element with value equal to a[i], then we transition to bob facing dp[i-1]. More generally if he picks some element with value a[i_dj] we transition to bob facing dp[i_dj -1]. For alice to win from dp[i], it's enough for bob to loose from dp[i_dj -1] for some j. Thus, we can take the negation(~) of the and(&) over all dp[i_dj -1], as a single false state (from where bob is guaranteed to loose) is enough for Alice to win. Hope I didn't complicate it too much. And, =~ just means we are taking negation of RHS, and assigning it to the LHS.
•  » » » 3 weeks ago, # ^ |   0 Brilliant!
 » 4 weeks ago, # |   0 can someone please answer this.... for Problem D, In shayan's video solution, dp[i][j], j={0,1,2,3} what is the j here ? , is it {00,01,10,11} where each boolean value tell us about the use of the 1st and 2nd 2x2 block in i_th row ?
 » 4 weeks ago, # |   0 I was a bit confused for C where i did one operation and did the same contribution idea (n-i)*a[i]. I am not sure why it is failing there but getting accepted if we do 2 operations. while one operation is sufficient for making the array increasing acquiring required elements.can anyone help me to understand? Thank You
•  » » 4 weeks ago, # ^ |   0 While the array may be increasing, some of the elements might only have a frequency of 1 which means they will be erased in subsequent operations. 2 operations ensures that the count of every element is >=2
•  » » » 4 weeks ago, # ^ |   0 can you give an example.. i tried hard for finding a case where this assumption fails
•  » » » » 4 weeks ago, # ^ | ← Rev. 2 →   0 Sure.[2,3,1,1,2,3] With 1 operation it is [0,0,0,1,2,3]with 2 operations it is [0,0,0,0,0,0].
•  » » » » » 3 weeks ago, # ^ |   0 Thank you mate. I got it now since after the second operation only it becomes a right shift for the next iterations until all becomes zero. I missed that and only considered one operation might be enough.
 » 4 weeks ago, # |   0 What do we mean by "left most row" is editorial of problem D. Rows run horizontally shouldn't they be top or bottom. Can anyone help i am confused.
•  » » 4 weeks ago, # ^ |   0 "left most row" --> means absolutely left of any row (or from beginning of any row) example: if [a1,a2,.....an] representing a row , then a1 is leftmost, a2 is next leftmost,....
 » 4 weeks ago, # |   0 For bonus in B, the array exists for y <= x case or not??
 » 4 weeks ago, # |   0 brainlet solution on problem D. 271773223 no dp, no extra variable. proof: AC
•  » » 4 weeks ago, # ^ |   0 In problem D in which testcase my code is failing , please help! 271787469
 » 4 weeks ago, # |   0 C > B > D gg contest the most stupid D problem of all contest
•  » » 4 weeks ago, # ^ |   0 271787469 Can you please help me in which testcase my code is failing :(
•  » » » 4 weeks ago, # ^ |   0 3 1 3 1 expect 3 found 2 
•  » » » » 4 weeks ago, # ^ |   0 Oh thanks man :)
 » 4 weeks ago, # |   0 can someone explain dp transition on dp solution for D? plz
 » 3 weeks ago, # |   0 I have a few doubts in the solution 1 of the editorial for E. Firstly, why do we choose 50? It seems that we should be taking $\sqrt{n}$, so 70 should be ideal right? Is there something special about 50, because I saw another comment below which says that using a number slightly smaller than $\sqrt{n}$ is better and I didn't understand the reason behind that either. Additionally, in the 3rd case, when there's no vertex with $maxdep_v - dep_v = 50$, then we only need at most 50 moves right, why does it say 100 moves then?
•  » » 3 weeks ago, # ^ | ← Rev. 2 →   +5 I figured taking Sqrt(n) is ideal for solving E2, because you'll need N / 70 + 70 + logN operations(though due to weird constants you still need to optimize binary search by cutting down to r = mid — 2), Then I believe it is optimal to choose K=50 as a constant only in E1 cuz choosing 70 exceeds allowed operations: N / 70 + 2*70 > 200As to the 3rd case, yeah you only up to 50 moves after optimization
•  » » 3 weeks ago, # ^ |   0 When we drive away this mole once, we need to immediately check if it is still in the subtree v. So it is $50 \times 2$ moves.
 » 3 weeks ago, # |   +5 Can someone explain this part of sol2 for E?Then the tree can be split into ≤70 chains.
•  » » 3 weeks ago, # ^ |   +5 We query any leaf $70$ times, then delete all nodes $x$ such that $maxdep_v-dep_v+1<=70$. So if a chain is still alive after the deleting, there must be at least 70 deleted nodes underneath it.
 » 3 weeks ago, # |   +6 An approach for bonus of EConsider all the nodes that the mole can be one. These lie on a single path from leaf to the initial node of mole. If we can find this path then we can find the mole in O(log n) operations. To find this path consider the following: 1. We know that root node (node 1) lies on this path. 2. For each node that lies on this path exactly one of its children lies on the path.Let numJumps be the number of operations where jury has returned 0, that is number of times mole has jumped up.Now start tracing the path from root. Let's call the set of all children where maxDepth — depth >= numJumps candidates for our path extension. If candidates is empty, we are at end of our path. Otherwise while candidates has more than one node, remove the node with minimum maxDepth — depth value and query it. If judge return 1, we move to this node and proceed tracing our path recursively. If judge returns 0, we discard this node, increment numJumps and remove all nodes that have maxDepth — depth < numJumps.At the end if we are left with exactly one node in candidates we move to this node.To calculate the number of operations required, notice that first time we query at least 1 node is discarded, second time atleast 2, and so on.If judge returns 0, then chain is discarded and size of numJumps increases meaning next chain to be discarded must have maxDepth — depth atleast 1 more that cur node's maxDepth — depthIf judge returns 1, notice that there must be atleast one more node with maxDepth — depth at least equal to this node's maxDepth — depth. Meaning at least half of nodes under consideration were discarded, considering single chains with no branching.Thus nodes under consideration either reduce as 1, 2, 3, ... or half. Either way after k moves, atleast k * (k + 1) / 2 nodes will be removed from nodes under consideration. Meaning after atmost 71 moves we will have completed our path.Binary search on path will take at most log n moves, that is around 13.Thus we take atmost 71 + 13 = 84 moves.Submission: Submission for the above approach #include using namespace std; //#pragma GCC optimize("Ofast,unroll-loops") //#pragma GCC target("avx,avx2,avx512,fma") template ostream& operator<<(ostream &os, const pair &p) { return os << '(' << p.first << ", " << p.second << ')'; } template::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { os << '{'; string sep; for (const T &x : v) os << sep << x, sep = ", "; return os << '}'; } void dbg_out() { cerr << endl; } template void dbg_out(Head H, Tail... T) { cerr << ' ' << H; dbg_out(T...); } #ifdef LOCAL #define dbg(...) cerr << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__) #else #define dbg(...) #endif #define ll long long #define ld long double #define PI 3.1415926535897932384626433832795l // -------------------------------------------------- // RANDOM NUMBER GENERATOR mt19937 RNG(chrono::steady_clock::now().time_since_epoch().count()); #define SHUF(v) shuffle(all(v), RNG); // Use mt19937_64 for 64 bit random numbers. vector> adj; vector depth; vector maxDepth; vector par; vector path; int numOperations = 0; int numJumps = 0; int query(int x){ ++x; cout << "? " << x << endl; int res; cin >> res; if(res == 0){ ++numJumps; } ++numOperations; return res; } void answer(int x){ ++x; cout << "! " << x << endl; } void dfs(int u, int p){ for(int v: adj[u]){ if(v != p){ depth[v] = maxDepth[v] = depth[u] + 1; par[v] = u; dfs(v, u); maxDepth[u] = max(maxDepth[u], maxDepth[v]); } } } void tracePath(int u){ path.push_back(u); stack candidates; for(int v: adj[u]){ if(v == par[u]){ continue; } if(maxDepth[v] - depth[v] < numJumps){ continue; } candidates.push(v); } while(!candidates.empty()){ int v = candidates.top(); candidates.pop(); if(maxDepth[v] - depth[v] < numJumps){ continue; } if(candidates.empty() || query(v)){ tracePath(v); return; } } } bool cmp(int a, int b){ return (maxDepth[a] - depth[a]) < (maxDepth[b] - depth[b]); } void solve() { int n; cin >> n; adj = vector>(n); depth = vector(n, 1); maxDepth = vector(n, 1); par = vector(n); path.clear(); numJumps = 0; numOperations = 0; for(int i = 0; i < n - 1; ++i){ int u, v; cin >> u >> v; --u, --v; adj[u].push_back(v); adj[v].push_back(u); } dfs(0, -1); for(int u = 0; u < n; ++u){ sort(adj[u].rbegin(), adj[u].rend(), cmp); } tracePath(0); int l = 0; int r = path.size() - 1; while(l < r){ int mid = (l + r + 1) / 2; if(query(path[mid])){ l = mid; } else{ r = mid - 1; l = max(0, l - 1); r = max(0, r - 1); } } answer(path[l]); assert(numOperations <= 84); } int main() { int tc; cin >> tc; for(int t = 1; t <= tc; ++t){ solve(); } return 0; } 
 » 3 weeks ago, # |   +3 For solution 2 on F, I'm pretty sure you can store a max segtree for the last time each position was updated, and in the map store also store when the range was added. Then when you visit a range just check whether you need to recompute it in log N and then recompute if you have to. I think this doesn't increase the complexity because an interval tree is already n log^2 n to update...?
 » 3 weeks ago, # | ← Rev. 2 →   0 This solution of mine is getting WA for problem D. Can anyone point out the reason? 271964225I'll explain my approach. I have followed greedy method. I have initialized the minimum no. of operations 'n' since it is always possible.Now iteratively I am checking for each row the no. black cells, if it is >4 continue else if it's ==0 operation req decreases by one.My approach is like we can decrease the operations req only when the count of black cells encountered is <=2 && !=0 if so, and the next row is <= 2 && != 0 decrease the operation req by one and move to i+2, if not then minimum of next 2rows should >2 && <= 4 and the next row(i+3 here) should >=2 && != 0 then we can decrease operation req by one as we can use only 1st option in these rows to make them all white and move to i+4.
 » 3 weeks ago, # |   0 Uneven problems
 » 3 weeks ago, # |   0 I had a general question for interactive problems, I've seen a lot of problems mention whether the interactive is adaptive or not, I wanted to understand if this makes any difference to the solution. In this contest for example, for E1 and E2 it said that the interactor is not adaptive, but from what I understand, even if it was adaptive, that wouldn't have changed the solution in any way right? What's exactly the purpose of mentioning this then?
 » 3 weeks ago, # | ← Rev. 2 →   0 Can anyone explain, please, why we cant solve problem C simply implementing the algorithm?My observation was that number of 0's after each operation grows exponentially, so there will be no more log(n) iteration. Recalculating next iteration of the array will be O(n), times std::map operation to find the most frequent element is O(log(n)) times O(log(n)) total operation result in O(n*log^2(n)) opearions that should pass TL.Also for some reason my implementation gives WA 272048767. Why so?
•  » » 3 weeks ago, # ^ |   0 I read the problem worng. Nevermind
 » 3 weeks ago, # |   0 can anyone tell me why this code doesn't work for E1? https://mirror.codeforces.com/contest/1990/submission/273122031I can't tell whether it is an implementation issue, or my algorithm is incorrect. Thanks (see find() function for the main logic)
 » 3 weeks ago, # |   0 someone tell me whats wrong with this solution for C?273115595
 » 2 weeks ago, # |   0 For the problem 1990B - Array Craft, I am setting all the elements in the segment $a[y,...,x]$ equal to $1$ and all the remaining elements as $-1$. In this way, the $presum_{y-1}$ is $negative$ as well as the $postsum_{x+1}$ is also $negative$. Therefore, the $\textbf{maximum presum}$ will be at the index $x$, because all the elements after it are $-1$, which will decrease the presum.Similarly, the $\textbf{maximum postsum}$ will be at the index $y$. wuhudsm What is wrong with this approach?
 » 2 weeks ago, # |   0 For problem E, I just query the subtree that has the most possible nodes less than half of the amount every time. https://mirror.codeforces.com/contest/1990/submission/273813620
•  » » 8 days ago, # ^ |   0 It was really helpful thnx.
 » 9 days ago, # |   0 My submission for problem C shows TLE for TC 15, I basically tried to simulate the process given in the problem statement using maps but am unable to come up with a mathematical equation in order to not run an unnecessary "while(mp.size()!=0)". Here's my submission to the problem : 274692750. Can someone please help me out? Tia
 » 9 days ago, # |   0 can someone please explain , where my solution for c went wrong?. My_sollutionwhat I did was after first process if there are some consecutive numbers in array with same value of length greater than 1. they are going to exist in array till they get completely shifted out of the array.so I added it's value to sum as length*(number of rounds this length will be sustained-1)*value + ((length)*(length+1)/2)*value (because after reaching end length will start to decrease by 1).and for length ==1 I just added to sum only once because they will be removed after next process.
 » 4 days ago, # | ← Rev. 3 →   0 .ComplaintFrame { display: inline-block; position: absolute; top: 0; right: -1.4em; } .ComplaintFrame a { text-decoration: none; color: #ff8c00; opacity: 0.5; } .ComplaintFrame a:hover { opacity: 1; } ._ComplaintFrame_popup p, ._ComplaintFrame_popup button { margin-top: 1rem; } ._ComplaintFrame_popup input[type=submit] { padding: 0.25rem 2rem; } ._ComplaintFrame_popup ul { margin-top: 1em !important; margin-bottom: 1em !important; } please explain solution one