Gol_D's blog

By Gol_D, history, 7 weeks ago,

1611A - Make Even

Idea: MisterGu

Tutorial
Solution

1611B - Team Composition: Programmers and Mathematicians

Idea: MikeMirzayanov

Tutorial
Solution

1611C - Polycarp Recovers the Permutation

Idea: MikeMirzayanov

Tutorial
Solution

1611D - Weights Assignment For Tree Edges

Idea: MikeMirzayanov

Tutorial
Solution

1611E1 - Escape The Maze (easy version)

Tutorial
Solution

1611E2 - Escape The Maze (hard version)

Tutorial
Solution

1611F - ATM and Students

Idea: Gol_D, MikeMirzayanov

Tutorial
Solution

1611G - Robot and Candies

Idea: MikeMirzayanov

Tutorial
Solution

• +51

 » 7 weeks ago, # |   +5 By the way, in F many of you have written a two-pointer solution and I liked it. If anyone wants to write a proof, please.
•  » » 7 weeks ago, # ^ | ← Rev. 4 →   +8 Correct me if I am wrong ProofThe problem is similar to problems where size of sliding window changes depending on some conditionHere the condition is we should always have enough money to perform next transaction.In this explanation assume that we are always maintaining a $sum$ variable for the current amount of money in the ATM (initially $s$) and here $l$ signifies left pointer (initially 0) and $r$ right pointer (initially 0)There are four changes possible Change 1moving left pointer when it is a credit operation ===> subtract that value from $sum$ i.e. $sum-=a[l]$ Change 2moving left pointer when it is a withdrawal operation ===> add that value to $sum$ i.e. $sum+=a[l]$ Change 3moving right pointer when it is a withdrawal operation ===> check if sum is greater than required amount, if possible then subtract that value from $sum$ otherwise move left pointer ahead i.e.if(sum >= a[r]) $sum-=a[r],r++$else do $l++$ until we have enough money Change 4moving right pointer when it is a credit operation ===> add that value to $sum$ as there is no pre-requisite to perform this operation i.e. $sum-=a[l]$0-based indexingLets suppose we start from $0$ and we are able to perform all transactions upto $i$Now obviously, the transaction at point $i+1$ has to be of withdrawal as we are always able to perform credit operation.So , at $i+1$ we are unable to provide the required amount as ATM doesn't have that muchSo we will rollback our previous operation upto a smallest (nearer to 0) point where we have enough money to perform the given operationNow the $0th$ operation can be 1) Withdrawal====> If we remove this operation than obviously the amount of money inside the ATM will increase and in that case all the intermediate operations will have more than required money to perform operations so no intermediate operations is invalid. 2) Credit====> If we remove this operations than obviously the amount we are having right now will decrease so it's not helpful to only remove this individual operation. As it doesn't help us to get enough money to proceed. So we will have to move our left pointer more ahead.====> So it is safe to say that our rollbacks will always stop after a withdrawal operation because otherwise the amount of money will be less than previously we had at the point $i$ and in that way now operation in between will be invalid.So if we are unable to have enough amount of money even if we rollback all previous operations then our left pointer will be $i+2$Otherwise we will increment the right pointer by $1$.So we can just keep doing this until the right pointer reaches the end of array and while extending our right pointer we will keep track of the max number of operations($[l,r]$) performed for answer. PSThis is first time I am writing proof of some problem.So, sorry for my poor English or incomplete explanation (if found anywhere please comment below that part or a testcase where my explanation seems inappropriate)
•  » » 7 weeks ago, # ^ | ← Rev. 2 →   +7 Let us assume the max possible index(MPI) for some index L is R. Now for L+1, there are 2 possibilities: The MPI for L+1 >= R, which means 2 pointers would work normally. The MPI for L+1 < R. The reason 2 pointers work in this case is the fact that if MPI for L+1 is < R, it doesn't even matter to us because we need the max interval and this will definitely be less than the size of [L,R]. Thus for any useful range with start index > L, MPI must be greater than R.
•  » » 7 weeks ago, # ^ |   0 I didn't realize 2 pointers solution worked, so I wrote segment tree + binary search. 2 pointers is much cleaner :)
•  » » » 7 weeks ago, # ^ |   0 how would you solve it if the problem were to find largest subsequence instead of contiguous subsequence ??
•  » » » » 7 weeks ago, # ^ |   0 Several observations: If we fix the leftmost position of the contiguous subsequence we chose to employ, we can binary search on our rightmost position. This is because choosing to help one more person on the right is always more expensive than not choosing to help that person. How do we know if we can help a contiguous subsequence $[a_l, a_{l + 1} \dots a_{r - 1}, a_r]$? We can only help if $a_l, a_l + a_{l + 1}, a_l + a_{l + 1} + a_{l + 2} \dots a_l + a_{l + 1} + \dots + a_r$ are all positive. That is, if all the prefix sums are positive, or alternatively that our minimum prefix sum is $\ge 0$. How do we quickly calculate minimum prefix sums which have some left offset? Just notice that prefix sums starting at $a_l$ are exactly the same as prefix sums starting at $a_0$, except we subtract off $pref[l - 1]$. So in short, we can find the minimum prefix from $a_l \dots a_r$ by computing prefix sums $a_0 \dots a_r$, finding the minimum on the interval $[l, r]$, and subtracting off $pref[l - 1]$. You can check out my submission here: 136938974 if you are still confused. Also, there's no need to cheese in this problem, but if you did need to cheese, you could be sparse table instead of segment tree for minimum, since the prefix sum array is static.
•  » » » » » 7 weeks ago, # ^ |   0 yeah i understood this one, but i asked a different question..i asked if we could solve this problem in O(NlogN) when we are asked to find longest subsequence instead of longest contiguous subsequence
•  » » » » » » 6 weeks ago, # ^ | ← Rev. 2 →   0 I assume what you meant is creating the longest subsequence by removing some elements in the original sequence.In this case, we can try to solve the problem greedily.First we construct a minheap.Then we will iterate through the original sequence using a pointer i. If the ith element is negative, put it in the heap. When the sum of all elements from 1 to i becomes negative, we will remove the element with the smallest value using the minheap we just constructed. Since the removed elements will have the smallest possible value, I think the resulting sequence will be the longest possible sequence. I couldn't prove/disprove this idea, but it seems to work.
•  » » 6 weeks ago, # ^ |   0 In China we call this solution "Monotone queue", maybe you can get some information by searching this word.
 » 7 weeks ago, # |   -9 im so debil
 » 7 weeks ago, # | ← Rev. 2 →   +38 Alternative solution for G:We have to cover the candies with chains. According to Dilworth's theorem it is enough to find the longest antichain. (set of candies, where it is impossible to collect two of them in the same turn.Two candy $a$, $b$, (with the same parity) can be in the antichain if their width differnce is strictly larger than their height difference ($|y[a]-y[b]|>|x[a]-x[b]|$)This motivates a dp solution $dp[i][j]$ — the longest anticahin from the first column ends $(i, j)$. The transitions are easy: $dp[i][j]$=max($dp[i-1][j-1]$, $dp[i+1][j-1]$) and $dp[i][j]$=$dp[i][j-2]+1$ (if there is a candy in (i, j).The time and memory complexity is $O(n*m)$.
