### ChthollyNotaSeniorious's blog

By ChthollyNotaSeniorious, history, 16 months ago,

Thanks for your participation! I am so sorry for my careless review. We were preparing for this round for many months and made some problems which writers and testers are all like. We do want to give everyone a good time to enjoy the contest. But carelessness is deadly. In problem B, some test cases should have been made, but we missed them in not only the pretests but also the final tests. In fact, we had not noticed it until some suspicious hacks appeared. I and all co-authors sincerely regret our mistake and hope you can forgive us.

Besides, few people are cyberbullying authors, please do not do so. If you have a bad experience, you can downvote me because of our fault.

Solution
Code
Solution
Code
Solution
Code
Solution
Code
Solution
Code
Solution
Code
Solution
Code
Hint 1
Hint 2
Solution
Code
Solution
Code
| Write comment?
 » 16 months ago, # |   +27 Auto comment: topic has been updated by ChthollyNotaSeniorious (previous revision, new revision, compare).
 » 16 months ago, # |   +9 Thanks for fast tutorial.
 » 16 months ago, # |   +9 Problem B was decent!!
•  » » 16 months ago, # ^ |   +10 Enlighten me what decency you found ?
 » 16 months ago, # |   0 Is it possible to solve Problem E if they don't have to return to the root?
•  » » 16 months ago, # ^ |   0 The implementation would be painful.
•  » » 16 months ago, # ^ | ← Rev. 4 →   0 We can see answer >= (answer of the original problem) — 2*(sum of max depth of target nodes of 2 pieces), but if there's no 2 deepest target nodes of each piece where their distance <=d, it's hard to find the minimum number of operations
•  » » 16 months ago, # ^ |   0 I didn't realize initially that they did have to return to the initial spot, so I solved it the other way. It was more complicated and I had to remove that complication to get the right answers.But the additional complication wasn't especially tough. Just required a lot of attention to small details.
 » 16 months ago, # |   +3 DD_my_love solved one problem less than me still has a better rank by around 300. Don't know how many more candidates are like this. LMAO ded.
 » 16 months ago, # |   +3 1774A - Add Plus Minus SignIt can be solve in O(t * n). the solution sounds like this: Let's create a sum equal to the first element. Then we just subtract 1 if sum > 0, otherwise we add 1. AC Code: 185664996
 » 16 months ago, # | ← Rev. 2 →   +36 Alternative solution for E: We define dp[x] as minimum cost to visit all subtree nodes of x with both pieces and come back. We do DFS, maintaining two values — mn1[v] and mn2[v] — which signify the maximum depth of a vertex we has to be visited by the first piece or the second piece. Now let's do transitions from a vertex u which is a son of v to v: if there are both types of vertexes (which have to be visited by both pieces) we do dp[v] += (4 + dp[u]) (we have to come down, visit all vertices and then come back)if there are no vertexes, we simply don't have to visit that subtree.if there is one type (let's say type 1 — a vertex that has to be visited by the first piece), then we have to visit that subtree with the corresponding piece (dp[v] += (2 + dp[x]), and, if we have to come down with the other piece, we do dp[v] += 2 (and that is why we maintain both heights)
•  » » 16 months ago, # ^ |   0 If we add another dimension to the DP, can we solve this problem?https://codeforces.com/blog/entry/110184?#comment-981781
•  » » » 16 months ago, # ^ | ← Rev. 2 →   0 [Deleted] (Whatever I suggested is not correct)
•  » » 16 months ago, # ^ |   +9 There is no need in dp: you can just do ans += 2 or 4 if you need to visit some child. My implementation: 185696308
 » 16 months ago, # |   0 lol
 » 16 months ago, # |   +3 ChthollyNotaSeniorious there is some problem with markup in the solution for D
•  » » 16 months ago, # ^ |   0 fixed now
 » 16 months ago, # | ← Rev. 2 →   0 Problem B was underrated, it was a much better problem to be at B
•  » » 16 months ago, # ^ |   0 I knew I had a problem with how I was approaching B so I looked at the other problems instead of trying to force it.Then I came back in 30 minutes and wrote a good easy solution. Sometimes it's important to recognize when you're on the wrong path, even when it seems to be working.
•  » » » 16 months ago, # ^ |   +3 Got you! Problem B taught us to be focussed more on the basics
•  » » » » 10 months ago, # ^ |   0 Can't you solve Problem B by only using the max used colours 210542105
 » 16 months ago, # |   +3 Thanks for the super fast editorial....
 » 16 months ago, # |   +3 Is it just me or latex for D doesn't work?
