### culver0412's blog

By culver0412, 6 months ago,

Thanks for participating, and happy Easter!

Editorial
Implementation
Remark

Hint
Editorial
Implementation
Question

Hint 1
Hint 2
Editorial
Implementation

### 1815B - Sum Graph

Hint 1
Hint 2
Editorial
Implementation
Harder version
Solution to harder version

Editorial
Implementation

Hint 1
Hint 2
Editorial
Implementation

Hint 1
Hint 2
Observation 1
Editorial
Implementation

### 1815F - OH NO1 (-2-3-4)

Key Idea 1
Key Idea 2
Editorial
Implementation (Tester: gamegame)
• +130

 » 6 months ago, # | ← Rev. 3 →   0 In problem D2C / D1A's Editorial, please correct the following line For even n, n−2 is odd...
 » 6 months ago, # |   -18 what;s s in Let Ti consists of vertices x such that vx=s .
•  » » 6 months ago, # ^ |   +3 I think it should be "Let T_i consists of vertices x such that v_x = i". In other words, T_i consists of all the vertices which shortest distance to 1 is (i-1). It is also true that such x will appear i number of times in the final sequence.
 » 6 months ago, # | ← Rev. 3 →   +24 A slightly simpler solution of 1815A:The answer is "NO" if and only if n is even and the alternating sum of the elements of A is positive. Obviously the alternating sum is constant and this linear condition is the only condition on elements of A (we can add n-1 linearly independent vectors to A any number of times each). So we can transform A into any other array with the same alternating sum. The only situation where such an array does not exist is when n is even and the alternating sum is strictly positive.
•  » » 3 months ago, # ^ |   0 I can't understand your solution. Can you explain it again?
 » 6 months ago, # | ← Rev. 2 →   +4 Alternative solution to D2C / D1A (code with explanation)boolean solvable(long[] a) { /* Observation 1: If the array [a_1, a_2, ..., a_n] is solvable, then the array [a_1 - k, a_2, ..., a_n] is also solvable for some posivite k. Therefore, we will always try to reduce the next element if possible, to increase the solvability of the segment [i+1, n-1]. Observation 2: For some general index i, if the number of elements up to (and including) i are even, or, if the number of elements after i are even, then we can (infinitely) reduce/increase all those elements respectively, thereby splitting the array. Observation 3: If the next element is greater or equal to the current, we move on. Otherwise, if we cannot split the array, two cases arise- (I) local resolution is not possible -> return false (II) local resolution is possible -> update the next two elements as required. */ for (int i = 0; i < a.length - 1; i++) { int behind = i; int ahead = a.length - 1 - i; long delta = i == 0 ? 0L : a[i] - a[i - 1]; a[i + 1] -= delta; if ((ahead & 1) == 0 || (behind & 1) == 1) { a[i] = a[i + 1]; } else { delta = a[i + 1] - a[i]; if (delta < 0L) { if (ahead == 1) { return false; } a[i + 1] = a[i]; a[i + 2] -= delta; } } } return true; } AC submission — Java — iterativeAC submission — Java — recursive
 » 6 months ago, # |   +1 I posted this on the main blog but I realized that maybe its better to post it here.Can someone please explain proof of B in editorial in more detail?In particular, I would like to know what does it mean lowerbound for maximum cost and how do we, from the observations in proof before that, conclude that this is the value of the lowerbound.In task we need to construct the grid such that minimum cost over all paths is maximized. So I think in order to prove that some construction satisfies the requirements we need to find value C(n) such that for every placement of integers on the grid minimum cost among all paths in the grid is <= C(n). Then we need to show that for our construction minimal cost equals C(n). Am I wrong?