•  » » 7 weeks ago, # ^ |   +3 That was what I did in the contest. I was just a bit dumb and didn't realize that I could've just done a bit of dp. Instead, I solved with LIS, so the code got much longer than needed. Well, the final code was really similar to Baltic OI — 2009 — Candy.
 » 7 weeks ago, # | ← Rev. 2 →   0 Did anyone else solve E1 using LCA?I solved E1 using LCA and a bruteforce-ish approach. For every leaves, I brute through all the enemy vertices in the list and then used LCA to calculate the distance from the leaf to the enemy and from the leaf to the root in $O(logN)$. I did a little optimization that if the leaf is an enemy vertex, I skip it.In the worst case the complexity should be something around $O(N * k * logN)$ with $k$ is the number of enemies, since it is possible to build a tree with $N - 1$ leaves. Still not sure why my code didn't got FST, probabilistic magic maybe?
•  » » 7 weeks ago, # ^ |   0 I did simple dfs two times. That is a O(n), check my submission herehttps://codeforces.cc/contest/1611/submission/136941781
•  » » » 6 weeks ago, # ^ |   0 bro i did the same thing but I am getting a TLE. Could you help me with that? https://codeforces.cc/contest/1611/submission/137884514
 » 7 weeks ago, # |   +2 my simple two pointer solution for problem F:solution for F
•  » » 7 weeks ago, # ^ |   0 Thanks for this, it was helpful.
•  » » » 7 weeks ago, # ^ |   0 welcome bro
•  » » 6 weeks ago, # ^ |   0 thanks,dude,it's helpful!
 » 7 weeks ago, # | ← Rev. 3 →   0 Please, help me. Why my solution for F get WA: https://codeforces.cc/contest/1611/submission/136894757 ?
•  » » 7 weeks ago, # ^ | ← Rev. 2 →   0 1 2 0 -1 5 correct output: 2 2 your output : 1 2
•  » » » 7 weeks ago, # ^ |   0 Thank you!
 » 7 weeks ago, # |   0 Can someone help me,please https://codeforces.cc/contest/1611/submission/137113575
•  » » 6 weeks ago, # ^ |   0 this test 1 8 1 1 2 3 4 5 1 7 1 7 2 3 4 5 6 8 get wrong answer distant to 8 is 7, distant to 5 is 8, but 5 earlier then 8 it's solution don't work because you don't check distant from root of tree.
 » 7 weeks ago, # |   0 Is this a bug? The editorials to the problems aren't linked in "Contest Materials" yet, only the Announcement is linked.
 » 7 weeks ago, # | ← Rev. 2 →   -10 I think, my solution for F is easier than editorial's.Time complexity: O (n * log ^ 2 (n))Link: 137119559P.S. you can use sparse table instead of segment tree.
