### 300iq's blog

By 300iq, 19 months ago,  Tutorial of VK Cup 2019-2020 - Final Round (Engine)   Comments (182)
 » 19 months ago, # | ← Rev. 2 →   Edit: Nvm, it's showing up now
 » How does the interactor work for F?
•  » » You can find Smith values for all vertices in $O(E \sqrt{E})$, and then all the arithmetic should be simple enough.
•  » » » Could you elaborate? (What's a smith value?)
•  » » » » The only source I know about Smith theory is Winning Ways For Your Mathematical Plays, chapter 12. In short, every position in such a game is equivalent to a nim heap $*k$, or $\infty_S$ for a set of non-negative numbers $S$. $\infty_S$ is winning if $0 \in S$, and a draw otherwise. Smith value of a position is one of these options.The addition rules are: $*a + *b = *(a \oplus b)$ (just Grundy), $\infty_S + *k = \infty_{S \oplus k}$ (XOR every element of $S$ with $k$), $\infty_S + \infty_{S'} = \infty_{\varnothing}$.
•  » » » » This paper has a short summary in section 6: https://www.msri.org/people/staff/levy/files/Book56/12siegel.pdf
•  » » » » I just wanted to ask you a question Benq. Tried to message you but was unable to do so."do smth instead of nothing and stay organized". What is "smth" in here? I am so curious and can not resist asking.
•  » » » » » something
•  » » » » » » Thank you. I googled "smth technique", "smth method", even "smth algorithm". But never searched only "smth". It just never crossed my mind.
•  » » » 19 months ago, # ^ | ← Rev. 2 →   Any tips on how you can compute the values in $O(|E|\sqrt{|E|})$? I figured out how to do it in $O(\sum_{i=1}^{|V|}degreein_{i} * degreeout_{i})$ which is bounded to $O(|V| * |E|)$, but I can't seem to find any improvement.
•  » » » » You can place $*k$ in a vertex $v$ if: there are edges from $v$ to vertices marked $*0, \ldots, *(k - 1)$, and no edge to a vertex marked $*k$; for each $u$ -- unmarked option of $v$ there is an edge to $*k$. If the rule can not be applied anymore to any vertex, then all remaining vertices are $\infty$'s.If all $*0, \ldots, *(k - 1)$'s are placed, then all possible $*k$'s can be placed in $O(E)$ with a reverse BFS-like traverse. We can stop after $k \sim \sqrt{E}$, since there has to be $\Omega(k^2)$ distinct edges for a $*k$ to exist.
 » Div2 C can be solved with binary search for the answer. 97454890
•  » » Sir, can you please tell me how did got to the solution of A? I just couldnt solve it after spending 2 hrs on it
•  » » » Well, this is how I thought: -the easiest way for gcd not to be one — to take even numbers only, so gcd of any two to them is at least 2. -Okey, now it is necessary that there are no pairs of numbers that one is divisible by another. And again the easiest way to do so is to make ratio of any two less than 2. So we would have no such pairs for sure.With two observations above I immediately got to the solution.
•  » » » » Thank you sir...really dont know how to bring those ideas even after regular practice..
•  » » » just see the example test cases and u will find a pattern that will satisfy the solution requirement e.g. 2*n,2*n+2,2*n+4 ....... these all have gcd greater than 1 and are not divisible with each other
•  » » » » yaa i tried to find something like that also but then... a very poor day
•  » » » 19 months ago, # ^ | ← Rev. 2 →   First find the mid of the interval [1, 4n] i.e 2n and now just print even numbers starting from 2n up to 4n. Here is the snippet: int t; cin >> t; while(t--) { int n; cin >> n; int mid = 2*n; for(int i = mid ; i < 4*n ; i+=2) cout << i << ' '; cout << '\n'; } 
•  » » Beautiful solution
•  » » » 19 months ago, # ^ | ← Rev. 2 →   In C? First, let's say we are given some time x. How can we determine whether it's possible to get all the food in no more than x?Let's go throw the a array. If a[i] > x then we need to go to take this item on our own. Summarise all such a[i]. If sum <= x, then it's ok, we can do this. Otherwise, it's not possible to do this in x.Now we can use binary search on answer. (read about it in internet). We can do this since for some first x-s we can't do this in no more than x and starting from some x, which we want to find, we can. So in fact just need to find the first x such that we can do that in no more than x. And to find it we use the binary search.
•  » » » » can you see my code for C ? 103697796i can neither understand the editorial nor your explanation.what i did was , i would add up the time of the user if and only if that resulting sum after going to restaurant is less than the max(delivery) time.But my solution is failing the 2nd test case itself ? #define f(n) for(int i=0;i>n; vi v(n); //vector f(n) { cin>>v[i]; } vi k(n); f(n) { cin>>k[i]; } ll s1=0,s2=0; if(ks2) { s2=v[i]; } } } // cout<
 » Straightforward dp solution, where s(i,j) – max possible sum after j operations on first i arrays and transition in O(k), has complexity of O(nk2) or precisely O(k⋅min(nk,∑i=1nti)) and doesn't fit into the time limit. Or does it?97479244
•  » » Suneet ORZ
•  » » Vectorization speeds up the 3000^3 main loop up significantly. (I didn't think that would be enough though, whoops.)Anyway, the problemsetters should have done better. Thinking of this solution is quite simple, and countering it is also simple (just raising both the limits and TL works.)
•  » » see https://codeforces.com/blog/entry/84257?#comment-718314 for another reference
 » Can someone please tell me in whats wrong with my this solution for Div2D ? Submission
•  » » I can give a counter testcase Try 1 5 2 5 4 5 3The answer should be no I think your code would output yes
•  » » » Ahh thanks I found my mistake...
•  » » The answer should be no in the following array But this program says yes~~~~~ 13 20 13 10 13 15 10 15 15 14 ~~~~~
 » 19 months ago, # | ← Rev. 2 →   In 1443D-Extreme Subtraction, my idea was to maintain two other arrays which will store the minimum element to the left of element in array and minimum element to the right of element in array respectively for each element in the array. This way I could check for all elements if they are less than or equal to the sum of left minimum element and right minimum element and if there is an element which is greater than this sum then for sure we can not reduce that element to zero. I passed the given test case but failed pretest 2. I'm attaching the code below please help if you can in letting me know where exactly I went wrong. Here is the code 97483817
•  » » The condition is not sufficient, e. g. your code prints yes for the following counterexample 5 1 2 1 2 1 (It's not possible, the output should be no)P.s. Please don't post whole code, since it makes the comment section longer and less readable
•  » » » Sir, can you kindly tell why the above approach of pythonPappi doesn't work?
•  » » » » As said, the described condition is necessary (all the inputs that produce "Yes" have to satisfy this condition), however, it's not sufficient (meaning that not every input satisfying this condition will have a "Yes" as solution). To see this, you can look at the counterexample I provided in my original comment. You need to come up with another condition.
•  » » » » » Actually I came up with the same example when my solution gave WA. So, from your reply, shall I conclude that the above solution is not logically incorrect but rather it's not sufficient to solve the problem??
•  » » » » » » Yep. Exactly. The actual condition is narrower than the condition mentioned.
•  » » I have exactly the same idea...
 » Div2B is simple. I wonder why I wasted my time to come up with a dp solution :))
•  » » waste a lot of time in dp +1
•  » » Can you explain your DP solution?
•  » » i have solved Div2B with a dp solution XD
•  » » » 7 months ago, # ^ | ← Rev. 3 →   I came up with a DP solution similar to yours where I first remove all leading and trailing zeroes from the string but I am now wondering how this solution will work correctly for the case:10 1 01 Optimal strategy should be to put a mine under 0th house using 1 coin, this will also activate the mine under 1st house. So answer should be 1, but your solution gives 10 for this case. What am I missing?This is your DP solution I am talking about: https://codeforces.com/contest/1443/submission/97455404EDIT: Got it, its because b coins is only the cost for placing a mine, you need another a coins to activate it.
•  » » the same for me
 » I want to cry out loud, got almost all things in problem C except the case when you have to bring all the parcel on your own!!! I feel it happened because I stressed out in the last, won't do that from next time. AC https://codeforces.com/contest/1443/submission/97496785
•  » » » Why be so toxic?
 » 19 months ago, # | ← Rev. 2 →   Can anyone tell what is wrong with the following code ? This is the approach that i have taken for the problem — D (Div-2) https://codeforces.com/contest/1443/submission/97494454
 » Problem C of div2 can also be done using binary search on the ans.Here is my submission 97456070
•  » » Can someone tell what I am missing in my thought process #include using namespace std; unsigned int factorial(unsigned int n) { if (n == 0) return 1; return n * factorial(n - 1); } void input(int a[],int n) { int i; for(i=0;i>a[i]; } int main(){ int t; cin>>t; while(t--){ int i,j,n; cin>>n; int *a =new int[n]; int *b =new int[n]; for(i=0;i>a[i]; for(i=0;i>b[i]; int m1=a,s2=0,m2=b; for(i=0;ib[i]) m2=b[i]; s2+=b[i]; } // m1=max(a,n); s2=sum(b,n); m2=min(b,n); if(s2<=m1) { cout<>v; pairp; for(i=0;i>()); int has[n]={0}; int s=0,ans=INT_MAX; for(i=0;i=s) { ans=v[i].first; } else{ break; } s+=v[i].second; has[i]=s; } cout<
 » What does engine editorial mean?
•  » » 19 months ago, # ^ | ← Rev. 2 →   This VK cup contest has several tracks (mobile, design, machine learning), and one of them is called "engine" which is basically a competitive programming track.
 » Div2D/Div1A tagged dp and greedy. Anyone please explain dp solution.
 » Can problem C solved by DP??
 » In Div-2 D,The problem sounds like this — check that there are increasing and decreasing arrays, the element-wise sum of which is equal to the given array.Can someone elaborate on what this means and how it relates ?
•  » » If we could only decrease prefixes, then the whole array would need to be non increasing. If we could only decrease postfixes, then the whole array would need to be non decreasing.Since we can do both, it must be a sum of both.
•  » » same, what is "the element-wise sum"?, can someone explain it?
•  » » » Consider a non-decreasing array1 [2,4,5,8,11] and a non-increasing array2 [14,8,5,5,1]. As said above: If we could only decrease prefixes, we would want the array to be something like array2. If we could only decrease suffixes, we would want the array to be something like array1. Since we can do both, an array of the type array1 + array2, i.e. [2+14, 4+8, 5+5, 8+5, 11+1] would also give us a "YES"
•  » » » » can you explain how to check that?
•  » » » » Thanks for really helpful explanation)
•  » » » » The tutorial should have had this example..!!
 » 19 months ago, # | ← Rev. 2 →   Very short $O(n)$ solution for div2F/div1B 97497692, but I'm not fully clear about why it works.
•  » » Take a look at this submission 97441804.
•  » » » The idea is the same I think.
•  » » 19 months ago, # ^ | ← Rev. 2 →   Try to prove these facts: if $a_{i-1}$ hasn't been chosen yet, but it will be chosen later, and $a_i$ exists (1), then they are still adjacent in the current array if $i \neq 1$, $a_i$ exists and $a_{i-1}$ has already been removed (2), then $a_i$ is adjacent to the left to a visited integer in the current array if $i \neq 1$, $a_i$ exists and neither (1) nor (2) holds, then $a_i$ is still adjacent to $a_{i-1}$ in the current array
 » For 1443A — Kids Seating, If there are 3 kids, can't we print "202 204 206" as answer? I get this when i submit the code "wrong answer Integer element [index=1] equals to 202, violates the range [1, 8] (test case 1)"
•  » » every number must be in the range 1 to 4n
•  » » » Gosh How did i over look that
 » Can someone give an explanation for div2D solution? I can't really understand what is written in the editorial.
•  » » Editorial of D is written for those who have solved D, I think :(
•  » » Observation 1:- We can do operations in any order it doesn't affect our final array A.Observation 2:- If we do all prefix operation first and after it we get an array A which is non- decreasing then the ans is YES(as now you can apply suffix operation and decrease one by one from last also all elements must be greater than or equal to 0) if we get any other array then the ans is NO.now our only motive is to make the array non-decreasing after applying prefix operations.Why observation 2 is correct(with example) :- A = [12,7,20,8,17] step 1 -> at first we can decrease A to 7 A = [7,7,20,8,17]step 2 -> Since 7 7 20 is already in non decreasing order now we check 20 and 8 ..... since 20 > 8 so we have to decrease our first k(k=3) elements by 20-8 to make 20 equal to 8 . A = [-5,-5,8,8,17]though we got an non — decreasing array but our First two elemnts are less than 0 so ans = "NO"for more clarity https://codeforces.com/problemset/submission/1443/97522500sorry for bad english.
•  » » » I_will_come_back you explained really well! I really wish that the editorials are written in great detail so that everyone understands.
•  » » » » Thanxx mate... Ya i also feel same for some editorials....
•  » » » very nice, thanks!
•  » » » Your explanation is really easy to understand!
•  » » » mast explanation diya brother :)
•  » » » A legendary greedy solution, bro.
•  » » » Sir, your approach is abs awesome...Scarcity of words to describe the beauty of your solution....Hope one day I shall be able to do the same
•  » » As stated in other comments, We can just chose to perform all the prefix operations first. In that case, the array after performing the prefix operations must be non-decreasing. I saw I_will_come_back's submission. Thank you for the explanation. Just wanted to post a simpler way to solve it using the same concept.So I traversed the array from the end and kept a count of the decrement till the index 'i' For eg. [11 7 9 6 8] initially: count =0 , i = n-2 Since the final array should be non-decreasing,Whenever we encounter, arr[i]> arr[i+1] we'll update count and arr[i] i.e. for i = 2 here, arr[i] will become 6 and count will be updated to 3. After the loop, we just need to check if all elements in the modified array are >=0 or not. Take a look at my submission if needed.97652518 Have fun coding :')
 » Why this code is getting different verdicts for the same code in C++17(64) and C++17 ?
•  » » Accessing a[i] if i is out of bounds is undefined behavior. Anything is allowed to happen. Maybe your solution is just too slow, but in one case you were lucky to get runtime error. Another theory is that accessing a[i] for some big i overwrote n causing your loops to go on very long.
•  » » » Thanks! n must have been overwritten. The solution isn't slow, this submission got accepted. This thing ruined my contest, I am not using global variables ever again.
•  » » » » Global state is evil, but I'm not sure how you will prevent out-of-bounds access just by not using global variables.
•  » » » » » Would double check too. I wouldn't at least get weird verdicts by not using global variables.
 » 11 6 7 10 9 9 8 ,can anybody explain why and how it is yes
•  » » 19 months ago, # ^ | ← Rev. 2 →   11 6 7 10 9 9 8 6 6 7 10 9 9 8 6 6 6 9 8 8 7 6 6 6 6 5 5 4 5 5 5 5 5 5 4 4 4 4 4 4 4 4 0 0 0 0 0 0 0 BTW, my solution to Div2.D problem.
 » This may be a dumb question but how is the answer for sample 3 in div2D NO?Is the following not a possible sequence of performing operations?[1 3 1 3 1] -> [0 2 0 3 1] -> [1 2 0 3 1] -> [2 2 0 3 1] -> [1 1 0 3 1] -> [0 0 0 3 1] -> [0 0 0 2 0] -> ... (and similarly for the 2 0 in the suffix)
•  » » You can't increment! The question states that you can pick first k or last k elements of the given array and decrement it by 1.
•  » » » Oh okay thank you :)
 » Made the silliest mistake of my life in Div2D.if(n==1) cout << arr << endl;instead ofif(n==1) cout << "YES" << endl;:(
 » is it rated?
 » 19 months ago, # | ← Rev. 2 →   Just to mention, as a full-BFS solution to Div.1 problem C:Let $base_{0,u}$ be the minimum (even) number of required transpositions to reach the vertex $u$. Similarly let $base_{1,u}$ be the minimum (odd) number of required transpositions to reach the vertex $u$.(Note that their difference wouldn't be greater than 1.) We can evaluate $base$ numbers by a 0-1 BFS algorithm:Create a graph with a node for each of the $base$ array cells; Connect $(i, u)$ to $(1 - i, u)$ with a 1 weighted edge. For each u->v edge in the original graph, connect $(0, u)$ to $(0, v)$ with a $0$ edge. For each u->v edge in the original graph, connect $(1, v)$ to $(1, u)$ with a $0$ edge. Now declare $dis_{u, i, j}$ as the minimum number of token movements needed to reach $u$ while $base_{i, u} + j$ transpositions have been applied and the oddity(# % 2) of the applied transpositions is equal to $i$(Yes! Half of the states are unused/invalid.). To update $dis$ values, create a new graph with a node for each triple $(u, i, j)$. Connect $(u, i, j)$ to $(u,\ !i,\ j + base_{i, u} - base_{1 - i,\ u})$ with a $0$ edge. For each u->v edge in the original graph, connect $(u, 0, j)$ to $(v, 0, j + base_{0, u} - base_{0, v})$ with a $1$ edge. For each u->v edge in the original graph, connect $(v, 1, j)$ to $(u, 1, j + base_{1, v} - base_{1, u})$ with a $1$ edge. Then run a 0-1 BFS from the $(1, 0, 0)$ node to evaluate each $dis_{u, i, j}$.The answer equals to the minimum value among $2^{base_{i, n} + j} + dis_{n, i, j}$ with all of the possible $i, j$ values.It can be easily proved that it's enough to set the $log(m)$ as an upper bound for $j$(third argument of $dis$) and still solution works correctly. So the size of $dis$ would be $n . 2 . log(m)$ and the whole solution would work with $O((n + m).log(m))$ time complexity.
•  » » Is this just for the first part of the problem? What about when you have to do $m-1$ transpositions? (A line graph with alternating directions on edges.) It seems $j$ will have to be $O(m).$
•  » » » Not actually; Note that $j$ is the difference between "minimum number of required transpositions to reach $u$(i.e. $base_{i, u}$)" and "the actual number of applied transpositions to reach $u$ in an optimal way", this difference wouldn't exceed $log(m)$.I think in your example $base$ values would be large enough(almost equal to m or n).
•  » » » » Oh, of course, I understand the definition now. Cool!
 » Is there any explanation (proof) for 1442B — Identify the Operations for a fact that decisions 1..X-1 (to pick i-1 or i+1) doesn't influence outcome of step X? Basically that it doesn't matter what we did before, step X will always have 0, 1 or 2 options for all possible sequences. I got AC, but wasn't able to prove it.
•  » » 19 months ago, # ^ | ← Rev. 2 →   Here's my thought:Suppose that we're currently processing $a:=b_i$ and let $c:=b_j$ for some $j>i$. There are two possible cases that previous operations influence our current choice: $a$ moves to the border $a$ and $c$ become adjacent. The first case is impossible because, before $a$ moves to the border, the number between $a$ and the border must be deleted and thus $a$ is added to $b$, but numbers in $b$ are unique, so it's impossible. The proof for the second case is similar.
•  » » We need to choose the elements in b[] in given order. So, foreach the coresponding a[i] we can choose the left or right neighbour if it exists. Doing so does not change the number of chooseable neigbours of other elements. Because the removed one is replaced by the choosen one. Because of this the 0, 1 or 2 is invariant.
 » I have an easier solution for Div2F — Div1B: Go through the elements of b, look the position of the current number in b. If there is only one possible neighbour to delete (either on edge of list or one neighbour is a future number in b) take it, if there is no possible neighbour then the answer is 0, and if both are possible you can take either one since the result is in each case the same (the other not taken numbers are equal to the other two possible not taken numbers, each of those numbers can be taken in the future and which two we take doesn't influence the indexes of future takes). You can maintain this with a linked list, nodes have two pointers for neighbours, EZ O(n). Here's my submission: https://codeforces.com/contest/1443/submission/97489269, it's ugly cuz I didnt have much time left, should have made some Node classes instead of just keeping it in an array but thankfully I didn't make any mistake while implementing it (unlike on most tasks in the contest lmao).
•  » » nvm the solution in the editorial actually isn't really different, I just thought it must have been cuz it was nlogn. The problem was really easy for a F type.
 » In problem B, I used memoization. int memo[1e5+1]; I do a memset(memo, -1, sizeof memo); at the beginning of each test case.There are 10^5 test cases, and i do memset at each one of them. yet my solution was accepted !!? any explanation? https://codeforces.com/contest/1443/submission/97508001
•  » » It looks like the answer could be weaker test cases — even though the limit is given as 1e5, the max value in the test cases seems to be about 11000. Whilst this would still result in many operations, my understanding is that 1e9 of the very simplest operations is achievable in the time limits. You could try a custom invocation with 1e5 test cases and I suspect it might fail. I’m not certain, though.
•  » » Maybe the test data is too weak...I even saw that someone use an $O(n^2)$ algorithm to pass a problem that $n\leqslant 10^6$. It worked successfully and accepted the problem :)
•  » » Your code passes T = 1e5 in 900 ms :)
 » 19 months ago, # | ← Rev. 2 →   How to solve Div1B — 1442B - Identify the Operations if the resulting array $b$ is not distinct?