•  » » 6 months ago, # ^ |   0 Editorial contains the formal proof. My intuition for the problem using n = 12 as example is below. To place {1,2,3,4,5,6,7,8,9,10,11,12} into 12 spots, among which 6 has positive contribution to the alternating sums. It always makes sense to place {7,8,9,10,11,12} into the positive spots.  1 2 3 4 5 6 1: + - + - + - 2: - + - + - + As v[1][1] and v[2][6] are both positive and always included, it always makes sense to place {12,11} into these two spots. A path would pass exactly one of v[1][3] or v[2][2], so it makes sense to place (10,9) into these two spots. I end up placing these 5 pairs (10,9)(8,7)(6,5)(4,3)(2,1) the way below with bigger value in second row. The intuition happens to be right.  1 2 3 4 5 6 1: 12 5 9 3 7 1 2: 6 10 4 8 2 11 
 » 6 months ago, # |   0 I'm struggling to understand Div2D's example. How does [1 2 3 4 5 6] comply with the query about $p_1$ and $p_3$? The distance between nodes 1 and 3 is 2 in the graph at that time.
•  » » 6 months ago, # ^ |   0 To be clear, the example's description does not mean that we have ruled out [2 3 1 5 4 6] for instance?
•  » » » 6 months ago, # ^ |   0 The example is correct by coincidence. It does not rule out other possibilities.This is common for interactive problems. The example mostly boils down to randomly guessing to avoid hinting you about the solution.
•  » » 6 months ago, # ^ |   0 You guess 2 permutations and only 1 of them needs to be correct. In this example the first one $(1,4,2,5,3,6)$ is correct, so it doesn't matter whether the second one $(1,2,3,4,5,6)$ is consistent with earlier queries.
•  » » » 6 months ago, # ^ |   0 I see, thanks! But the example's solution had not figured out the permutation with certainty, right?
 » 6 months ago, # | ← Rev. 2 →   +35 I solved Div1D without noticing the pattern for $m\geq 3$. This DP is still $O(\log n)$ but works for all $m\geq 1$.Let $s(l,r)$ be the sum of all possible XOR values, and $c(l,r)$ be the number of possible XOR values, when $l\leq a_1+\dots+a_m \leq r$. The answer to the original problem is $s(n,n)$.If we additionally require the lowest bit of the XOR value must be 0, the set of possible sums are $2\lceil\frac{l}{2}\rceil,2(\lceil\frac{l}{2}\rceil+1),\dots,2\lfloor\frac{r}{2}\rfloor$, and the number of 1s in the lowest bits of $a_1,\dots,a_m$ can be $0,2,4,\dots,2\lfloor\frac{m}{2}\rfloor$. Notice that both of them are set of integers equally spaced by 2. Thus by right shifting all numbers by 1 (that is, removing their lowest bits), we obtain a subproblem where the set of possible sums is again a contiguous interval. More precisely $\lceil\frac{l}{2}\rceil-\lfloor\frac{m}{2}\rfloor\leq a_1+\dots+a_m \leq\lfloor\frac{r}{2}\rfloor$. The contribution of this subproblem is \begin{align} c(l,r)&+=c(\lceil\frac{l}{2}\rceil-\lfloor\frac{m}{2}\rfloor,\lfloor\frac{r}{2}\rfloor)\\ s(l,r)&+=2s(\lceil\frac{l}{2}\rceil-\lfloor\frac{m}{2}\rfloor,\lfloor\frac{r}{2}\rfloor)\\ \end{align}Similarly for the case where the lowest bit of XOR value must be 1, we have \begin{align} c(l,r)&+=c(\lceil\frac{l-1}{2}\rceil-\lfloor\frac{m-1}{2}\rfloor,\lfloor\frac{r-1}{2}\rfloor)\\ s(l,r)&+=2s(\lceil\frac{l-1}{2}\rceil-\lfloor\frac{m-1}{2}\rfloor,\lfloor\frac{r-1}{2}\rfloor)+c(\lceil\frac{l-1}{2}\rceil-\lfloor\frac{m-1}{2}\rfloor,\lfloor\frac{r-1}{2}\rfloor)\\ \end{align}We can inductively show that all $l$'s and $r$'s for all states at the same depth of the recursion differs by at most 1 from each other. Thus the number of states at each level is bounded by a constant, and the recursion will only involve $O(\log n)$ distinct states.
 » 6 months ago, # |   -13 For Div1B/Div2D I have a working algorithm working on my local computer, but the OJ is declining it for some reason. I've tried doing a custom test with what the input would have been and it worked just as intended, but it is still declining it for some reason.It keeps giving me "wrong answer Wrong + operation format: x = 1 which is not between 2 and 2*n inclusive :( (test case 2)", but I am pretty sure my code doesn't print a "+ 1" unless n=1. Since the boundary for n is n>=2, it should never happen.Could anyone help me out with what I messed up so I can avoid this on future interactive problems? #include #include #include #include #include #include #include #include #include using namespace std; void solve () { int n; cin >> n; if (n==2) { cout << "! 1 2 2 1" << endl; return; } cout << "+ " << n << endl; int response; cin >> response; cout << "+ " << n+1 << endl; cin >> response; int mx=0, mxIdx=0; for (int i=2; i<=n; ++i) { cout << "? 1 " << i << endl; cin >> response; if (response>mx) { mx=response; mxIdx=i; } } vector dists(n+1); vector dist_map(n+1); for (int i=1; i<=n; ++i) { if (i==mxIdx) continue; cout << "? " << mxIdx << " " << i << endl; cin >> dists[i]; } for (int i=0; i> t; while (t--) { solve(); } } 