•  » » 16 months ago, # ^ |   0 Fixed
 » 16 months ago, # |   0 is there any working score predictor for codeforces contest ?
•  » » 16 months ago, # ^ | ← Rev. 2 →   0 I use Carrot. It's really accurate.
•  » » 16 months ago, # ^ |   0 yep, carrot extension
 » 16 months ago, # |   0 Problem B had very weak pretests which lead to a lot of people getting hacked so some people flew up the ranks by hacking instead of solving more questions
 » 16 months ago, # |   0 dont know what is going with the solution of b in editorial if anyone interested in a single line solution do check this out https://codeforces.com/contest/1774/submission/185703602
•  » » 16 months ago, # ^ |   +8 can u paste ur code here, I cant view it
•  » » » 16 months ago, # ^ | ← Rev. 2 →   0 for _ in range(int(input())): n,m,k=map(int,input().split()) arr=list(map(int,input().split())) if (max(arr)-1)*(k)+arr.count(max(arr))>n: print("NO") else: print("YES") 
•  » » » » 16 months ago, # ^ |   0 can you please explain why did we add arr.count(max(arr)) into the expression?
•  » » » » » 16 months ago, # ^ |   0 like lets say we have multiple maximums than to fits those maximum we need count of maximum extra space .for example 1 2 7 7 than to fit these two 7s we need to use count of the maximum element
•  » » » » » » 16 months ago, # ^ |   +8 Understood, thanks :)
 » 16 months ago, # |   +8 Can anyone view the solutions of other participants now? I aint able to view it
 » 16 months ago, # |   +26 It was a good round and I liked it.An occasional problem without strong pre-tests like B is a good thing because it offers opportunities to hackers. Those who made mistakes learn a valuable lesson about being more careful.Pre-tests are not supposed to be a guarantee.Problem E was very good.
 » 16 months ago, # |   0 The code for E is quite hard to understand compared to the written description which was crystal clear. It would be great if OP can use better variable naming in the future to help with readability.
 » 16 months ago, # | ← Rev. 2 →   +27 A slightly different solution to F: 185721355For every Create operation, we will find the number of pigs that survive. Let the index of the current Create operation be $i$. For now, we will assume that there was an Attack operation before $i$. We will create an array $s$: for $j >= 2$, $s_j$ will be the sum of Attack values between the $j-1$-th and $j$-th Remove to the right of $i$. $s_1$ will be the sum of Attack values between $i$ and the first remove to the right, and $s_0$ will be equal to the sum of Attack values before $i$ (so $s_0 > 0$). As we are only interested in the first $logX$ Repeats after $i$, we will only be interested in the first $t \leq O(logX)$ elements of this array. We will also denote $y$ to be the sum of Attack values after the last "interesting" Repeat.The array $s$ and the value $y$ are enough to find the solution for pig $i$: among all its clones, the health of the one with the $k$-th largest HP ($0$-indexed) turns out to be $x_i - s_0*k - y - \sum_{1\leq j < t} s_j * (\lfloor \frac{k}{2^{j-1}} \rfloor + 1)$. I can't think of a simple proof for this, but it's easy to see if you write the "unwrapped" (as in, you actually copy the sequence in case of a Repeat) sequence of operations down. Anyway, this means we can do a binary search to find the smallest positive element. In case of $s_0 = 0$ (if there was no Attack before $i$), we also need to count the number of Repeats before the next Attack, and multiply the answer accordingly.This is technically $O(Nlog^2 X)$, but it passes F2 in just over a second and I haven't managed to hack it yet, so it's probably just optimized enough.
