### awoo's blog

By awoo, history, 4 years ago, translation,

1463A - Dungeon

Tutorial
Solution (Ne0n25)

1463B - Find The Array

Idea: BledDest

Tutorial
Solution (Ne0n25)

1463C - Busy Robot

Idea: KAN

Tutorial
Solution (pikmike)

1463D - Pairs

Tutorial

1463E - Plan of Lectures

Idea: BledDest

Tutorial
Solution (pikmike)

1463F - Max Correct Set

Idea: Neon

Tutorial
Solution (Ne0n25)
• +90

| Write comment?
 » 4 years ago, # |   0 great tutorial and congratulations on completing century of educational rounds... wow
•  » » 4 years ago, # ^ |   +31 another approach for B is that we can round DOWN the value at each index to the closest power of 2. Then just print the array. Although it was a tougher contest than usual, as far as i know.
•  » » » 4 years ago, # ^ |   0 2∑i=1n|ai−bi|≤S How is this condition satisfied in the solution you mentioned?
•  » » » » 4 years ago, # ^ | ← Rev. 3 →   +1 When you round DOWN any number to the nearest power of 2, new number will still be greater than or equal to half of the current value. EXAMPLES:32 round DOWN TO 32 itself(nearest power of 2).30 round DOWN TO 16 (nearest power of 2).in above example it is clearly seen or observed that new number will still be greater than or equal to half of the current value.... THAT IS IT IS MAXIMUMLY REDUCED TO HALF OF INITIAL VALUE.NOW ARRAY EXAMPLE: A1 A2 A3 A4transformed to B1 B2 B3 B4WHERE EVERY Bi IS EQUAL TO NEAREST POWER OF 2.(A1+A2+A3+A4)=SSO (A1-B1)<=(A1/2)SO (A2-B2)<=(A2/2)SO (A3-B3)<=(A3/2)SO (A4-B4)<=(A4/2)NOW DOING SUM ON BOTH SIDES:THUS SIGMA(Ai-Bi)<= ((A1/2)+(A2/2)+(A3/2)+(A4/2)) SIGMA(Ai-Bi)<= (A1+A2+A3+A4)/2 SIGMA(Ai-Bi)<= S/2 2* SIGMA(Ai-Bi)<= SHENCE PROVED
 » 4 years ago, # |   +2 another approach for B is 2^k
•  » » 4 years ago, # ^ | ← Rev. 4 →   +5 Let x[i] = log2(a[i])then b[i] = 2^x[i]. It can be prove that sum of all 2*|a[i] — b[i]| always <= SThis problem can be extend to k*|a[i] — b[i]| <= S. It will be so funny XD
•  » » » 4 years ago, # ^ |   0 Proof: At first, if each b[i] is a power of 2 the first condition will be done. Let's prove the second condition will be done too. It means that b[i] >= ceil(a[i] / 2) for each i. If b[i] is equal to 2^k, where k = floor(log2(a[i])) the second condition will be done as well. Let's say x = a[i] = 5. It's 101 in binary representation. y = b[i] = 4. It's 100 in binary representation. Then, x / 2 = 5 / 2 = 101 >> 1 = 010 = 2. After the operation the highest bit in x / 2 will be equal to 0, but at the same time it's equal to 1 in y. Hence, y > x / 2. We have proved it.
 » 4 years ago, # |   +1 I'd love to see a clean implementation of problem 2C in C++, if possible. Can someone point me in the right direction here?