•  » » 7 weeks ago, # ^ |   0 You can use sliding window which is O(N)
•  » » » 7 weeks ago, # ^ |   0 how do we decide which one to slide?
•  » » » » 7 weeks ago, # ^ | ← Rev. 2 →   0 use a prefix sum (or just a sum), try taking next value at j. if S + range_sum(i, j) < 0, then its not possible to take elements up to j starting at i, then move i until it is possible to do so. At this point, you then increment j and repeat the process.something lile this: while(j < N) { while(i <= j && S + range_sum(i, j) < 0) i++; ans = max(ans, j-i+1); j++; } using this idea, you know that every i already tested cannot excede the current j, (because at some point S + range_sum was less then 0). At the meantime, we are removing all i that is not usefull (doesn't get to j). I think that the last question is: "Given an invalid window (i, j), what if I test an new_i (new_i > i) that can get to j, but there is some point x (new_i <= x < j) such that S + range_sum(new_i, x) < 0??", that is not possible because, initially our current window was invalid and: if we remove a positive prefix of our window (i, j), then S + range_sum(new_i, j) is also invalid (less then an invalid range). That is the case explained before. if we remove a negative prefix of our window (i, j), as S + range_sum(new_i, x) < 0, adding the removed negative prefix + S + range_sum(new_i, x) is also less then 0. Which means that S + range(i, x) is negative, therefore, j shoud never be greater then x, as j is the first invalid point. This is a contradiction.
•  » » » » » 6 weeks ago, # ^ |   0 thanks, i succesfully implemented this with a sum and two pointers
•  » » » 7 weeks ago, # ^ |   0 Yeah, I can.But... To my mind, my solution is more straightforward.
 » 7 weeks ago, # |   0 I think it should come like "Consider a vertex p[i], (2≤i≤n)" instead of "(2≤p[i]≤n)" in the editorial for D.
 » 7 weeks ago, # |   0 I did same as it written in the editorial.By running a breadth-first search at the same time from each vertex with a friend, we can find the shortest distance to any friend from each vertex and by running from the root — the distance to the root. Now let's just go through all the leaves and check if there is one among them that the distance to the root is less.Here is my implementationWhat I did in my implementation is that First I found the distance of every vertex from the root and stored it in the vector distance_from_root.second, I found the minimum distance of every vertex from every friend, What I mean is that if the distance of a vertex x is 1,2,3 from friend x1,x2,x3 respectively then I stored the minimum of it i.e., 1 for vertex x in the vector distance_from_friend and then I checked for this condition as it is given int the editorial. Thus, Vlad can win if there is such a leaf (which, by condition, exits) for which the distance to the root is less than the distance to any of the friends.But it is showing TLE. Please Help!
•  » » 7 weeks ago, # ^ |   0 You run bfs from each friend, it's O(n*k). In the editorial, It was meant to run one bfs which uses all friends as start vertices like it is in solution.
 » 7 weeks ago, # |   0 I tried to solve "1611E1 — Escape The Maze (easy version)" using approach of traversing from friends up (parents) and from root (Vlad) down (to leaves) and at the same time. When friends visit some node I mark it as visited and that prevents Vlad to traverse through that node down. This approach gives me incorrect solution and I don't know why. Any ideas? Submission: https://codeforces.cc/contest/1611/submission/136924541
 » 7 weeks ago, # |   0 Can someone explain to me my own approach for C xD? During the contest this seemed natural to me, but now I cannot convince myself why this actually works. In short, I compare leftmost and rightmost elements of a and whichever is smaller goes to the corresponding side in p (if a[left] is smaller, a[left] goes to beginning of p, otherwise a[right] goes to end of p)Link
 » 7 weeks ago, # |   0 Can someone explain solution of E1?
 » 3 weeks ago, # | ← Rev. 2 →   0 For question 1611B; Team Composition: Programmers and Mathematicians: I have solved it in another way and it works. My idea is if |a-b| <= 1 then we divide each team into half Programmers and half Mathematicians which mean min(a/2,b/2) else we assume will assume a<=b always then we need to find c that makes the difference between a and b <=1 and since b is larger we will subtract b by 3 every time and a by 1 which mean we need to solve this equation (b-3c)-(a-c)=0 which gives us c = (b-a)/2 and our new a and b is a-c and b-3c and if a-c<= 0 then our answer is c else our answer will be c + min(a/2,b/2) (which mean we c teams that contain (1,3) Programmers &Mathematicians and min(a/2,b/2) which contains (2,2) Programmers &Mathematicians import math for _ in range(int(input())): a,b = map(int,input().split()) x = max(a,b) y = min(a,b) count = 0 if x-y <= 1: count = min(x//2,y//2) print(count) else: z = (x-y)//2 x = x-3*z y = y-z if y<=0: count += (y+z) print(count) else: count += z count += min(x//2,y//2) print(count) `
 » 11 days ago, # |   0 Even though this contest was a while ago, I wanted to share an alternate solution for F that doesn't use segment trees or two-pointers directly. I used a binary search on the length of the subarray along with a sliding window, prefix sums, and a multiset to find the first valid subarray of a particular length (or lack thereof). I have implemented this in $O(n\cdot \log^2 n)$, but with some extra work (swapping the multiset for a hashmap and maintaining some additional data), I think this could be implemented in $O(n\cdot\log n)$. 141773589