•  » » 18 months ago, # ^ | ← Rev. 3 →   is A also not distinct?
 » 19 months ago, # | ← Rev. 2 →   I thought I'd share my solution for 1A as I think it's way more interesting than the editorial's solution.Let's assume the input array $a$ is the prefix sum array of some array $b$. Then it's obvious that $b_{i} = a_{i}-a_{i-1}$ for all $i \geq 2$ and $b_{1} = a_{1}$. Now we simply check to see if the absolute value of the sum of negative elements in $b$ is strictly greater than $a_{1}$. If it is, the answer is "NO" otherwise "YES"This boils down to the fact that an operation on the prefix decreases $b_{1}$ by $1$ and increases $b_{x}$ by $1$ where $x$ is the length of prefix chosen. An operation on the suffix simply decreases $b_{y}$ by $1$ where $y$ is the length of suffix chosen. Because of the 2nd operation, we can always make the entire array $0$ if array $b$ consists of all non-negative numbers. In order to make negative numbers $0$, we have to "move" a $1$ from $a_{1}$ without letting $a_{1}$ becoming negative itself.97513072
•  » » Perfect. but it is hard to come up with a solution like this At least for me in contest time or may be after that :).
 » In DIV1C, for the second part, when we know that B > log2(m), I used Dijkstra where distance is a pair where the first part of pair is B and second is A (B and A are same notations used in Editorial). Instead of splitting the graph into two different graphs, I used the number of transpositions till now to decide whether I can traverse the edge or I need to transpose it again. I ensure the minimum value of B, and if B is same, then I checked the value of A. But this approach is getting wrong answer on test 7, and I'm not sure whether there is something wrong with my approach or I can't implement Dijkstra in this way. Please help me understand my mistake. I really appreciate any help you can provide. Link to my submission.