•  » » 4 years ago, # ^ |   +3 Maybe you can have a look at my code. It is easy to understand I think.
•  » » » 3 years ago, # ^ |   0 Thanks a lot. I've spent half an hour thinking about an algorithm which has an O(nlogn) time complexity but I didn't get accepted. The solution is really an ingenious solution. Thanks very much!(P.S.: I'm a foreigner, if I made spelling mistakes, please forgive me. Thank you.)
•  » » » 3 years ago, # ^ |   0 I still can't understand the code, please explain the last condition if possible
•  » » » » 3 years ago, # ^ |   0 In this solution, l and r are the begin time and the end time of the last command isn't ignored, and from and to are the begin position and the end position of the command.If t[i]>=r, the last command that isn't ignored changes into i, so update the four variables and check if it is successful.Otherwise, calculate the position range $[l_{now},r_{now}]$ that robot stays in the time range $[t_i,t_{i+1}]$. To do this, we first determine the direction of the last command with (to-from)/(r-l). ($-1$ means left and $1$ means right) Second, at time moment t[i], robot moved for t[i]-l seconds, and at time moment t[i+1], robot moved for min(t[i+1]-l,r-l) seconds. (the robot may stop before the time moment t[i+1] so don't forget the min) Of course, if l_now>r_now, you need to swap them. Finally, you can just check if it is successful by checking if x[i] is in the range $[l_{now},r_{now}]$.
 » 4 years ago, # |   0 Can anybody say other approaches of problem B?
•  » » 4 years ago, # ^ | ← Rev. 2 →   +14 Yes. For example, we can print 2^k, where k = floor(log2(Ai)) for each i.
•  » » 4 years ago, # ^ |   0 My submission: https://codeforces.com/contest/1463/submission/101614243
•  » » 4 years ago, # ^ |   0 Proof: At first, if each b[i] is a power of 2 the first condition will be done. Let's prove the second condition will be done too. It means that b[i] >= ceil(a[i] / 2) for each i. If b[i] is equal to 2^k, where k = floor(log2(a[i])) the second condition will be done as well. Let's say x = a[i] = 5. It's 101 in binary representation. y = b[i] = 4. It's 100 in binary representation. Then, x / 2 = 5 / 2 = 101 >> 1 = 010 = 2. After the operation the highest bit in x / 2 will be equal to 0, but at the same time it's equal to 1 in y. Hence, y > x / 2. We have proved it.
•  » » » 4 years ago, # ^ | ← Rev. 2 →   +1 As you pointed out, getting the nearest $2^k \leq x$ can be done by only keeping the most significant bit (MST) of $x$. Therefore, if we could get the number of trailing bits from the MST, we would have $k$. You can implement this by yourself, but you can also make use of GCC compiler built-in function __builtin_clz() which counts the number of leading 0-bits from the MST (refer to here, I think it's a very useful post). Then, considering an int variable type has 32 bits, $k =$ 31-__builtin_clz(x) (subtraction is from 31 as otherwise we would count the MST, too). Having this, calculating powers of two it's easier and faster using the shift operator (<<), as $2^k =$ 1<
•  » » » » 4 years ago, # ^ |   0 Good job! Thank you a lot!
•  » » 4 years ago, # ^ | ← Rev. 2 →   0 Here's a different solution which I think is a little more simple, (my code 101560737)You can alternate between taking the number in A and taking 1. So your array B The intuition is that will look like this: B = [ a, 1, a, 1, a ... ]The differences will be, A — B = [0, a-1, 0, a-1, 0 ....]although it may happen that the difference is bigger if you take the zeros when a_i is a big number.However we can prove that by taking zeros on either the even indices or the negative indices, we get a sum of at most S/2 (S being the sum of all elements in A)[0, a-1, 0, a-1, 0, a-1 ... ] + [a-1, 0, a-1, 0, a-1, 0 ... ] = [a-1, a-1, a-1, a-1, a-1, a-1 ...]The sum of all the differences will be: S-n (where n is the number of elements in A)This means that on average, if we use this method we will get a sum of differences of (S-n)/2. To guarantee a correct answer we can use this method with even indices and odd indices, calculate our score, and choose the one which is lower.
 » 4 years ago, # |   +42 Hi Everyone !! Me and my friends tried to make the video editorials for this round, Please give a look and provide your valuable feedback : https://codeforces.com/blog/entry/85706