•  » » 16 months ago, # ^ |   +15 I think your key formulation for "kth largest HP" aligns with the key observation in the tutorial. Essentially, because of the observation that the damage of clones is "greedy", we can always find the kth largest "subset sum" of clones (two ways to count this value: one is counting by clones, as the tutorial does; the other is counting by attacks, as in your formula). : )Thanks for providing another idea! The property of this problem is very intriguing.
 » 16 months ago, # |   0 Could anyone help me with Problem F1? I'm not sure why my solution doesn't work. Basically, I track all operations performed in an array of pairs ("ops"). I track the total decrease in the int "total" which I minimize with "SIZE" (a const int = 2e5+5) to avoid overflow. If total == size when I encounter the third operation, I simply don't track the operation because all previous pigs will be killed, and all newly created pigs will be created in the same way as the first set was. If total < SIZE and total > 0, then I double all of the operations in "ops" and double total. If total == 0, I record that the count of all current pigs should be doubled. I use prefix sums to calculate how many times each created pig will be doubled or have its health decreased.Here is my submission: https://codeforces.com/contest/1774/submission/185734070Thanks in advance.
 » 16 months ago, # |   0 Strange. We've made many hacks but there are only 18 testcases in the problem now.
 » 16 months ago, # |   0 Problems are good.
 » 16 months ago, # |   0 In problem E you can also just simulate all their moves: My code#include using namespace std; #define int long long const int N = 2e5 + 5; const int LG = __lg(N) + 2; const int INF = 1e9; int n, d; vector adj[N]; int m1, m2; int a[N], b[N]; bool ca[N], cb[N]; int cnta[N], cntb[N]; // count of a[i] and b[i] subtree of u int timer = 0, tin[N], tout[N], up[LG][N], dep[N], par[N]; void prelca(int u, int p) { tin[u] = ++timer; up[0][u] = p; for (int j = 1; j < LG; j++) { up[j][u] = up[j - 1][up[j - 1][u]]; } dep[u] = dep[p] + 1; par[u] = p; for (int v : adj[u]) { if (v != p) { prelca(v, u); } } tout[u] = ++timer; } bool isanc(int u, int v) { return tin[u] <= tin[v] && tout[v] <= tout[u]; } int lca(int u, int v) { if (isanc(u, v)) return u; if (isanc(v, u)) return v; for (int j = LG - 1; j >= 0; j--) { if (!isanc(up[j][u], v)) { u = up[j][u]; } } return up[0][u]; } int dist(int u, int v) { int l = lca(u, v); return dep[u] + dep[v] - 2 * dep[l]; } void pre(int u, int p) { cnta[u] += ca[u]; cntb[u] += cb[u]; for (int v : adj[u]) { if (v != p) { pre(v, u); cnta[u] += cnta[v]; cntb[u] += cntb[v]; } } } int Findkth(int u, int k) { for (int j = LG - 1; j >= 0; j--) { if (k >> j & 1) { u = up[j][u]; } } return u; } // find child of u that is also ancestor of v int Find(int u, int v) { int diff = dep[v] - dep[u] - 1; return Findkth(v, diff); } void Movea(int u); void Moveb(int u); int ans; int posa, posb; void Movea(int u) { if (u == 0) return; if (posa == u) return; if (isanc(posa, u)) { ans++; posa = Find(posa, u); if (dist(posa, posb) > d) Moveb(posa); } else { ans++; posa = par[posa]; if (dist(posa, posb) > d) Moveb(posa); } } void Moveb(int u) { if (u == 0) return; if (posb == u) return; if (isanc(posb, u)) { ans++; posb = Find(posb, u); if (dist(posa, posb) > d) Movea(posb); } else { ans++; posb = par[posb]; if (dist(posa, posb) > d) Movea(posb); } } void dfs(int u, int p) { for (int v : adj[u]) { if (v != p) { if (cnta[v] > 0 && cntb[v] > 0) { while (posa != v) Movea(v); while (posb != v) Moveb(v); dfs(v, u); } else if (cnta[v] > 0) { while (posa != v) Movea(v); dfs(v, u); } else if (cntb[v] > 0) { while (posb != v) Moveb(v); dfs(v, u); } } } if (posa == u) { while (p != 0 && posa != p) Movea(p); } if (posb == u) { while (p != 0 && posb != p) Moveb(p); } } void solve() { cin >> n >> d; for (int i = 1; i <= n - 1; i++) { int u, v; cin >> u >> v; adj[u].push_back(v); adj[v].push_back(u); } cin >> m1; for (int i = 1; i <= m1; i++) { cin >> a[i]; ca[a[i]] = 1; } cin >> m2; for (int i = 1; i <= m2; i++) { cin >> b[i]; cb[b[i]] = 1; } tin[0] = 0, tout[0] = INF; prelca(1, 0); pre(1, 0); ans = 0; posa = 1, posb = 1; dfs(1, 0); while (posa != 1 && posb != 1) { Movea(1); Moveb(1); } cout << ans << '\n'; } signed main() { ios::sync_with_stdio(false); cin.tie(nullptr); int t; // cin >> t; t = 1; while (t--) { solve(); } } 
 » 16 months ago, # |   0 C was easy but I was panik by B and ended up solving only A :(
•  » » 16 months ago, # ^ |   0 dude can you explain problem C's idea
•  » » » 16 months ago, # ^ |   0 Store max and min index of iTH game winner. If game iTH is "0", all player from 1 -> max[i-1] will win the game, otherwise is min[i-1] + 1 -> i. You can prove it yourself.
 » 16 months ago, # |   0 Can someone give better explanation for problem C. The intuition behind the solution and observation.