•  » » 19 months ago, # ^ | ← Rev. 2 →   Consider 3 vertices a, b and c. You are currently in a, but you need to reach c, and the only way to do that is through b. To reach b you can either transpose and go to a short path to reach b, or you take a long path to reach b without transposing. But once you reach b you need to transpose to reach c, so it would be better to have transposed earlier (in a) so you could take this shorter path. Thats why you need to duplicate the graph, you cannot transpose lazily.
•  » » » It took me some dry runs to understand what you are saying, but I finally understood it. Thanks a lot.
 » I have a solution that is different from 1443A: You can preprocess the first 100 prime numbers and, when you print the answer, times 2 for each number and that could be fit for the request of the problem :)
•  » » It will run into an issue for n=6 (it gives 4, 6, 10, 14, 22, 26). Here, 26 exceeds the limit of 24 (4*n). I started solving it that way and ran into this issue — had to improvise. However, the editorial solution is cleaner (i.e. take multiples of 2 starting backwards from 4*n, you'll be okay every time — since their gcd will be at least 2 and they won't divide each other).
•  » » I tried that but it had some problem. Like when n = 5, then your answer is 4, 6, 10, 14, 22. But 22 violates the range [1, 20]
•  » » Oh I forgot! I didn't pass using the algorithm :(
 » Why didn't you post analysis for 1441F - Matching
