zltzlt's blog

By zltzlt, history, 7 weeks ago,

Thank you for participating! Sorry for being much harder than usual Div. 2 :( But we still hope you find some of our problems interesting.

Rating predictions (Inspired by sum's editorial)

1981A - Turtle and Piggy Are Playing a Game

Idea: zltzlt

Hint 1
Hint 2
Solution
Code

1981B - Turtle and an Infinite Sequence

Idea: zltzlt

Hint 1
Hint 2
Solution 1
Solution 2
Code for Solution 1
Code for Solution 2

1981C - Turtle and an Incomplete Sequence

Idea: zltzlt

Hint 1
Hint 2
Solution
Code

1981D - Turtle and Multiplication

Idea: sinsop90

Hint 1
Hint 2
Solution
Code

1981E - Turtle and Intersected Segments

Idea: zltzlt
Developed by 244mhq.

Hint 1
Hint 2
Solution
Code

1981F - Turtle and Paths on a Tree

Idea: yinhee
Developed by 244mhq and zltzlt.
Thanks AFewSuns and crazy_sea for discovering Solution 2, which runs faster than Solution 1!

Hint 1
Hint 2
Solution 1
Solution 2
Code for Solution 1
Code for Solution 2
• +250

 » 6 weeks ago, # |   +20 Auto comment: topic has been updated by zltzlt (previous revision, new revision, compare).
 » 6 weeks ago, # |   +16 Look at the standings. It seems your F is too hard for a div2 so it works like a 5-problem round. Is that good?
•  » » 6 weeks ago, # ^ |   +63 I will elaborate on that.You're right, it wasn't expected and that's mostly my fault -- I was able to come up with $O(n^2)$ solution pretty easily and thought that a lot of people will think about solution $O(n \cdot bound)$ after some time. In general, I don't want for last problem to be that hard and I will try to listen to feedback of other people more carefully. I still hope that people had fun thinking about this problem (and others problem of the round).And one more point -- we intentionally didn't put in pretests tests where you need to use very big value of bound (maximum one that zltzlt was able to construct was around 3k and you can pass pretests with around 1k). I also want to elaborate on that. In general, I would vote for pretests to be as strong as possible, but here it was kinda special -- we didn't want people to try to squeeze solutions just with pure guessing (and since I've underestimated the problem, I thought that a lot of people will try to do so), that's why I agreed to not use such tests into pretests. In retrospect, I would insist on putting them (because problem already turned out to be too hard), and I fell sorry for maspy, congratulations on the win though!
•  » » » 6 weeks ago, # ^ | ← Rev. 2 →   +78 I proved that the required upper bound is $O(N / \log N)$, but because creating a test case that achieves that upper bound also seemed non-trivial, I didn't seriously consider the constant factor. I ended up submitting with a slightly conservative estimate, taking into account the possibility of tight TL or ML. (Also, since the pretest succeeded with a limit of 1K, I submitted with a limit of 2K.)While it might have been better to have some cases in the pretests closer to optimality, I think it's great that there were test cases in the system tests that required quite large upper bounds. Thanks for preparing a good contest!
•  » » 6 weeks ago, # ^ |   +27 look at the tester predictions, it is hard to be very accurate in predicting difficulties. F isnt very relevant for div2'ers anyways (only about 10 solve an average F?) that numbeer only decreased by 10.
•  » » » 6 weeks ago, # ^ |   -20 F isnt very relevant for div2'ers anyways So, why are they in div2 contests?
•  » » » » 6 weeks ago, # ^ |   +26 to give div2 people a harder problem to upsolve
•  » » 6 weeks ago, # ^ |   +33 A problem having no solve is different from not having a problem.Do you think everyone who didn't solve that problem just quit after solving 5 problems?
 » 6 weeks ago, # |   +8 Sorry for wrongly predicted the difficulty of problem F. As the writer, I wrongly predicted the difficulty to solve O(n^2) sol as well as calculating the maximum of MEX. So as is said above, guys can just consider it as a joke now:(
 » 6 weeks ago, # | ← Rev. 2 →   -8 Very surprised this didn't pass D:https://mirror.codeforces.com/contest/1981/submission/263490566Time complexity should be $O(Nlog\sqrt{N})$Edit: nvm I forgot to consider that it was multi-tested
 » 6 weeks ago, # |   +30 problem C has quite a bit heavy implementation.
•  » » 6 weeks ago, # ^ |   0 Not really, it took me about 20 minutes to implement.
•  » » 6 weeks ago, # ^ |   0 In thought it is hard to implement but in code not really. Using bitmask simplify it.
 » 6 weeks ago, # |   +56 C has a significantly simpler $\mathcal O\left(n \log\left(n\right)\right)$ solution. Notice that instead of stopping at the LCA, if the path has missing entries, it is valid to continue farther up the tree. The path only has to stop when it runs out of missing entries or it reaches the root. Therefore, assuming at least one entry is not missing, a simple solution is to repeatedly choose the largest entry $x$ with missing neighbors and replace those missing neighbors with $\left\lfloor\frac x2\right\rfloor$ (or $2$ if $x = 1$). This can be implemented in about 20 lines with a priority queue: Implementationint n; cin >> n; vector A(n); for (int &a : A) cin >> a; if (*max_element(begin(A), end(A)) < 0) A[0] = 1; priority_queue> Q; for (int i = 0; i < n; i++) if (A[i] >= 0) Q.emplace(A[i], i); while (!Q.empty()) { auto [a, i] = Q.top(); Q.pop(); if (i > 0 && A[i - 1] < 0) Q.emplace(A[i - 1] = a == 1 ? 2 : a / 2, i - 1); if (i < n - 1 && A[i + 1] < 0) Q.emplace(A[i + 1] = a == 1 ? 2 : a / 2, i + 1); } for (int i = 1; i < (int)size(A); i++) if (A[i] / 2 != A[i - 1] && A[i - 1] / 2 != A[i]) A = {-1}; for (int a : A) cout << a << ' '; cout << '\n'; 
•  » » 6 weeks ago, # ^ |   +5 Wow great idea
•  » » 6 weeks ago, # ^ |   0 I did this but got some stupid rte on testcase 4.
•  » » 6 weeks ago, # ^ |   +15 I could not understand your solution very well. It sounds like a great idea. Can you please explain in more detail (possibly with your thinking approach). Thank you
•  » » » 6 weeks ago, # ^ |   +21 For example, consider the sequence [9, -1, -1, -1, -1, -1, -1, 5]. The solution presented in the editorial is to find the unique simple path from 9 to 5 in the binary tree ([9, 4, 2, 5]) and then alternate between 5 and 10, resulting in the sequence [9, 4, 2, 5, 10, 5, 10, 5]. Most of the complicated logic in the solution is for finding this path, and in particular, for finding 2, the LCA of 9 and 5.My solution is to repeatedly find the largest entry with a missing neighbor and set its missing neighbor(s) to its value divided by two. In this example, 9 is initially the largest such entry, so set its missing neighbor to floor(9/2) = 4. Then, 5 is the largest such entry, so set its missing neighbor to floor(5/2) = 2. If the largest such entry is ever 1, we cannot set its neighbor to floor(1/2) = 0, so set it to 2 instead. Ties are broken arbitrarily. The full sequence of operations in this example is: 9 - - - - - - 5 9 4 - - - - - 5 9 4 - - - - 2 5 9 4 2 - - - 2 5 9 4 2 1 - - 2 5 9 4 2 1 - 1 2 5 9 4 2 1 2 1 2 5 For the last sample input, in the first step, 7 is the largest number, so set its missing neighbors to floor(7/2) = 3. Then, there are four 3's, each of which has at least one missing neighbor, so choose one arbitrarily (here I chose the first one). Then, there are two 1's and three 3's with missing neighbors, so chose one of the 3's arbitrarily (here I chose the last one). This case proceeds as follows: - - 3 - - - - 7 - - 3 - - - - 3 - - - 3 7 3 - 3 - - - 1 3 1 - - 3 7 3 - 3 - - - 1 3 1 - - 3 7 3 1 3 1 - - 1 3 1 - 1 3 7 3 1 3 1 - 2 1 3 1 - 1 3 7 3 1 3 1 - 2 1 3 1 2 1 3 7 3 1 3 1 - 2 1 3 1 2 1 3 7 3 1 3 1 2 In the binary tree, this corresponds to choosing a path that gets as close to the root as possible and using the cycle 1 2 1 2 ... to fill any remaining space. This can be implemented easily using a priority queue.
•  » » » » 6 weeks ago, # ^ |   +8 I got what you were trying to do , and i myself got the intuition maybe we can find the largest and insert half on each of its side , but i wasnt particularly able to get a conclusive proof to why this should work , I cannot think of a testcase at particular , but it just seemed to me that , there may exist a case where this solution wont work , do you have any proof as such why was this working , it will help me a lot in maybe understanding your thinking better or anything in such .Thank you in advance.
•  » » » » » 6 weeks ago, # ^ | ← Rev. 3 →   +8 Assume that at least one space is not missing and that a solution exists. The other cases are easy: if all entries are missing, we can just set the first entry to $1$ and use the same algorithm, and to check whether there is no solution, we can just use the same algorithm and do a linear-time check at the end that the constraints are satisfied. Removing these steps and I/O, the remaining implementation is: Implementationpriority_queue> Q; for (int i = 0; i < n; i++) if (A[i] >= 0) Q.emplace(A[i], i); while (!Q.empty()) { auto [a, i] = Q.top(); Q.pop(); if (i > 0 && A[i - 1] < 0) Q.emplace(A[i - 1] = a == 1 ? 2 : a / 2, i - 1); if (i < n - 1 && A[i + 1] < 0) Q.emplace(A[i + 1] = a == 1 ? 2 : a / 2, i + 1); } Also note that the output is bounded by $\max\left(2, \max_i a_i\right)$, so it cannot exceed $10^9$.Now, consider each nonempty consecutive run of missing spaces. There are two cases here: either the run is a prefix/suffix of the array or it is a subarray with non-missing entries on either side.In the suffix/prefix case, the algorithm will start from the non-missing element adjacent to the run and iteratively add values that meet the constraints. Example- - - 5 - - 2 5 - 1 2 5 2 1 2 5 The second case is slightly trickier. Let $a_i$ and $a_j$, $i < j$, be the entries on either side of the run. Consider the binary tree described in the editorial where $1$ is the root, $n$'s children are $2n$ and $2n+1$, and $n$'s parent is $\left\lfloor\frac n2\right\rfloor$. The solution, which we assume exists, will be a walk from $a_i$ to $a_j$ in this tree.Such a walk must consist of a simple path from $a_i$ to $a_j$ (which is unique in a tree) and some circuits. Trees are bipartite, so these circuits must have even length. Since we are assuming a solution exists, then, letting $d\left(a, b\right)$ be the distance from $a$ to $b$ in the tree, $j - i = d\left(a_i, a_j\right) + 2k$ for some integer $k \ge 0$ ($2k$ is the total length of the circuits and $d\left(a_i, a_j\right)$ is the length of the simple path). ExampleSuppose we start with the run 9 - - - - - - - - - - - - 5. $d\left(9, 5\right) = 3$ due to the simple path 9 4 2 5 and $j - i = 13 = d\left(9, 5\right) + 2\cdot 5$. One possible solution is 9 19 9 4 2 1 3 6 3 7 3 1 2 5, which is the simple path 9 4 2 5 plus the even-length circuits 9 19 9 and 2 1 3 6 3 7 3 1 2.When this is true, this algorithm constructs such a walk. It does this by repeatedly choosing the deepest endpoint (this will be the endpoint with the greater value, ignoring ties) and connecting it to its parent. This will reach the LCA after $d\left(a_i, a_j\right)-1$ steps and have $2k$ steps left.Then, it constructs an even-length circuit to fill the remaining length. First, it alternately connects the left/right endpoint to its parent, so after any even number of steps, a circuit is formed. Then, if there are still any missing entries, it completes the circuit with alternating 1's and 2's. Example 1Suppose we start with 19 - - - - - - 8. After two steps, we have 19 9 4 - - - - 8, which is just the simple path 19 9 4 8 plus an even number of missing entries. After two more steps, we have either 19 9 4 2 - - 4 8 or 19 9 4 - - 2 4 8 (depending on tie-breaking), which is the simple path plus the circuit 4 2 4. After two more steps, we have 19 9 4 2 1 2 4 8, which extends this circuit to 4 2 1 2 4. Example 2Suppose we start with 19 - - - - - - - - - - - - 8. After two steps, the algorithm produces 19 9 4 - - - - - - - - - - 8, which is the simple path 19 9 4 8 plus an even number of missing entries. Then, after four more steps, we have 19 9 4 2 1 - - - - - - 2 4 8 or 19 9 4 2 - - - - - - 1 2 4 8, which is the simple path plus the circuit 4 2 1 2 4. Since we have reached the root and there are still empty entries remaining, they are filled in with alternating 1's and 2's: 19 9 4 2 1 2 1 2 1 2 1 2 4 8, resulting in the simple path 19 9 4 8 plus the even circuit 4 2 1 2 1 2 1 2 1 2 4.
•  » » » » » » 6 weeks ago, # ^ |   +8 Thanks bro got the idea.
•  » » » 6 weeks ago, # ^ |   +12 Say you have two numbers a and b with b>a and with x negative ones between them. The main claim is that if there exists a way to replace these x negative ones with some positive integers to satisfy the problem's condition, then there exist a way in which the number just before b is floor(b/2). This is because say you had 2*b or 2*b+1 just before b, then at some point between a and 2*b+1 you must have reached b. Keep doing this recursively till you reach a point when the number just before b is b/2. Fill the numbers between this point and our originial b with b/2 and b alternatively.
 » 6 weeks ago, # |   0 Question B Detailed Video Editorialhttps://youtu.be/Gb5nnpg0TDk
•  » » 6 weeks ago, # ^ |   +1 Thank you so much for this. Literally a life saver
 » 6 weeks ago, # | ← Rev. 2 →   0 Can someone explain what might be wrong with this solution for problem C? https://mirror.codeforces.com/contest/1981/submission/263494280Thanks !
•  » » 6 weeks ago, # ^ |   0 Can anyone explain what is wrong with this solution 263791858 for C
 » 6 weeks ago, # |   +28 C's editorial is not friendly as a regular C. LCA is not something that most people thinking about in this position. There's still a solution without using such advanced topic, but why the author didn't do that?
•  » » 6 weeks ago, # ^ |   +16 I solved C in the contest and I don't understand what the editorial is talking about.
 » 6 weeks ago, # |   0 Why downvote editorial?
•  » » 6 weeks ago, # ^ |   0 Why downvote comment?
 » 6 weeks ago, # |   0 Problem C, I use brute-force searching with "merge intervals" to get an AC. Hacks welcome.263496224
•  » » 6 weeks ago, # ^ |   0 can you please explain your solution , what you did using merge intervals and how that concept is being used here ?
•  » » » 6 weeks ago, # ^ |   0 Explanation replied.
•  » » 6 weeks ago, # ^ |   0 Can you please explain your solution
•  » » » 6 weeks ago, # ^ |   0 Explanation replied.
•  » » 6 weeks ago, # ^ |   0 Can anyone explain what is wrong with this solution 263791858 for C
•  » » 6 weeks ago, # ^ | ← Rev. 5 →   +3 Explanation:For each step, value x can be transformed into either of x/2, 2*x, or 2*x+1.If we deal with a interval of integers [left, right], it will become a union of 2 intervals: [left/2, right/2] [2*left, 2*right+1] Both intervals are clamped within [1, 1e9]. Therefore, for each step, we operate on the set of continous intervals (type Intervals in my code), and use the good-old leetcode's "merge interval" solution (ivls_shrink in my code) after each step.Finally, after the specified number of steps, we see if the target value is an element of the the final intervals, and fill back the numbers by looking up the stored history.
 » 6 weeks ago, # | ← Rev. 2 →   0 Here are my 2 submissions for problem B 263489923 and 263504667 .The first submission gives AC while the second submission gives a WA. The difference between the two submissions is that in the 1st submission ,in the end I have written ll st=max(n-m,(ll)0); ll e=n+m; ans|=e; ans|=(st); and therefore it gives AC. I can't really figure out if we don't write these two lines ,why my code gives WA ,or are the tests weak ?
 » 6 weeks ago, # |   0 Can someone explain, how in problem C This code while (__lg(x) > __lg(y)) { L.pb(x); x >>= 1; } while (__lg(y) > __lg(x)) { R.pb(y); y >>= 1; } while (x != y) { L.pb(x); R.pb(y); x >>= 1; y >>= 1; } is generating the path between the two nodes ?
•  » » 6 weeks ago, # ^ | ← Rev. 2 →   0 I'll try explaining whatever I've understood. SpoilerThe code tries to find L, the path from the left node x to the LCA(x,y), and likewise R for the right node y. Every right shift (by 1) operation at a given node corresponds to moving one level up to it's parent node. Since the root node is always 1, we can see that the depth of a node corresponds to the position of it's MSB as every step down is accompanied by a left shift. So, deeper nodes have higher MSB positions, which can be easily evaluated by __lg(x). This serves as a quick tool to compare depths.As for the algorithm : First, we try to make the depths of the left and right nodes equal by moving the lower node (the one with higher position of MSB) up. If the LCA is either of x or y, our search ends here. If not, say the LCA is at some depth d and our current depth is d_curr. Then we must move both of our nodes up by d_curr-d times to reach the LCA. The takeaway being that, we must move them up simultaneously until they are equal. Then, we can follow L to reach the LCA from x, then the reverse of R to reach y ultimately. This will give us the shortest path.
•  » » » 6 weeks ago, # ^ |   +1 Thanks
 » 6 weeks ago, # |   +29 Love the first hint of the problem E
 » 6 weeks ago, # |   +12 For problem $C$, i found this logic. In order to go from one positive value to next positive value, we find the minimum no. of operations required, then if the required operations is less than given steps and has same parity as required, it is possible to go from one value to next, otherwise just return -1. This we do for all such positive values. Then, for first and last element, we just fill remaining -1s by doing *2, /2 and so on. HOW TO FIND OPERATIONS EFFECTIVELY? Let's say for example, we want to make 3 to 9, this can be done in 4 operations but how? $(3)_1$$_0 = (11)_2 and (9)_1$$_0$ $=$ $(1001)_2$, we just find the common bits from MSB in both, don't change them and first delete the uncommon ones from val1(here 3) and insert uncommon ones from val2(here 9). Here, common bits are only MSB, so operations required will be 1(for deletion from 3) and 3(from addition from 9), so total 4. During removing, do /2 operation, doing addition and bit is 0, do *2 operation, bit is 1, do *2+1 operation. We do this for all pairs of positive values of a. Submission Link :- 263497185
 » 6 weeks ago, # |   +1 what even is that solution to C lmao how can people even think about it as traversing a binary tree at all that's needlessly complicated and sounds like something that should be used within a moderately difficult Div2D. Instead, uhhh, my solution is much simplier, only kinda implementation heavy.(before the yapping, here's the submission: https://mirror.codeforces.com/contest/1981/submission/263477772)The condition that either val[i] has to be the rounded down value of val[i+1]/2 or the other way around can be interpeted as "when moving from an element to the next one, add or remove a bit from the back". This means that, as long as there exists a valid chain of suffix add/remove operation to "transition" between all non-empty values, there exists a valid sequence (for the prefix and suffix empty numbers, just fill them with random shit that still satisfies the condition).My algo goes as follows:1) Chug every non-empty number into a vector, alongside with their position.2) When considering 2 consecutive non-empty number, consider their bit sequence. Shove all of them into 2 corresponding deque, dq1 for the first number and dq2 for the second one3) When transforming from the first number to the 2nd one by suffix addition/deletion operations, we will want to keep the common prefix. Pop all of these out of the front of the 2 dqs. Then, delete the suffix of number 1 until it's empty (by constantly /2-ing the current value), then add the bits accordingly (by doubling the previous number, then either add 0 or 1 depending on the number on the front of dq2). Call the total amount of bit removal/addition operations num4) When transforming from a number at position i to position j, a total of (j-i) operations are needed. After we're done with transforming val[i] into val[j], just keep adding in a bit and then remove it in the next step. If (j-i-num) (the amount of "filler" operations) is non-negative and divisible by 2, the transition is possible. Otherwise, return -1.(would say that it's only a bit less complicated than the binary tree solution, this is kinda complicated for a div2C lmao)
•  » » 6 weeks ago, # ^ |   0 wait nvm it's actually the same thing lmao.at least the requirement is only 2 dqs instead of actually having to implement LCA. Though the LCA of 2 numbers in a complete binary tree is their prefix bit sequence or something anyways, so, uhhhhh
•  » » » 6 weeks ago, # ^ |   0 You don't even need two deques; see my submission: 263480468.
•  » » » » 6 weeks ago, # ^ |   0 ...for all that matters, I highly doubt that this dumb fuck who failed to get Expert 8 times in a row could compare with the efficiency and beauty of the legendary Tourist, but you do you
•  » » » » » 6 weeks ago, # ^ |   0 I highly doubt that this dumb fuck who writes author: tourist on the top of his code while not being even 1/1000th of tourist's skill could compare with the efficiency and beauty of tourist either.
 » 6 weeks ago, # | ← Rev. 4 →   +1 C has a much harder solution in tutorial , I did something which i feel is much simpler we just need to fill numbers between two non -1 numbers ,other than that its easy .Firstly store all the index where v[i]!=-1 then between two such indices we need to fill such that conditions are fullfilled , so say we want to fill numbers between l and r indices ,if v[l-1]>v[r+1] fill v[l] with v[l]/2 else v[r] with v[r]/2, we will try and get the two numbers as close as possible and minimum as possible(if we fill from both sides we can maintain the conditions more easily as from at least one side the number will be either half of the previous or next) , so basically they will both reach 1 at end after dividing by two as much as possible , after that we can just continue filling 2 and 1 alternatively ,after all this we should check if conditions are satisfied as there are cases where the numbers cannot come as close to each other https://mirror.codeforces.com/contest/1981/submission/263488558
•  » » 5 weeks ago, # ^ |   0 As simple an idea as jiangly 263500214. Nice explanation!
 » 6 weeks ago, # |   +2 C really has so much implementation.Hope it can be easier nxt time.qaq
•  » » 4 weeks ago, # ^ |   +3 check this one:265693364
•  » » » 4 weeks ago, # ^ |   +1 Wow it looks really simple,thank you!(^_^)
 » 6 weeks ago, # |   0 Can i get a counter test case for my solution of second problem
•  » » 6 weeks ago, # ^ | ← Rev. 2 →   0 Here is the test case : test case19 1Expected : 11 , found : 15
•  » » » 6 weeks ago, # ^ | ← Rev. 2 →   0 ya got it by dry running thank you.
 » 6 weeks ago, # | ← Rev. 3 →   0 zltzlt Can you please explain why the following is true in Task B? When $\left\lfloor\frac{l}{2^{d + 1}}\right\rfloor \ne \left\lfloor\frac{r}{2^{d + 1}}\right\rfloor$, $dth$ digit will be flipped at least twice between $[l,r]$
•  » » 6 weeks ago, # ^ |   +8 Because the $d$-th bit of $l$ and the $d$-th bit of $r$ are both $0$, and since $\left\lfloor\frac{l}{2^{d + 1}}\right\rfloor \ne \left\lfloor\frac{r}{2^{d + 1}}\right\rfloor$ there exists an $x$ in range $[l, r]$ such that the $d$-th bit of $x$ is $1$.
 » 6 weeks ago, # | ← Rev. 2 →   0 In problem D we can choose $x$ primes such that we can make $\ x \ * (x \ + \ 1) \ / \ 2 \ >= \ n \ - \ 1$ pairs, but don't know how to make such an arrangement. please tell me i'm in correct direction or not. Thanks!
 » 6 weeks ago, # |   +27 clist ratingIf more GMs were to participate on time, the estimated rating of F could be lower? 4k blew my mind.
 » 6 weeks ago, # |   0 Can anyone please explain why my following approach for the problem B fails: My ApproachI observed each bit individually and checked for two possibilities:I tried to find the greatest number smaller than 'n' whose ith bit is set. If it exists, check if the difference between this number and 'n' is less than or equal to 'm'. If this difference is less than or equal to 'm', the ith bit in the answer would be set.In the second case, I tried to find the smallest number greater than 'n' whose ith bit is set, and then check if the difference between this number and 'n' is less than or equal to 'm'. If this difference is less than or equal to 'm', the ith bit in the answer would be set.Here is my submission: https://mirror.codeforces.com/contest/1981/submission/263527422
•  » » 6 weeks ago, # ^ |   0 Implementation issue I think. Double check for (int j = i - 1; j >= 0; j--) { if (((fst >> j) & 1LL)) { fst = fst ^ (1LL << j); } } I believe all it does is convert fst to 0.
 » 6 weeks ago, # | ← Rev. 2 →   0 https://mirror.codeforces.com/contest/1981/submission/263527099--> wrong submissionhttps://mirror.codeforces.com/contest/1981/submission/263500175--> correct submission why (temp.size()-1)>len --> is performing differently when I substitute siz = temp.size()
•  » » 6 weeks ago, # ^ |   +1 temp.size() is by default a size_t
•  » » » 6 weeks ago, # ^ |   0 can you plz explain it further?
•  » » » » 6 weeks ago, # ^ |   +1 Because it's an unsigned, it overflows.
 » 6 weeks ago, # |   +3 Can anyone please tell the mistake in this code, getting WA.https://mirror.codeforces.com/contest/1981/submission/263510295Thank you!
•  » » 6 weeks ago, # ^ | ← Rev. 2 →   +4 https://mirror.codeforces.com/contest/1981/submission/263498446--> try to get the test case as I did..see the flag and no variable and if statement.. you will get it
 » 6 weeks ago, # |   +15 Someone will never think such complex solution in problem C!I solved C with Two Pointers method, just filling the -1 gaps in the array!My solution: 263542553Time Complexity: O(n)Uphacks are welcome!
•  » » 6 weeks ago, # ^ | ← Rev. 2 →   0 i have done 2 pointer filling with LCA at common number we get by dividing two . soln. Spoilerjust missed to submit in contest by 2 minutes
•  » » 6 weeks ago, # ^ |   0 hey very good solution, but could you explain that greedy nature you used. if (arr[L] >= arr[R]) { if (arr[L] > 1) { arr[L + 1] = arr[L] >> 1; L++; } else { // 1 cannot be divided by 2, cz all a[i] >= 1 arr[R — 1] = arr[R] << 1; R--; } } else if (arr[L] < arr[R]) { if (arr[R] > 1) { arr[R — 1] = arr[R] >> 1; R--; } else { arr[L + 1] = arr[L] << 1; L++; } }
•  » » » 6 weeks ago, # ^ | ← Rev. 2 →   +8 Okkayy... Suppose you have a gap like: [4, -1, -1, -1, 3] Now, consider two numbers outside the gap, 4 and 3, as 4 >= 3, the gap: [4, 2, -1, -1, 3] [4 >>= 1 means dividing by 2, so 4/2 is 2] Now, consider 2 and 3, 3 >= 2, then: [4, 2, -1, 1, 3] Then, 2 >= 1, then [4, 2, 1, 1, 3] If the filled-gap is valid, continue to next gap! But in this case, this is invalid, which will be checked on later step and print -1 Consider the same gap with an extra -1! Then finally we will get [4, 2, 1, -1, 1, 3] Here 1 >= 1, but here we cannot divide 1 by 2, because by rule, all a[i] >= 1, so multiply by 2, then we are getting [4, 2, 1, 2, 1, 3]. This is correct solution! Now, imagine different gaps and try yourself to fill it up!
•  » » » » 6 weeks ago, # ^ |   0 thanks, got it very nice approach
•  » » » » 6 weeks ago, # ^ |   0 what was the intution behind such approach ? How can a newbie comeup with some intution like this ?
•  » » » » » 6 weeks ago, # ^ |   0 I didn't learn to code binary tree as mentioned in the editorial yet. So I had to think as much as I can code, easier way! Consider a gap: [4, _, 16], here you can use 8 in the gap. Means multiplying by two the smaller side (4 <= 16). [4, 8, 16] is valid. [4, 8, 4] is valid for [4, _, 4]. In my previous comment I showed division approach. But,Q. Why division? Why not multiplication?In the problem statement, you see a floor function is used. So I got the idea not to multiply numbers as much as I can, because multiplying a numbers minimizes the usage of the floor function, as a result two non-equal number will be mismatched! Consider [4, _, 5], but [4, 8, 5] is invalid. Where [4, 2, 5] is valid option! The reason is a number x cannot have multiple floor(x/2)! But two different numbers x and y can have same floor(x/2) = floor(y/2) So, there is an observation that using division can minimize the difference between two numbers (e.g. 4 and 5 etc.), but using multiplication never minimizes the difference! And integer dividing already doing floor!Q. Why are we using multiplication in 1?This answer was already given in my previous comment. As we always divide the bigger one, we will get 1 when both side have 1s, so these are already equal sides. Multiplication can be used when there is no value differences between two sides! As multiplication doesn't remove value differences between the sides.The case [1, _, 1] is similar to [4, _, 4] which is mentioned above.
•  » » » » » » 6 weeks ago, # ^ |   0 got it !
•  » » 4 weeks ago, # ^ |   0 Very similar idea with better implementation, i guess,: 265693364.
 » 6 weeks ago, # |   0 Basic idea of D was almost exactly same as https://mirror.codeforces.com/problemset/problem/367/C
 » 6 weeks ago, # |   0 Super short solution for B.int a = max(0ll, n-m), b=n+m; int ans = (b | ((1<<__lg(a^b))-1)); if(!m){ cout << n << endl; continue; } cout << ans << endlI just used the xor to account for the spread and chose the largest element that I can reach (m+n) as the base. The idea being that the largest bit in xor is the largest bit that spreads and all bits less than that would also spread.
 » 6 weeks ago, # | ← Rev. 3 →   0 simple bruteforce for problem solution Spoilernow i am realizing i am finding LCA but didn't realise at time
 » 6 weeks ago, # | ← Rev. 2 →   0 i like problem c though i use brute force to find the path during the contest...
•  » » 4 weeks ago, # ^ |   0 Check this one: 265693364. I'm just using two pointers here.
 » 6 weeks ago, # | ← Rev. 2 →   0 Why do these writers write code that is not understandable.I agree you guys are pro but that doesnot mean every one can understand it.What does this means ,I am unable to understand for B: void solve() { ll n, m; scanf("%lld%lld", &n, &m); ll l = max(0LL, n — m), r = n + m, ans = 0; for (int i = 31; ; --i) { if ((l & (1LL << i)) || (r & (1LL << i)) || (l >> (i + 1)) != (r >> (i + 1))) { ans |= (1LL << i); } } printf("%lld\n", ans); }
»
6 weeks ago, # |
0

please, why my code wrong (problem B)

include <bits/stdc++.h>

using namespace std;

long long cases, m, n;

int main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

cin >> cases;
for (int t = 1; t <= cases; t++)
{
cin >> n >> m;

if (m == 0) cout << n << "\n";
else {
int len = __lg(m + n), sum = m + n, lim = 0;
for (long long i = (1LL << len); i >= 1; i = i >> 1) {
if ((sum & i) > 0 && (n & i) == 0) {
lim = i;
break;
}
}
for (long long i = 1; i <= lim; i = i << 1) {
n = n | i;
} cout << n << "\n";
}
}

return 0;


}

 » 6 weeks ago, # |   0 thanks, it has been fixed. I forgot to OR minn, i just think it is not important(#include ) using namespace std;long long cases, m, n;string binary(int n) { string ans = ""; while (n > 0) { ans = char(n%2 + '0') + ans; n = n / 2; } return ans; }int main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); freopen("testCode.inp", "r", stdin); freopen("testCode.out", "w", stdout); cin >> cases; for (int t = 1; t <= cases; t++) { cin >> n >> m; if (m == 0) cout << n << "\n"; else { int minn = max(0LL, n - m), maxx = n + m; int lim1 = 0, lim2 = 0; for (long long i = (1LL << __lg(maxx)); i >= 1; i = i >> 1) if ((maxx & i) && !(n & i)) {lim1 = i; break;} for (long long i = (1LL << __lg(minn)); i >= 1; i = i >> 1) if ((minn & i) && !(n & i)) {lim2 = i; break;} for (long long i = 1; i <= max(lim1, lim2); i = i << 1) n |= i; cout << n << "\n"; } } return 0; }
 » 6 weeks ago, # | ← Rev. 2 →   0 Hello In question D. Let the number of vertices in the complete graph be m. If m is odd, then the degree of each node is even, so this graph contains an Eulerian path, and the path length is equal to the number of edges, which is m(m+1)2. But how the edges should be mc2 which is (m*(m-1)) / 2.
•  » » 6 weeks ago, # ^ |   0 self-loop edges exist
•  » » » 6 weeks ago, # ^ |   0 Yaa I got thanks..
 » 6 weeks ago, # |   0 Can someone explain why are we looking at only the endpoints of the required sub array to look at in problem B?
 » 6 weeks ago, # |   0 In problem D if I tried to keep extra edges(when K is even) in the last 2 end points I get WA (https://mirror.codeforces.com/contest/1981/submission/263673037) but if i keep the first and the last end points I get AC (https://mirror.codeforces.com/contest/1981/submission/263675186)Can someone explain what is the cause ?Ex. n = 9, we get k = 4If i distribute the edges such that degree looks like this 5 4 4 5 I get AC but if I distribute it as 4 4 5 5 I get WA as in the Eularian Path there are 2 pairs with same product. Why is my implementation going wrong in this type of distribution.
•  » » 6 weeks ago, # ^ |   0 I believe it's because for finding an euler path, it is important where you are starting.If the number of vertices V is odd, it doesn't matter because each vertex has an even degree.If the number of vertices V is even, you presumably remove the edges until only 2 of the nodes have an odd degree. In that case, you have to start the dfs from some vertex with odd degree. The algorithm relies on the fact that if you start on a vertex with odd degree, you can only end on the other node with odd degree (all other nodes have even degree), because if you enter nodes with even degree through an edge, you are guaranteed to have another edge to exit the node from.
•  » » » 6 weeks ago, # ^ |   0 Thank you very much, I did not know that. I changed the starting vertex to the last vertex and got AC.
 » 6 weeks ago, # |   +22 Ignoring the difficulty, I think this round is more edu than edu round.
 » 6 weeks ago, # |   +3 just found this submission for D, and to me it seems very random. Can anybody explain why this part is correct (if it is) act=(act+seguentSalt[act]++)%mida
•  » » 6 weeks ago, # ^ |   +3
•  » » » 6 weeks ago, # ^ |   +3 thanks!
•  » » » 6 weeks ago, # ^ |   0 This mentions a different method, namely, constructing a Euler circuit by decomposing a complete graph into Hamiltonian paths.. The above submission clearly uses varying paths which need not be Hamiltonian.
•  » » 5 weeks ago, # ^ |   +3 Btw, I asked the question on stackexchange, since I was not able to figure it out. Someone gave a proof for it: https://math.stackexchange.com/questions/4926360/finding-an-eulerian-path-on-complete-graphs.
 » 6 weeks ago, # |   0 B was solvable. I was stuck finding the pattern, rather I should have just wrote k th term of ai :(
 » 6 weeks ago, # |   0 Can there be any easier approach for C. can someone suggest without tree and a more intuitive solution for this..??
•  » » 6 weeks ago, # ^ | ← Rev. 2 →   0 i mean only the explanation for finding an array knowing both the ends(a1 and an-1) might suffice!
•  » » 4 weeks ago, # ^ |   0 Check my submission: 265693364. It is quite intuitive in both logic and implementation. The idea is to find two non-negative elements and use two pointers to fill the in-between -1s by dividing the greater one by 2 and writing on the left/right side accordingly. Mathematically: if(v[right] >= v[left]) {v[right - 1] = v[right] / 2;right--;} else { v[left + 1] = v[left] / 2; left++; }And to handle edge cases, I have defined a vector of size n + 2, putting 0s on either side.
 » 6 weeks ago, # |   +6 in fleury algorithm dont we have to check if the edge we are traversing is a bridge or not ? i read the code above for problem D afew times and i still dont get how they are handling it
•  » » 6 weeks ago, # ^ |   +6 Hello, I had the same problem trying to implement my function to find an eulerian path. I believe the author's solution doesn't use Fleury after all. In fact, it's some sort of Hierholzer's algorithm. You can try seeing that this method returns a valid eulerian path (or cycle) given dfs is first called on a vertice with odd degree (if there is one).Now I'll always remember this simple method of finding the eulerian tour.
•  » » » 6 weeks ago, # ^ |   +6 i solved it using Hierholzer's algorithm but it doesnt seem like Hierholzer's algorithm because in Hierholzer's algorithm you have to remove the edge u add when m is odd cuz the algorithm only finds cycles and not paths but in the authors solution they dont seem to remove any edge iam so lost trying to understand the intuition behind the authors solution honestly
•  » » » » 6 weeks ago, # ^ | ← Rev. 2 →   +4 Here's what I came up with : You run a dfs starting on an odd degree. It will then end on the other odd degree. But your path may not be complete. In fact, you can see that, when exiting a call to dfs, the remaining calls to dfs will insert loops at the path you are currently in.In the end you have a valid path that visits all the edges.Now with your remark I remember that there may have been an easy method where you remove the first and last edges, indeed ... But it should be about as easy to implement.
•  » » » » » 6 weeks ago, # ^ |   +6 i feel so dumb we forgot the fact that we are dealing with a complete graph thats why it'll always end with a complete path on the other odd vertex
•  » » » » » » 6 weeks ago, # ^ |   +6 Well, when you reach the first end of a dfs function, the path may not be complete. But it will for sure be on the other vertex with odd degree. That's because when you enter a vertex, if it initially had an even degree, then when you leave it it will have an even degree again : either 0 and you don't come back to it, or something positive and you will be able to exit it again.Now when it backtracks through the dfs, it will find other paths that will have to be loops (similar proof).
•  » » » » » » » 6 weeks ago, # ^ |   0 it took me a minute there but i see what you mean, now i think the only time we need to add and edge between the odd vertices is when we are starting from an arbitrary vertex but if we are only starting from one of the 2 odd vertices then there is no need for me to add that extra edge
•  » » » 5 weeks ago, # ^ |   +6 Sorry for making mistakes. We should use Hierholzer's algorithm in this problem.
•  » » 6 weeks ago, # ^ | ← Rev. 2 →   +6 Also, I've seen your code. Note that you don't need to binary search the right $m$ at the beginning. It's something that was suggested by the editorial I know, but in fact you can do a linear search ; the complexity is perfectly fine.
•  » » » 6 weeks ago, # ^ | ← Rev. 2 →   0 yea also another thing so weird i dont seem to understand is that if we use the Hierholzer's algorithm starting from an odd vertex without adding the edge that we remove later it'll work for some reason i cant seem to wrap my head around this algo
•  » » » 6 weeks ago, # ^ |   0 why does it need to be an Eulerian path?
 » 5 weeks ago, # |   0 may someone tell me why my code get wrong answer in the sample 1 1000000? https://mirror.codeforces.com/contest/1981/submission/264373070
 » 5 weeks ago, # |   0 I cannot understand this fact The left$1$spreading to$a_n$takes$x+1$seconds, and the right$1$spreading to$a_n$takes$2^d−x$seconds. Suppose, I am taking 10001101 number in binary, then how the bits are spreading in it from left to right and right to left?
•  » » 3 weeks ago, # ^ |   0 Umm Actually we are talking about dth bit there so when x lies in range 0 <= x <= 2^d — 1 let say d = 2 here then 0 <= x <= 3 now imagine a number line from 0 to 3. x is the point where the number lies on that number line. on that number line -1 and 2^d will be only numbers whose dth bit will be set for more clear view 0 -> 0 1 -> 1 2 -> 10 3 -> 11 now see here for 2nd bit can only be set because of 4 and -1 now x is the point where you actually number lies in this number line (How far is it from 0) the distance is simply the time taken to set the bit as you can tell from left it will be x + 1 and from right it will be 2^d — x so basically we are just shifting some number to number line of 0 — (2^d — 1) . I hope this does not confuse you more I understood it this way. Correct me if I am wrong somewhere
 » 5 weeks ago, # | ← Rev. 2 →   0 Can anyone explain me the second solution of problem B?How/Why [l / 2^(d + 1)] != [r / 2^(d + 1)], d-th bit of answer is 1? I'm confused at "flipped.Thanks alot!
•  » » 5 weeks ago, # ^ |   0 Consider ith bit (from right), we know the bit is off in l and r otherwise we would already include it in answer. Now for number between l-1 and r-1 (inclusive) we have to check whether ith bit is on any time. Notice when you write consecutive numbers, ith bit is on for 2^(i-1) times consecutively and then off for 2^(i-1) times (consecutively). For eg, look at the 3rd bit from right between the numbers 16 and 24 16 -> 10000 17 -> 10001 18 -> 10010 19 -> 10011 20 -> 10100 21 -> 10101 22 -> 10110 23 -> 10111 24 -> 11000 In this sequence the 3rd bit from right is on 4 times from 16 to 19 and then off for 4 times from 20 to 23 and the pattern repeats. You are given l and r such that ith bit is off in both of them. Thus if the numbers between l and r is greater than or equal to 2^(i-1) then the bit must have flipped in the range otherwise not. You can check my submission I think it is cleanhttps://mirror.codeforces.com/contest/1981/submission/265039262
•  » » » 5 weeks ago, # ^ |   0 Oh! I understood. Thanks.
 » 5 weeks ago, # |   0 Still haven't got why in D we should remove m/2 — 1, not m/2. Can somebody explain?
 » 4 weeks ago, # |   0 Hi! Thanks for the tasks. Does anyone has thoughts/any references on how the proof for F can be generalized beyond chains? As I understand, we have proved that optimal solutions for chains it's $O(\frac{n}{ln{n}})$, but that argument doesn't fit for trees (for example, full binary trees consisting of ones).
•  » » 4 weeks ago, # ^ |   +8 We need some chains to cover a tree, and if for a single chain we need to consider MEX up to $O(\frac{n}{\ln n})$, then in the whole tree we also just need to consider MEX up to $O(\frac{n}{\ln n})$.
•  » » » 4 weeks ago, # ^ |   0 Thank you! Now it's clear.
 » 4 weeks ago, # | ← Rev. 3 →   0 .
 » 4 weeks ago, # | ← Rev. 2 →   0 why in solution 1 of problem B x <= 2 ^ d — 1, and not x <= 2 ^ (d + 1) — 1?
 » 9 days ago, # | ← Rev. 2 →   0 There is not a single accepted submission for problem E in pypy3 till now, I wonder does the author checks out that the time limit is enough so that the correct algorithm can pass in different languages?
 » 5 days ago, # | ← Rev. 2 →   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; } Nevermind, I understand now.