•  » » 16 months ago, # ^ | ← Rev. 3 →   0 I don't understand editorial. I'll just explain my solution. Sorry, I don't know how to explain it shorterSuppose we want to answer on $x$, so we consider only first $x - 1$ rounds. Then, following holds for any $y \leq x$. After $y - 1$ rounds there are $y - 1$ who dropped out. And one participant who is current winner. We can get their temperature, including winner. Length of this list will be $y$. Then sort this list in increasing order. Now, crucial part, if we change their temperature into consecutive numbers from $1$ to $y$, and let them perform rounds from the beginning in the same order, we will get same winner (but probably now he has different (new) temperature). This means, that first $y$ rounds for any limit $x$ has outcome similar to limit $y$, just some participants ignored. But in any outcome with limit $y$ we can insert all ignored participants and get same outcome as if it was limit $x$.Let's apply it for $x = n$ and $y = n - 1$. This means, only one participant is ignored, the one who will fight winner of all previous rounds. Consider case when corresponding $s = 1$. There are two cases: either winner previous winner wins or new participant wins. Suppose new participant wins with temperature $t$. Then temperature of previous winner is less than new one. So, there exist outcome where participant with less temperature is winner previous rounds. It means, set of possible winners with less temperature than $t$ is not empty set, so there is minimum temperature, who can win previous $n - 2$ rounds. In short: if new participant win, there is possible outcome where he wins against opponent with minimum temperature. Then, again crucial part: if we order all $y = n - 1$ participants by increasing temperature, we know where new participant is inserted. And, to be able to win, he should be inserted after winner of previous rounds (after participant who can win $y - 1 = n - 2$ rounds with minimum possible temperature). This gives us way to find out who could win against winner of previous rounds if we know minimum possible winner of $n - 2$ rounds.Second case: suppose previous winner wins against new participant. Similarly, we know where new participant should be inserted in sorted list of participants of $n - 2$ rounds. It should be inserted before previous winner. And obvious best way is to insert him as participant with temperature 1, then he can be defeated by any previous winner (because all their temperatures will be greater than 1). This gives us way to find out who could win against new participant if we know possible winners of $n - 2$ rounds.Let all possible winners of $y - 1 = n - 2$ rounds without new inserted participant is $W$. To clarify: W is set of who could win if there was $n - 1$ participant with temperatures from $1$ to $n - 1$. Then, using two observations above, we get that possible winners of $n$ rounds is all participants with temperatures $> \min(W)$ and also $v + 1$ for each $v \in W$ (after insertion of new participant under temperature 1, all previous winners increase their temperature). It's easy to show that union of this two sets is just every temperature $v$ satisfying: $\min(W) < v \leq n$.Similarly, we can find out, if corresponding $s$ is 0 and winners of previous $n - 1$ rounds is $W$, then winners of $n$ rounds is every temperature $v$ satisfying: $1 \leq v \leq \max(W)$.Using this two relationships, we can maintain possible winners as segment and update it correspondingly and output answer based on segment length.Source code: 185679312
 » 16 months ago, # |   +5 Who can prove D's conclusion for me, why I don't feel so obvious?
•  » » 16 months ago, # ^ |   +8 hello i did not get time to solve d in the contest but today i solved it without seeing the editorial, i'll tell you my implemetation. 1.)firsly we count the total number of ones in the (n*m) array, let's name it check, now we will like to distribute equal number of ones in all the n rows, now if check%n is not equal to 0, then we can not have our answer, otherwise we will like to distribute (check/n) number of ones to all the n rows, let's call this number req. 2.)now in all the n rows we will calculate the total number of ones present in it if it is greater than req, we will store the index of the row and the value in a map, and all the values less than req in another map and we will not touch the rows which have req no of ones, this can be done in (n*m) complexity which is allowed. 3.)now our task is to exchange ones between the rows which has smaller no of ones than required and with the ones which have larger number of ones required, note we already know about them in our two maps, both the index and the values, this can be done easily in ((n^2)*m) complexity by going row by row but sadly it is not allowed, here comes the tricky part:-> 4.)instead of going row by row we go column by column, each time we encounter a one in our column we will check if the row in which the one occurs is a row having larger number of ones than req using map, if yes we mark it and if we find a corresponding 0 for that one on the same column whose row has lesser number of ones than req, we exchange the value, vice versa goes for when we encounter a 0 and after the row having larger number of ones than required becomes equal to required we erase it from the map, vice versa for the row having lesser number of ones than required, this complexity for this process is order of n*m which is allowed, ignoring the logarithmic time complexities used for map. here is my submission: https://codeforces.com/contest/1774/submission/185759065
 » 16 months ago, # |   0 Hello everyone I am not able to understand the logic of question number d (same count one) from the tutorial. Can anyone explain the logic behind the d. I dont want to see the solution for d now because i want to try it first. Thank You...