•  » » Fixed
•  » » » I still don't see it. Also, could you open up that contest (or at least that problem) for practice?
•  » » This is apparently a classical problem. This 2001 paper has the solution: https://collaborate.princeton.edu/en/publications/unique-maximum-matching-algorithmsThe main observation is a theorem of Kotzig: Consider any graph with a unique perfect matching. Then, that perfect matching contains a bridge of the graph. Intuitively, any biconnected graph has either 0 or at least 2 perfect matchings, because there are enough cycles to find a second matching. I found a short proof here: https://arxiv.org/abs/1402.0949.Now, to solve the problem, we just need to repeatedly identify bridge edges, decide if the two components it connects are odd-sized, and if so, use the edge and delete both endpoints. We can do this with merge-smaller-into-bigger or parallel-BFS type algorithms on the faces.
 » div2C- 0) lets sort a in non increasing order 1) lets say we want all dishes to be delivered, then the time needed is a(the maximum) 2) If we want to reduce the time the only way is to pick 0th dish on our own, as picking any other dish will not reduce the total time 3) we go and pick the dish on our own if that reduces the total time, and the total time if we pick the 0th dish on our own is max(a,pick_time+b), so we update the total time to be this if it is less than a 4) we do this in while loop until last dish https://codeforces.com/contest/1443/submission/97496785
 » I had different solution for problem C. I searched for the minimum number of steps that we should make if we are allowed to make up to $T$ transpositions. To find such value we can duplicate all nodes, assign cost 1 to regular edges, and cost $X$ to edges that make transposition. Then, with binary search we can find such values. To avoid several binary search, we can run a single binary search that looks for all values at the same time.I didn't put too much thought about what was the complexity of this solution during the competition (lucky me). The complexity is $O(|V| \cdot \log |E| \cdot |C| \cdot \log |C|)$ where $|C|$ is the total number of distinct target paths that exist. Target paths are those such that a value $X$ exists where $T \cdot X + steps$ is minimum among all paths. During the competition I thought this number was bounded by $O(n^{\frac{1}{4}})$ but it turns out that there are graphs where the number of distinct target paths is $O(n^{\frac{1}{2}})$.I managed to hack my solution with one such graph.
 » 19 months ago, # | ← Rev. 5 →   I was solving div2B, and found this unexpected runtime error in the below piece of code, can anyone explain what's going on?while debugging, I found that even after prs.size()==0, for loop is getting executed and then giving the error. Pls help. for(int i=0; i<(prs.size()-1); ++i){ int diff = (prs[i+1].first - prs[i].second -1); if((diff*b)