•  » » 6 months ago, # ^ |   +4 I'm dumb I wasn't getting input to see if my final guess was right.
 » 6 months ago, # | ← Rev. 3 →   +66 For D1F we can solve it as follows:Lemma:Consider a graph with arbitrary initial weights, and for each edge we can add $1$ to exactly one of its vertices, we can make the final weights different.Construction:Start from the vertex with the smallest initial weight,and for each step,take an unpicked vertex with smallest initial weight,and for all the unassigned edges connected to it, add 1 to the other vertex. This works in $O(n+m)$ or $O((n+m)\log(n+m))$ with set.For the original problem, we can just reduce it to the lemma by properly assigning values in each triangle. It is clear that we can achieve $(+4,+4,+4)$ and $(+3,+4,+5)$ by only using weights $1,2,3$,and this are enough to handle all the cases if we add $(3,3,3)$ to each triangle initially and use the lemma.Submission:201599238.
 » 6 months ago, # |   0 for div2B did anyone have any other explanation? the editorial seems very involved for a div2B :O
•  » » 6 months ago, # ^ |   0 We just put odd numbers in 1st row and even in other or vice versa. To maximise the answer we shud take the first and second maximum and put in the first row first element and 2nd row last element and greedily add the remaining elements. U can refer my submission belowhttps://codeforces.com/contest/1816/submission/201541528
•  » » » 6 months ago, # ^ |   0 thank you for the reply,I was able to make some random stuff during the round to get AC, but I was scared coz I can't prove that my solution is the best. which makes me less confident to submit during contests.and that is why I felt this is hard for div2B
•  » » » » 6 months ago, # ^ |   +1 Yeah even I took 20 min to figure out. I just randomly took cases for n=4,6 and figured out. Eventually it worked. Greedy solutions will be tough to prove sometimes. But yeah we hv to try grinding it out
 » 6 months ago, # |   0 when will we have delta for div2, I cant wait to be cyan for the first time :v
•  » » 6 months ago, # ^ |   0 Same Here!
 » 6 months ago, # |   +46 For problem D2B, we intended to make a task about parity (the checkered property). However, we noticed that many participants discovered the solution by looking at samples and "proved by AC". In fact, the proof of this solution is very hard considering its position. Sorry if this task wasn't enjoyable for you.We added some insights on finding the optimal construction in the editorial and made some minor fixes; sorry for the confusion. Still, I hope you had fun participating in the round :)
•  » » 6 months ago, # ^ |   0 when will be ratings get updated??
•  » » 5 months ago, # ^ |   0 I am having some difficulty understanding the proof for Div2 B. Can you provide some more explanation? I am particularly confused as to why we are averaging cost of 2 paths and how it gives the upper bound for the minimum cost.
 » 6 months ago, # |   -77 Div1B is a bad problem.
 » 6 months ago, # |   0 In the editorial of Div2 problem B The example output is inversal reversal to the formula.
 » 6 months ago, # |   0 As Rating of Div 1 is already updated but why there is delay in Div 2 rating update?
 » 6 months ago, # | ← Rev. 2 →   0 Can anyone help me with a testcase where my code-201678387 for problem -C will fail?