•  » » 16 months ago, # ^ | ← Rev. 2 →   +12 step1: find out all rows which have an excess of 1's and which have deficient 1's Swapping between ith, jth row in the kth column becomes valid only when a[i][k] != a[j][k] otherwise, after swapping, we will have the same matrix as beforeWe need to minimize the operations.My claim :Given a row with excess 1's and another row with deficient of 1's, it is always possible to send one from the excess row to the deficient row. (i.e sum[excess_row] --; sum[deff_row] ++; ) Proof :(By contradiction)Assume that you cannot do such swappingLet any excess row contain x1 onesLet any deficient row contain x2 ones => x1 > (sum/n) > x2If I cannot do such a swapping, it means that for every 1 in excess_row, the corresponding column in the deficient_row should also contain a 1.This implies => deficient row should contain at least x1 ones => x2 >= x1 But x1 > x2 This contradictsOur claim is correct
•  » » » 16 months ago, # ^ |   0 thanks a lot for the proof. I had an intuition, but not being able to proof was really bugging me. Thanks again.
•  » » » » 16 months ago, # ^ |   +1 you are the first person to reply to me , welcome pa
 » 16 months ago, # |   +1 Any E solution in easy words?
•  » » 16 months ago, # ^ | ← Rev. 3 →   +21 I'll try my hand at it.To make the problem a bit nicer to explain (imo), I'll label the $a_1,a_2, \dotsc ,a_{m_1}$ nodes as red and the $b_1,b_2, \dotsc ,b_{m_2}$ ones as green.We know that both nodes start at 1 and must return to 1, and so it's a good idea to root our tree at 1 as well. Let's consider an easier variant of the problem, where we only need to reach the red nodes.So first off, since the nodes must return to 1, we notice that every edge in the optimal paths is traversed twice (one to go, and one to return) for each of our pieces. If $d = n$, then we can simply keep the green piece back home at the root and let the red piece dance about. Let's suppose we know for each node whether it contains a red node in its subtree. Then it's clear that the minimum path that hits all red nodes AND returns to the root will traverse only the nodes that contain red nodes in its subtree. Crucially, it will traverse the edges twice and only twice (any more would be a waste). Okay, that's great, now let's see what happens if $d < n$. So, the green piece must follow the red piece within a certain distance like a leashed dog. Now, we want to move the green piece minimally. So what we can do is greedily move a green piece only if we need to. What do I mean by this? Let's assume we are at a root $r$ and both the red piece and green piece are here. Suppose $r$ has a child $c$ that has both green and red nodes in its subtree. We most definitely need to move both the green piece and red piece in that direction. (because we need to collect the green and red nodes). Thus, both red and green pieces traverse the edge from $r$ to its special child $c$, and we know that it must return back to the root (so it's gotta come back the way it came). Therefore, we can add $2$ for each piece, totaling to $4$ moves.Now, let's suppose $r$'s child $c$ only contains a red node in its subtree. Well, let's suppose we know the depth of the deepest red node in this subtree. If this depth $\text{maxDepth} \leqslant d+\text{depth}(r)$, then we clearly don't need to move the green piece. The red piece can do it all by itself. We can add $2$ for the red piece and recurse further into the subtree. Notice this also holds for the reverse case ($c$ only contains a green node in its subtree), aka WLOG.What if $\text{maxDepth} > d+\text{depth}(r)$? Well, we're gonna have to move the green piece in the direction of $c$, otherwise we violate the constraint. Note that this is very similar to the "+4" case where both red and green were contained in the subtree at $c$. So just like that, we add 4 and recurse further. We basically apply these two principles to every child and do a proper DFS through it. Now the question is, how do we calculate The max depth of a coloured node Whether a node contains a coloured node. You can do this in any number of ways but I find it easiest to just do a DFS beforehand to set everything up. Set up an int array maxRedDepth and when DFS'ing, if a node $v$ is red, then set maxRedDepth[v] = depth. Then take the $\max($maxRedDepth[c]$)$ of every child. 185894910
•  » » » 16 months ago, # ^ |   +1 Detailed explanation. Thanks.
•  » » » 13 months ago, # ^ |   0 when in your explanation, maxDepth > d + depth(r)? , are we assuming that the green piece and red piece are at the same place ?
•  » » » » 13 months ago, # ^ |   0 Yep.
•  » » » » » 13 months ago, # ^ |   0 i am still not able to process it clearly, can you please simulate it over an example to help me understand clearly, like when +2 extra steps can help us when maxDepth > d + depth(r) can be greater than just one edge distance?
•  » » » » » » 13 months ago, # ^ | ← Rev. 2 →   0 Imagine that the tree is with $d = 2$, then it's clear that the red piece can't reach node 3 if the green piece doesn't move to 1.maxDepth of 1 will be 2, as the red node 3 is 2 levels down from node 1.
•  » » » 7 months ago, # ^ |   0 great explanation
 » 16 months ago, # |   0 why in problem B we are doing (n-1)%k +1 instead of n%k. Any Particular reason???.