•  » » prs.size() is unsigned type, so prs.size()-1 is unsigned, too.
•  » » » thanks!
 » 19 months ago, # | ← Rev. 2 →   What is the proof for Div1B? Let's say the answer to the problem is not $0$. Then how to prove that in the case $(3)$ while choosing any of the $a_{i-1}$ or $a_{i+1}$ will always lead to the solution in the end rather than ending up in a contradiction later on.
•  » » 19 months ago, # ^ | ← Rev. 2 →   First, we can notice, that the actual values are not very important. Let's use | to denote something that we will use later, and . to denote something removable. You should note, that the order of the | chosen is still important, though not represented here.So our array looks like ..|...|...|...|...|....Now we can see that one of the | will be next. After we add it to the array b, it is useless, and removable like a ., because all values in "b" are distinct. So using either |. and .| in .|. yield a ... So the next state is the same regardless of whether we choose left or right.
 » Can someone Pls suggest some more problems like div2D/div1A.
•  » » it's the easiest pblm in this contest! A was way harder for me! -_-
 » Don't know who needs this counter test case in div 1C but I definitely did, so I'll share it: 9 9 2 1 2 3 9 3 1 4 4 5 5 6 6 7 7 8 8 3 Expected Output: 8
•  » » I need! :D Thanks ;)
 » Can anyone please explain why I am getting TLE 97543660
 » 19 months ago, # | ← Rev. 3 →   I think the test data of Div2D/Div1A is not so strong, here is an accepted $O_{(n^2)}$ solution.
 » 19 months ago, # | ← Rev. 2 →   About Div.1 D, I have another solution with complexity O(nklgn)，the idea is that some of element will never be choice.Then we calculate the prefix sum and sort the column，for the j-th column the last n-1-k/j element will never be choice. here is code. https://codeforces.com/contest/1442/submission/97548953