•  » » 6 months ago, # ^ | ← Rev. 2 →   0 1 3 1 9 1 The output should be YES.
•  » » » 6 months ago, # ^ |   0 Thanks got it.
 » 6 months ago, # |   0 The harder version of D2D/D1B can be also solved by optimizing the editorial solution:) SpoilerIt's sufficient to notice that distances from 1 to vertices to the left of 1 on the "chain" are pairwise different and form a contiguous segment [1, x] for some x (we assume that segment is empty when 1 is a leaf). Similar thing happens for vertices to the right of 1 (segment [1, y]). So for distances d, such that $1\leq d \leq min(x, y)$ there are two indices corresponding to that distance. We can iterate over the distances (first decreasing, later increasing) and maintain previous vertex on chain. Every time when there are two possible next vertices on path, we can simply ask a question whether previous and next candidate are directly connected (distance between them is 1). And since $x+y=n-1$, we know that $min(x, y) \leq \frac{n}{2}$ and achieve the desired amount of questions.My accepted code: 201628377
 » 6 months ago, # |   0 The interactor of problem D(div2)/B(div1) can be made TLE. Select a case that n>800,add O(n) random x between n/2 and 3n/2, and query n random pairs of nodes.As there are O(n^2) edges in the graph, it takes O(n^3) time for the interactor to answer all the query.
•  » » 6 months ago, # ^ |   0 I thought there was some genius algorithm to update the distances for each query
•  » » » 6 months ago, # ^ |   0 Unfortunately, no, it is just a simple BFS (I don't know any genius algorithm to update the distances). So indeed the interactor can be made TLE. However, as far as I know, all the correct solutions only use $O(1)$ type 1 queries, so this issue shouldn't prevent any correct solutions from getting accepted.
 » 6 months ago, # |   0 Why is the interactor in D1B space intolerant. I spent almost an hour upsolving this problem just because of that :(
•  » » 6 months ago, # ^ |   +5 I think it is because you outputted extra debug lines?
•  » » » 6 months ago, # ^ |   0 Yeah, I guess, thanks
 » 6 months ago, # |   +5 C. Between Some test cases that I got wrong while upsolving: Test case 11 4 3 2 4 3 1 2 3  Test case 21 4 4 2 1 2 4 4 3 3 4  Test case 31 4 5 2 1 3 4 2 4 4 2 2 3 
 » 6 months ago, # |   +3 The div is unrated?
•  » » 6 months ago, # ^ |   0 idk my rating isnt changed
•  » » 6 months ago, # ^ |   0 UP
 » 6 months ago, # | ← Rev. 5 →   0 culver0412 till now rating has not been updated yet for div 2, when ratings will get updated.
 » 6 months ago, # | ← Rev. 3 →   +5 culver0412 Just found this Easter Egg!
 » 6 months ago, # |   0 Can anyone explain the editorial of Div2 C? I can't seem to grasp anything after the second line.
 » 6 months ago, # |   0 Thank you for the hints they are really helpful
 » 5 months ago, # | ← Rev. 2 →   0 can some one help me, why my solution 201888165 is giving i = -1 for the output? problem : 1815B - Sum Graph