•  » » 16 months ago, # ^ |   +7 if n is a multiple of k, it should be k instead of 0
 » 16 months ago, # | ← Rev. 2 →   0 1774B - Coloring how to prove that number of $a_i$ which is equal to $\left\lceil \frac{n}{k} \right\rceil$ should be not bigger than remainder?How to make sure construction works? Not for all segments there is $j$-th cell. Do we just skip segment if $j$-th cell doesn't exist?
•  » » 16 months ago, # ^ |   0 For a particular value of $k$, the number of segments $=$ $\lceil{\frac{n}{k}}\rceil$. Let's take $n = 12,$ $k=5$, then our segments will look like $[ __, __, __, __, __ ]$ $[ __, __, __, __, __ ]$ $[ __, __ ]$.Here $\lceil{\frac{n}{k}}\rceil = \lceil{\frac{12}{5}}\rceil = 3$Let $M[4] = [3, 3, 3, 2, 2, 2] = [a_1, a_2, a_3, a_4, a_5]$. Let's start filling the segment:After filling $a_1$:Segment $=$ $[ a_1, __, __, __, __ ]$ $[ a_1, __, __, __, __ ]$ $[ a_1, __ ]$$M[4] = [0, 3, 3, 2, 2, 2] = [a_1, a_2, a_3, a_4, a_5].After filling a_2:Segment = [ a_1, a_2, __, __, __ ] [ a_1, a_2, __, __, __ ] [ a_1, a_2 ]$$M[4] = [0, 0, 3, 2, 2, 2] = [a_1, a_2, a_3, a_4, a_5]$.Now you see that there is no way to fill $a_3$ such that the distance between any two $a_3$ is $k$.Hope this answers your question
•  » » » 16 months ago, # ^ |   0 maybe it doesn't work just because very first arrangement of $a_1$ is already wrong, and if you put them in other way, it will somehow turn out. I don't need "see" explanations, I need rigorous one.
•  » » » » 16 months ago, # ^ | ← Rev. 2 →   0 How is the first arrangement of $a_1$ wrong? Since $a_1$ has the maximum frequency, it makes sense to handle it first and place it at the first position of the first segment since this position will definitely provide the distance of $k$ in the next subsequent segments.
•  » » » » » 16 months ago, # ^ | ← Rev. 2 →   0 There is also: following possibilities [ a_1, __, __, __, __ ] [a_1,  __, __, __, __ ] [__,  a_1 ] [ a_1, __, __, __, __ ] [__,  a_1, __, __, __ ] [__,  a_1 ] [__,  a_1, __, __, __ ] [__,  a_1, __, __, __ ] [__,  a_1 ] Why you arguing about first one. May be for one of other it will work?
•  » » » » » » 16 months ago, # ^ | ← Rev. 4 →   0 First of all, notice that your second arrangement is wrong since you won't be able to place $a_2$.Hmmm, okay let me phrase it like this: Let $K'$ $=$ $(n \% k \equiv 0$ $?$ $k : n \% k)$ --> The size of the last segment.Let the suitable indexes in the $last$ segment be $[1, K']$ The only way to place first $K'$ elements having value equal to $\lceil\frac{n}{k}\rceil$ in the $last$ segment is to place them in the suitable indexe of the $last$ segment. After you have placed them in the $last$ segment, one sure way to place them in the remaining segments without violating any condition is to place them cyclically at distance $k$. Now we have $\lceil\frac{n}{k}\rceil - 1$ segments remaining. If there is one more element having value equal to $\lceil\frac{n}{k}\rceil$, we won't be able to place that element without violating the condition. There are less segments and more values, then by the Pigeon-Hole principle, there will be two values in the same segment(box). The distance between these two same values will be less than $k$.
•  » » » » » » » 16 months ago, # ^ |   0 Actually placing the first $K'$ elements having value equal to $\lceil\frac{n}{k}\rceil$ in the $last$ segment and then cyclically placing them in the next segments is the only way. Proof: Note that right now we are only dealing with those elements having value equal to $\lceil\frac{n}{k}\rceil$.Let's increase the distance between any two same elements (Let's call them $A$) in any consecutive segment by $x$. The new distance is $k+x$. Then the distance between the element $A$ in the next segment and the current segment decreases by $x$ making it $k-x$. To accommodate this change, the $A$ in the next segment will have to be moved by at least $x$. This creates a chain reaction that will reach the last segment. Since the size of the last segment is less than or equal to $k$, then $A$ in the last segment will have nowhere to move. So we can say that placing the element in the last segment decides the order in the next subsequent segments.
•  » » » » » » » » 16 months ago, # ^ | ← Rev. 2 →   0 This creates a chain reaction that will reach the last segment. Sometimes "chain" reaction would be resolvable, but you phase it like it will always fail: example: n = 11, m = 5, k = 3 a = [3, 3, 2, 2, 1] [1, 2, 3, 4] [1, 2, 5, 3] [4, 2, 1] [1, 2, 3, 4] [1, 2, 5, 3] [4, *1, 2*] Please, stop claim you know proof when you don't. It obstruct comments section.
•  » » » » » » » » » 16 months ago, # ^ | ← Rev. 2 →   0 You wanted an explanation of the case when frequency of values equal to $\lceil\frac{n}{k}\rceil$ exceeds the remainder. I gave an explanation for that.Why are you giving a rebuttal with an invalid test case?
•  » » » » » » » » » 16 months ago, # ^ | ← Rev. 2 →   0 Because I don't see why similar thing may not happen. If you're talking about case which is you claim is impossible, then starting from some arrangement and then extending distance is odd idea. Because if it's already impossible, why then we extend distance. If it's possible, then claim is wrong. If you consider some unfinished filling, with empty spots, then you just may consider my example with all colors > 2 not yet filled: n = 11, m = 5, k = 3 a = [3, 3, ?, ?, ?] [1, 2, _, _] [1, 2, _, _] [_, 2, 1] [1, 2, _, _] [1, 2, _, _] [_, *1, 2*] Why I send this example, because this "chain" of reactions is perfectly fine, because one color just jumps to the front (but you claim it should only move farther, I'm extending distance between two cells of color 2)
•  » » » » » » » 16 months ago, # ^ | ← Rev. 2 →   0 First of all, notice that your second arrangement is wrong since you won't be able to place $a_2$. Then why in your first reply to my question not just say "we can't place a1 in first places of all segments because we can't place $a_3$ then". It's not a proof if you tried all possibilities for some example and it didn't work. The only way to place first $K′$ elements having value equal to $\left\lceil\frac{n}{k}\right\rceil$ in the last segment is to place them in the suitable indexe of the last segment. Claim without reasoning. Many other statements also without reasoning.
•  » » 16 months ago, # ^ |   0 I came up with proof of first claim myself. Here it is. ProofConsider case when $n$ divisible by $k$. If we split into boxes by $k$, then we have $\frac{n}{k}$ boxes, each of size $\leq k$. This means, that in one box there can not be two elements of same color (by requirement from the statement). So, in box can be 0 or 1 occurrences of a color. Then, there can not be more than $k$ of colors with $a_i = \frac{n}{k}$. Proof by contradiction. Suppose $c$ is the number of colors with $a_i = \frac{n}{k}$ and $c > k$. Then number of colors $c$ times their number $\frac{n}{k}$ will be $c \times \frac{n}{k}$ which is greater than $k \times \frac{n}{k} = n$. So, total number of such $a_i$ is bigger than $n$, this is contradiction with requirement that sum of $a_i$ is equal to $n$.Consider case when $n$ is not divisible by $k$. Let $r = n \bmod k$. Then, there is $\left\lceil\frac{n}{k}\right\rceil$ boxes, and last box with $r$ elements. Similarly, there can not be more than one occurrence of color within box of size $k$. Also, easy to show that there can not be two elements of same color in last box of size $r$. Then for each box, the number of occurrences of a color can be 0 or 1. Then, for color with $a_i = \left\lceil\frac{n}{k}\right\rceil$ it will have occurrence 1 in all boxes! Then, the number of colors like that can not be $> r$. Proof by contradiction. Suppose $c$ is the number of colors with $a_i = \left\lceil\frac{n}{k}\right\rceil$ and $c > r$. Then, each of colors like that, should have occurrence 1 in all boxes, in particular: in last box! This means, last box should have $c$ colors, but $c > r$. Contradiction with capacity of last box.
 » 16 months ago, # | ← Rev. 3 →   +3 Please add a test case with t=1; n=2; m=500000 in Problem D. the First array with all 1's and 2nd array with all 0's. I have seen many solutions with M^2 in solution getting accepted. Please look into it. 185717356
•  » » 16 months ago, # ^ | ← Rev. 2 →   0 In fact, you can hack it. However, I have hacked it.Thank you for providing the test.
 » 16 months ago, # |   +20 My unproven solution to G:We must start with an interval with $x=l$. Choosing an interval with the highest $y$ is irrelevant because whether you choose one with lower $y$ or not is pointless so the sum is $0$ so we can ignore it; that repeats until you get to the interval with lowest $y$, let's call that lowest $y$ $e_1$. Now the new intervals are the ones with $x$ in $[l+1,e_1]$; once again we find the interval with the lowest $y$ out of the ones which have $x$ in $[l+1,e_1]$, call that lowest $y$ $e_2$, continue the process with $[e_1+1,e_2]$, etc. until $e_i=r$ or we see that that's impossible, if it's impossible then the answer is 0, otherwise whether it's $1$ or $-1$ depends on the length of the path.I precompute all the intervals which are possible to reach using this process and use binary lifting to answer queries. Code: 185786867.The unproven part is the complexity; I don't know how many intervals are possible to reach using this process. It's not hard to see that the sum of lengths of intervals is $O(n^2)$, which means that there can be at most $O(n\sqrt{n})$ of them. Is there a better upper bound on the amount of reachable intervals?
•  » » 16 months ago, # ^ |   -18 The solution for G is a bit strange. If there exist two segments (l1,r1),(l2,r2) such that l1≤l2≤r2≤r1 and we choose (l1,r1), number of >ways of choosing (l2,r2) at the same time will be equal to that of not choosing. Hence if we >choose (l1,r1), the signed number of ways will be 0. So we can delete (l1,r1). This is not true. For eg. if the segments are $[1,3],[4,6],[2,5],[3,4]$ and $[l,r]$ is $[1,6]$, then the answer is equal to $1$ (not zero) and also $[2,5]$ contains the segment $[3,4]$.
•  » » » 16 months ago, # ^ |   +28 Why did you reply to my comment? Your reply is completely irrelevant to my comment.I recommend reading the part of the editorial that you quoted more carefully. It just says that the solution will stay the same if we delete $[2,5]$, not that the solution is 0 due to its existence.
 » 16 months ago, # | ← Rev. 2 →   0 Totally blown away by the knapsack trick in F2 of the array where $2a_{i-1} \lt a_{i}$. Is it a well-known trick among high rated contestants, or is it something ad-hoc for this problem?Tagging the author of the Problem Little09