•  » » Can you please say why the last n-1-k/j element will never be choice for j-th column?
 » Someone can explain Div2E task. How we generate a permutation with the corresponding number?And why only the last 15 elements need change, if there may be such a situation when the last 15 elements are initially in descending order and the 16th element needs to be changed
•  » » Please someone explain the div-2 problem E LONG PERMUTATION of this contest .! what 15 they mentioned in editorial and why ?Thnx in advance ...
•  » » 19 months ago, # ^ | ← Rev. 2 →   There are n! permutations of {1,2,3,...,n}. But how do they look in lexicographic order?Let's look at first 6 permutations (n >= 3): 1: {1,2,...,n-2,n-1,n}, 2: {1,2,...,n-2,n,n-1}, 3: {1,2,...,n-1,n-2,n}, 4: {1,2,...,n-1,n,n-2}, 5: {1,2,...,n,n-2,n-1}, 6: {1,2,...,n,n-1,n-2}. As you see, only last three elements were changing their positions. Why? Because 3! = 6, so first 3! = 6 permutations only permute last 3 elements. In general, for given 1 <= k <= n first k! permutations of {1,2,...n} only last k elements change their positions, the first n-k elements are always {1,2,...,n-k} in that order."And why only the last 15 elements need change?" - Let's notice that we have x <= 2e5 and q <= 2e5 and we start from X=1 permutation index. Therefore at the end maximum possible index is X <= 1 + 2e5 * 2e5 = 4e10 + 1. Just because 15! > 4e10 + 1, we know that only last 15 elements can change. In fast it is sufficient to look at 14 last elements, as 14! = 87178291200 > 4e10 + 1."How we generate a permutation with the corresponding number?" - We can enumerate all permutations of {1,2,...n} with integer numbers from [1,n!]. An example algorithm of retrieving permutation from its index is explained here: https://www.geeksforgeeks.org/find-the-k-th-permutation-sequence-of-first-n-natural-numbers/. However, this code returns string and assumed an integer index, but in our case it can exceed integer range, remember about it. My code (https://codeforces.com/contest/1443/submission/97579828) uses this approach to retrieve permutation from index, you can look at it.
 » Nice Contest!
 » 19 months ago, # | ← Rev. 2 →   In editorial of problem Div2 D : How to prove that " maximizing each element of the decreasing array" is the best way to construct the increasing and decreasing array and can people tell their train of thought while arriving at above during contest.
 » Please help me to find what I did wrong in my code.https://ide.codingblocks.com/s/367339In my Approach, I simply created two partial sum arrays. The first from the beginning called pre and the second from the end call sum.
 » D <= C <= B <= A <= F <= E for div2 -_- A ruined my whole contest!
 » How do I find the law of problem A? I find problem B much easier: v
•  » » To get rid of GCD(a,b)=1, choose only even numbers which will make sure GCD is 2 at least.For the second condition, which says if we consider a pair (a,b) then neither a should divide b nor b should divide a. The clue- "The only number that divides a number after the number itself is number/2."So if you start with 4*n, the next which divides it is 2*n.So going from 4*n to 2*n+2 is the safest option.Hope you find it useful
•  » » » I understand then thank you very much :>
 » Did anybody solve div2D using segment tree like me :v
•  » » Here is LimitBreaker's submission with segment tree, just in case.
 » in kids seating i started with n=4 and then did n+2, but got wrong answer. Can anybody explain.
•  » » I saw your submission. You assumed c=4, and then went on printing c,c+2,c+4,c+6.....Let's say the input n=3. Your code will output "4 6 8" This output passes the first condition but it fails the second condition, which says if we consider a pair (a,b) then neither a should divide b nor b should divide a.The pair (4,8) clearly disobeys the second rule.Your approach was partially correct, but it needs improvement. Choosing even numbers to get rid of GCD(a,b)=1 was a good thought. Instead of starting from 4 and going in the forward direction, you should have started from the last number possible, i.e 4*n, and go onto 2*n+2."The only number that divides a number after the number itself is number/2."So if you start with 4*n, the next which divides it is 2*n.So going from 4*n to 2*n+2 is the safest option.Hope you find it useful
•  » » » Thank u so much man, I misunderstood the problem and thought that a and b are any two consecutive numbers.
 » Can someone please explain the binary search approach for the answer in "1442B — Identify the Operations"? Thanks in advance!!
 » I am getting Memory limit exceed in DIV2 B. if anyone can help plz. I really appreciate it ! Thanks in advanceMy Code
 » 19 months ago, # | ← Rev. 2 →   someone please explain how third statement is correct? According to me array should become [2 1 0 -1 2]1.decrement from the first two elements of the array. After this operation a=[2,1,2,1,4]; 2.decrement from the last three elements of the array. After this operation a=[3,2,1,0,3]; 3.decrement from the first five elements of the array. After this operation a=[2,1,1,0,3];
 » Can someone tell me how the divide and conquer works in Div1 D?