•  » » 5 months ago, # ^ |   +3 What I see is you didn't input $1$ or $-2$ after outputting the answer.
 » 5 months ago, # |   +10 I did not get solution at first after reading editorial but solved Div2C using following method. ApproachAs per Question there are two operations for any array a1 a2 a3 a4 ... i.e. +1 to ai and ai+1 -1 from ai and ai+1 I define two more operation using above 2 i.e. ai+1 and ai+2-1 ( using first operation on ai and ai+1 then second operation on ai+1 and ai+2) or ai-1 and ai+2+1 ( using second operation on ai and ai+1 then first operation on ai+1 and ai+2 ) Now back to our Problem :- Consider Odd Case firsta1 a2 a3 a4 a5we can see that a1, a3 and a5 can share any number among themselves ( How ? by using self defined operation ai-1 and ai+2+1 and so on )similarly a2 and a4 can share any their value among themselvesso we can assume there are two groups that can share their values, one group on even indexes and other on odd.If we try to use operation 1 or 2 present in problem ( +1 to ai and ai+1 or -1 from ai and ai+1) values will be added in or substracted from both groups so we neither gain or loose values so it can't help us if sequence is not sorted.But we notice one thing if we can take as many value from first index ( odd group ) and distribute it in center and give largest values to right most element which will make array sorted no matter what is even group.Consider Even Case Nowa1 a2 a3 a4 a5 a6 we can see that a1, a3 and a5 can share any number among themselves ( How ? by using self defined operation ai-1 and ai+2+1 and so on )similarly a2, a4 and a6 can share any their value among themselves there are two groups again that can share their values, one group on even indexes and other on odd.If we try to use operation 1 or 2 present in problem ( +1 to ai and ai+1 or -1 from ai and ai+1) values will be added in or substracted from both groups so we neither gain or loose values so it can't help us if sequence is not sorted.Unlike previous case, here we don't have option that we used earlier ( take from left most index as many as we like , distribute need values it in center and give largest to right most index ). Here we can't arbitrarily take values from first index so what can we do really ? These are still groups so we can use it for sorting. share values among even groups and odd groups as well.Now consider two example:- 2 1 4 3 Odd group values ( odd index values ) :- 2 4Even group values ( even index values ) :- 1 3in this case no matter what even group share it can't beat last index value i.e. if we do this 0 6 ( shared values to right most index )0 4 ( shard values to right most index )we cant make it sorted ever. So we Got our condition for even case Even group total >= Odd Group total ( why not vice versa ? because right most element will always belong to Even group. and for every odd group ai there need high or equal ai+1 to make it sorted )
•  » » 3 months ago, # ^ |   0 thank you
 » 5 months ago, # |   0 Anyone can tell me why my solution for Div1B/Div2D gives the wrong answer on OJ? Also, is there any way to find the code for the interactor for such problems?
•  » » 5 months ago, # ^ |   0 Checker comment: wrong answer Printed answer is not a permutation :( (test case 1)That means your code reported an answer that's not a permutation. Please take a look at your solution and see what has to be changed. If you have any doubts, you can read the tutorial.Also, there is no way to find the code for the interactor, unless the authors want to make it public for some reasons.
 » 5 months ago, # |   0 I think the note for 1815F - OH NO1 (-2-3-4) has a wrong explanation for the first test case. According to the problem statement, the weights should be added to (1, 2), (2, 3) and (3, 1) respectively, making the final weights [5, 3, 4, 0].
 » 4 months ago, # |   0 https://codeforces.com/problemset/status?my=on why this code not working,I am unable to figure out after many WA attempts for Div.1 B
 » 4 months ago, # |   0 In problem B. Grid construction . I am putting highest and lowest value in matrix . If i is even and odd accordingly but failing for some test cases. Please check...1816B - Grid Reconstruction #include #include #include #include #include #include #include #include #include typedef long long int ll; #define pb push_back #define tc ll t;cin>>t;while(t--) #define fastio ios_base::sync_with_stdio(false); cin.tie(0); const int mod = 1e9 + 7; using namespace std; void solve(){ ll n; cin>>n; int mat[2][n]; int h=2*n; int l=1; mat[0][0]=h; h-=1; mat[1][n-1]=h; h-=1; for(int i=0;i
 » 3 months ago, # |   0 editorial code of 1815A is giving output "YES" for following test case: n = 5 a = [2, 3, 1, 4, 3] but when I tried to perform operations by hands I found answer should be NO, am I missing something, can anyone please explain the sequence of operations to make the array a in non-decreasing order.
•  » » 3 months ago, # ^ |   0 -1 0, 0 3, 3
 » 2 months ago, # |   0 This is a high-quality contest!
 » 5 weeks ago, # |   0 Im just curious, how do you solve the minimum number of jumps problem for Div2A?
 » 2 weeks ago, # |   0 Seems like your official solution on div1 D got an TLE on test #94. I figured out that the problem is you haven't clear the two maps before each subtask XD.
•  » » 2 weeks ago, # ^ |   0 I submitted the same code that you submitted, but using C++ 20, and got accepted in 717msI think there is issues on C++ 14?
•  » » » 2 weeks ago, # ^ |   0 Maybe I would stop using C++ 14 ...