•  » » 4 years ago, # ^ |   +11 very nice video editorials !!Now I want you to answer a question which is probably the most asked question in history of codeforces.How to become an orange coder ? What exact path or strategy we can follow ?Although many coders have answered such questions but it is always beneficial to listen 1 more time.
•  » » » 4 years ago, # ^ |   +28 Practice
•  » » » » 4 years ago, # ^ |   +5 I may do a lot of practice but that practice won't yield much if I don't choose a correct strategy or a path .I am practicing a lot but i am improving less. What may be the problem? Can someone tell. Everyone is welcomed to showcase their views.
•  » » » » » 4 years ago, # ^ |   +6 You should start practicing problems of difficulty 1600-1800 and strengthen your graphs and DP.
•  » » » » » » 4 years ago, # ^ |   +4 Thank you
•  » » » » » 3 years ago, # ^ |   +11 Always practice the problems whose difficulties are a bit higher than your present level. Try to think it up by yourself and do not read the tutorial unless you are sure you can't make it.
•  » » 4 years ago, # ^ |   0 Suggestion: It would be good to find the find the links of the problem and solution in the you tube description area.
•  » » » 4 years ago, # ^ |   0 Yes, we will make sure that.
 » 4 years ago, # |   +10 There's another O(n) solution for D. This is my code.But I don't know how to explain this works... English is too hard