•  » » 19 months ago, # ^ | ← Rev. 2 →   Basically, we are aiming to solve knapsack problem (precisely, calculate entries of dp array) for $n$ elements but $i$-th one for all $1 \le i\le n$ mentioned in the editorial.Here, we will divide $n$ arrays into two halves ($A$ and $B$), and then calculate the dp array $dp_l[]$ (resp. $dp_r[]$) if we take the first half (resp. second half) elements into account， i.e. we are free to choose any subset of the first half(resp. second half) elements. With auxiliary array $dp_l[]$(resp. $dp_r[]$) in hand, we may only focus on the initial problem for the second half(resp. first half) and merge them in the obvious way.btw, you may check others' implementation to get a better understanding. (That's how I understood above approach... I was confused by editorial as well)
•  » » » I understand , thank you very much:)
•  » » » Can you more explain what does it mean?"With auxiliary array dpl[](resp. dpr[]) in hand, we may only focus on the initial problem for the second half(resp. first half) and merge them in the obvious way."
 » For problem C, why does Accepted one works while this almost identical one Wrong One gives memory limit exceeded . The only difference between the two solution is that I copied the contents of the loop from the wrong one and pasted it in a function, then called it instead in the loop to solve, and now I don't get memory limit exceeded using the function. Why is this happening ?Problem C
 » Can anyone please explain me problem D of div 2. I am not getting it
•  » » 19 months ago, # ^ | ← Rev. 2 →   We can decrement any suffix by 1. We can decrement any prefix by 1.Now we are asked if its possible to make each element of given array as 0 by performing above 2 operations.
•  » » » thanks but i am not getting how taking difference and subtracting it from first element and checking that it is greater than or equal to 0 give yes. Please can you explain it.
•  » » » » Honestly I myself couldn't understand the editorial solution. I solved using a different approach about which you can find here
•  » » » » » thank you for your help.
•  » » » » » » Welcome.
 » I've written a blog post to explain the solution to 1443D (D1A / D2D)
•  » » I think your blog has been removed.
•  » » » Nope it's still there?
•  » » » » It shows me you are not allowed to view the requested page.
•  » » » » » That's bizarre, likely some bug in the site. cc'ing MikeMirzayanov as I'm not sure where else to post site issues
 » Squeezed $O(n k \sqrt n)$ solution in D1D. With pragmas submission
 » Div 2 B -> 1100011 .. In this example we just need to replace the 0's at position 3 and 5 and activate them , why in all the explanations they all are counting all the zeros between the and then comparing with the activation value of the mine. c=count of 0's between the 1'sWhat they all are doing is ans+=min(a,b*c)I just need to place mine at 3th and 5th position and activate . Is it necessary to place mine at all zeros?
 » Good evening, this is our solution for problem C with explanation. »

I am writing my code for B but it is not getting accepted . Can anybody tell me what is the problem

# include <bits/stdc++.h>

using namespace std;

void io() { ios_base::sync_with_stdio(false); cin.tie(NULL);

# ifndef ONLINE_JUDGE

freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);

# endif

}

int main() { io(); int t; cin >> t; while (t--) { int a, b; cin >> a >> b; string s; cin >> s; int start = -1, end = -1; for (int i = 0; i < s.length(); i++) { if (s[i] == '1') { start = i; break; } } for (int i = s.length() — 1; i >= 0; i--) { if (s[i] == '1') { end = i; break; } } int seg = 1, ct = 0; if (start == -1 || end == -1) { cout << 0 << '\n'; } else { for (int i = start, j = start + 1; j < end; i++, j++) { if (s[i] == '1' && s[j] == '0') { ++seg; } if (s[j] == '0') { ++ct; } } cout << min(seg * a, (ct * b) + a) << '\n'; } } }

 » Can anyone explain me B.Saving the city?? Even a little hint would be appreciated
•  » » 100154641 You are welcome!
 » In C I used multimap and it was ac,then i used map and for multiple same courier delivery time i kept summation of all the pick up time at the index of that courier delivery time.Rather than this one difference everything else was same.why it isn't working? Example 3 3 5 5 / 2 2 2 2 I kept 4 at index 3 and 4 at index 5.Here are my submissions: AC:https://codeforces.com/contest/1443/submission/97495754 WA at TC2:https://codeforces.com/contest/1443/submission/98000111
•  » » I'm retarded
 » Div 1C is just pure genius (the making copies of graph part). Never seen this before. Just....wow.
 » can anyone help me with the first problem how in editorial come into that conclusion??
 » 300iq This page is not linked with the contest problem page neither is the announcement page .. Can you please look into it
 » How is this possible, as written in the editorial, 1442B has the power of 2 as the answer but as specified in the output, judge expected 150994942 which is not a power of 2Proof: My solution, see test 10 :/
 » memory efficient DP approach for problem B: https://codeforces.com/contest/1443/submission/101710030