•  » » 16 months ago, # ^ | ← Rev. 2 →   0 In my opinion, some high rated contestants might have seen it in other problems. However, when I made this problem, I was unfamiliar with the trick. But I think it is not difficult to solve it after observing $a_i>\sum_{j=1}^{i-1}a_j$.
 » 16 months ago, # |   0 https://codeforces.com/contest/1774/submission/185708026 Can anyone help me, why is my submission wrong?
•  » » 16 months ago, # ^ |   +3 Take a look at Ticket 16646 from CF Stress for a counter example.
•  » » » 16 months ago, # ^ |   0 ooohhh I understandd. Thank you so much.
 » 15 months ago, # |   0 Can anyone tell what's wrong in my approach for Problem-E, 189112092 its failing at test 20...My approach: I am first calculating minimum number of steps separately for the two chess pieces. For each piece, for a particular node, if there exists a node in its subtrees (or the node itself) which is supposed to be travelled(is in the piece's sequence), then increase the number of steps by 2 as we will have to reach the root node of that subtree atleast once. This path of nodes is marked(coloured) separately for both nodes. At the end, subtract 2 from steps as the piece was already there on the root of the whole tree. Then I am calculating the extra steps separately for each piece that they will have to travel. For each piece, at a particular node which has to be traversed atleast once, if the other piece's marked path's distance becomes more than 'd' (given in ques), then increase number of steps by 2, as we will have to pull down the other piece atleast one node down.
•  » » 10 months ago, # ^ |   0 Hey I did the same thing as you and I'm missing the same test case. Were you able to get this issue resolved?