•  » » 4 years ago, # ^ |   0 tidy solution! Can someone explain this approach?
•  » » » 4 years ago, # ^ |   +8 To explain more clearly, we define that $a=\{x \; | 1 \le x \le 2n, \forall \; 1 \le i \le n, x \neq b_i \}$. In other words, $a=\{1,2,\cdots,2n\} \setminus b$. Then we need to solve the problem that we arrange $a$ in some order to make there are exactly $x$ pairs $(a_i,b_i)$ such that $b_i •  » » » » 4 years ago, # ^ | 0 Wow! Thanks for the nice explanation.  » 4 years ago, # | 0 Can anybody explain the solution of problem E? •  » » 4 years ago, # ^ | +9 Consider the prerequisite edges marked as 0 and special pairs as edges marked as 1.if a single vertex has more than one edges marked as 1 outgoing or incoming than it's not possible to find an ordering. Moreover, the graph should not contain any cycle.After checking this we can first group all the edges marked as 1 they will form a simple path, compress all the vertices to a single vertex and assign it as a parent of all vertices. Also keep the ordering of vertices for that component.Now add the edges marked as 0 in the new graph between parent of vertices, if both have different parent add the edge else we can ignore that cause we already checked for cycle. After this topsort the graph, if it is not possible than answer is zero else find the topsorted list will give a valid ordering. Print them by iterating through every vertex list that we found in the compression stage. my code » 4 years ago, # | -19 CODE A Solution is wrong. In Last line it will be " print("YES" if min(a, b, c) >= (a + b + c) // 7 else "NO") " # include<bits/stdc++.h> using namespace std; int main(){ long long int t,a,b,c; cin>>t; while(t--){ cin>>a>>b>>c; long long int sum=a+b+c; long long int d=sum/7; if(((sum%9)==0) & (a>=d) & (b>=d) & (c>=d)) cout<<"YES"<<endl; else cout<<"NO"<<endl; } return 0; } •  » » 4 years ago, # ^ | 0 d should be sum/9 and also you have to use '&&' instead of '&' •  » » » 4 years ago, # ^ | 0 sorry,my bad,'&' will also work  » 4 years ago, # | +6 Can someone please explain ecnerwala solved the F problem 101602047 using gcd? •  » » 4 years ago, # ^ | +91 It turns out that, given the lemma from the editorial (there exists an optimal string with period$x+y$), this problem can be solved in$O(x+y)$time.First, if$g = \gcd(x,y) \ne 1$, we can split the problem up by mod$g$, because all edges connect two things that are separated by$x$or$y$, which are multiples of$g$. Thus, we can assume$\gcd(x,y) = 1$.The key thing to observe is that all edges span$\pm x$modulo$x+y$. Because of the lemma, we can merge all nodes with the same residue mod$x+y$to get$x+y$super-nodes. Furthermore, because the edges are exactly the changes by$\pm x$mod$x+y$, and we assumed$\gcd(x,y) = 1$, these supernodes form exactly 1 complete cycle. Then, instead of doing the DP in$1 \ldots x+y$order, we can use the order of this cycle ($x, 2x, 3x, \ldots \pmod{x+y}$). This means our DP only needs to track whether we took the first element and whether we took the latest, so there are only$4(x+y)$states. •  » » » 4 years ago, # ^ | 0 what are edges here? •  » » » » 4 years ago, # ^ | ← Rev. 2 → 0 Consider the graph where two vertices$a,b$have an edge if$|a-b| \in \{x,y\}$, so that this problem is about finding maximum independent set.  » 4 years ago, # | 0 Am I the only person who didn't like problem C? •  » » 2 years ago, # ^ | 0 Disappointedly not a decent explanation. Where understanding is so tough, there solving is just a fun  » 4 years ago, # | 0 Can anybody help me in my submission of C submission. Thanks in advance. •  » » 4 years ago, # ^ | +1 Consider the following test case: Your first command on$t = 1$is to go to$x = 10^9-1$. It will arrive on$t = 10^9$. Then the second and last command is on$t = 10^9$(which the robot won't ignore as it's not moving anymore), to go to$x = -10^9$. You can see it will take$\left|(10^9-1)-(-10^9)\right| = 2\cdot10^9-1$units of time to get there. Therefore, it will arrive at$t = 3\cdot10^9-1$. Both commands are successful, while your code will only tell the first one is successful, as your variable mmm which you add at the end of the list of commands in what it seems to be a "dummy" element, is only equal to$10^9+5$, restricting your time range and therefore calculating incorrectly the range of positions where the robot would pass, and by so not counting the last command as successful. Increasing that value to$3\cdot10^9$should fix the issue, but of course by doing that you may have to be careful and work with long long variable types. •  » » » 4 years ago, # ^ | 0 Ouch.Thanks a lot man, feel so stupid should have set it to 1e10 or something. Also int is actually long long in my snippet and main function returns int32_t. Thanks again.  » 4 years ago, # | 0 Another approach to B for those who need: At first, if each b[i] is a power of 2 the first condition will be done. Let's prove the second condition will be done too. It means that b[i] >= ceil(a[i] / 2) for each i. If b[i] is equal to 2^k, where k = floor(log2(a[i])) the second condition will be done as well. Let's say x = a[i] = 5. It's 101 in binary representation. y = b[i] = 4. It's 100 in binary representation. Then, x / 2 = 5 / 2 = 101 >> 1 = 010 = 2. After the operation the highest bit in x / 2 will be equal to 0, but at the same time it's equal to 1 in y. Hence, y > x / 2. We have proved it.  » 4 years ago, # | 0 Can someone tell approach of problem D?  » 4 years ago, # | ← Rev. 3 → -12 does anyone else feels that Problem: C could have been more clearly explained ? •  » » 4 years ago, # ^ | ← Rev. 2 → +16 Can you tell me how do you understand it? I've reread the last paragraph of the legend a hundred times and still have no idea how can you interpret it other than the intended way...We were getting questions about it during the contest, I was answering "The robot should visit$x_i$at some moment between$t_i$and$t_{i+1}$" and the people seemed to be getting it and not returning with more questions, but I literally see no difference between the statement and that... •  » » » 4 years ago, # ^ | 0 Why do we not consider the first command as successful command? •  » » » » 4 years ago, # ^ | 0 Why do you think it always satisfies the condition for being successful? •  » » » » » 4 years ago, # ^ | 0 We start at t0 and reach our destination at t1 seconds. •  » » » » » » 4 years ago, # ^ | 0 You start at$t_1$and should reach it before$t_2$. •  » » » » » » » 4 years ago, # ^ | 0 So u are saying that when our robot starts at t1 sec it should reach x1 before t2 seconds.But in the problem statement we are have to reach our our destination( in this command x1) at t2 seconds.(As per my understanding correct me if I'm wrong), As both bounds are inclusive.You call the command i successful, if there is a time moment in the range [ti,ti+1] (i. e. after you give this command and before you give another one, both bounds inclusive; we consider tn+1=+∞) when the robot is at point xi. •  » » » » » » » » 4 years ago, # ^ | 0 Yes but you are moving 1 unit per second, have you noticed that? •  » » » » » » » 4 years ago, # ^ | ← Rev. 3 → 0 Can You Expain the answer with this test case. 63 105 58 012 -414 -719 -5 dist : [0,0,0,0,1,2,3,4,5,6,7, 8, 9, 10]time :[0,1,2,3,4,5,6,7,8,9,10,11,12,13] •  » » » » » » » » 4 years ago, # ^ | 0 Can you explain it? I still have no clue how can you understand that problem so that the answers are not complete nonsense but still wrong. •  » » » » » » » » » 4 years ago, # ^ | ← Rev. 4 → 0 at t = 3 sec we are at x = 0, t = 7 we reach x = 4, similarly we reach x = 10 at exacty t = 13 seconds, our time interval was [3,13], x1 was 10. t = 13 is the time before i give new command.[ti,ti+1] (i. e. after you give this command and before you give another one, both bounds inclusive; we consider tn+1=+∞)`Acoording to above statement. •  » » » » » » » » » 4 years ago, # ^ | ← Rev. 3 → +1 Ah, I see. You should not ignore$t_i$for the commands that are ignored.$t_{i+1}$is literally the time the$(i+1)$-th command gets sent (not necessarily executed). •  » » » » » » » » » 4 years ago, # ^ | ← Rev. 2 → 0 DELETED •  » » » » » » » » » 4 years ago, # ^ | ← Rev. 3 → 0 EDIT : understood the question in the wrong way  » 4 years ago, # | 0 I think there is a O(n) solution for problem E. I not sure about it. But it pass the test. •  » » 4 years ago, # ^ | 0 It's true. I think it's not necessary to find the order of the vertices inside each component by sorting, as you can just have for each lecture, the previous and next lecture in each of the components of special pairs, and reconstruct in linear time from each component after the topsort. Then you would just check if no lecture which should be a prerequisite is given after the one you're checking in the ordering, and thereby determine if no answer exists or that it does and you have to print the solution.At least with that I could also pass the tests with an almost$\mathcal{O}\left(n\right)$solution (just used a set for counting components, but can easily be replaced with something that also works in linear time... 101592299).  » 4 years ago, # | ← Rev. 2 → 0 We can also do it without using binary search and checking for each x. I found out if we construct an array C, whose entry is (indice of upper bound of b[i] in nb) — i. Then for each x the condition becomes that - The maximum of C from [0, x — 1] <= (n — x) and minimum of C from [x, n — 1] > -x . We count such valid x. Accepted Code  » 4 years ago, # | 0 Practice! Happy New Year!  » 4 years ago, # | ← Rev. 5 → 0 . •  » » 4 years ago, # ^ | ← Rev. 2 → 0 The statement clarifies: " i. e. after some enhanced shot, the health points of each of the monsters should become equal to$0$for the first time ".In your test case and the way you've shown of killing the monsters, you can see that the second monster gets killed (health points drops to$0\$) after the 7th movement while the others haven't yet. You can prove that there's no way of fulfilling this condition in that test case.
 » 14 months ago, # |   0 For problem E, if you're having trouble understanding why the algorithm always works, you can see that, if you firstly build the tree, and then draw the paths created by the special edges, none of these paths should cross each other, ie if some vertex in special path A is an ancestor of some vertex in special path B, then no vertice of B can be an ancestor of any vertex in special path A. (there are a couple more conditions about there being no special edges to an ancestor or to an indirect child)By special paths not crossing I mean something like this: