### awoo's blog

By awoo, history, 19 months 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)  Comments (92)
 » great tutorial and congratulations on completing century of educational rounds... wow
•  » » 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.
•  » » » 2∑i=1n|ai−bi|≤S How is this condition satisfied in the solution you mentioned?
•  » » » » 18 months ago, # ^ | ← Rev. 3 →   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
•  » » » » » thanks a lot for the detailed and clear explanation! i really appreciate it. :)
•  » » » » » This solution is a lot more intuitive than the one described in the editorial...
•  » » » » » » thanks
•  » » » » » Great Solution !! Thanks
•  » » » » » » Welcome
•  » » » » » Its is beautiful, •  » » » Awesome solution, and explanation to match. Thank you!
•  » » » » Thanks
 » another approach for B is 2^k
•  » » 19 months ago, # ^ | ← Rev. 4 →   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
•  » » » 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.
 » I'd love to see a clean implementation of problem 2C in C++, if possible. Can someone point me in the right direction here?
•  » » Maybe you can have a look at my code. It is easy to understand I think.
•  » » » I finally understood the implementation, appreciate it!
•  » » » 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.)
•  » » » I still can't understand the code, please explain the last condition if possible
•  » » » » 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}]$.
•  » » » » » Thanks a lot!! Can understand in a much better way now
 » Can anybody say other approaches of problem B?
•  » » 19 months ago, # ^ | ← Rev. 2 →   Yes. For example, we can print 2^k, where k = floor(log2(Ai)) for each i.
•  » » My submission: https://codeforces.com/contest/1463/submission/101614243
•  » » 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.
•  » » » 19 months ago, # ^ | ← Rev. 2 →   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<
•  » » » » Thankyou both the editorial and the solution in the comments section are useful. Working with bits are so fascinating!!
•  » » » » Good job! Thank you a lot!
•  » » 19 months ago, # ^ | ← Rev. 2 →   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.
 » 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
•  » » 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.
•  » » » Practice
•  » » » » 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.
•  » » » » » You should start practicing problems of difficulty 1600-1800 and strengthen your graphs and DP.
•  » » » » » » Thank you
•  » » » » » 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.
•  » » » » » » Thank you so much.
•  » » Suggestion: It would be good to find the find the links of the problem and solution in the you tube description area.
•  » » » Yes, we will make sure that.
 » 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
•  » » tidy solution! Can someone explain this approach?
•  » » » 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 •  » » » » Wow! Thanks for the nice explanation.  » Can anybody explain the solution of problem E? •  » » 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 » 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; } •  » » d should be sum/9 and also you have to use '&&' instead of '&' •  » » » sorry,my bad,'&' will also work  » Can someone please explain ecnerwala solved the F problem 101602047 using gcd? •  » » 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. •  » » » what are edges here? •  » » » » 19 months ago, # ^ | ← Rev. 2 → 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. •  » » » » » 18 months ago, # ^ | ← Rev. 2 → Thanks for good problems  » Am I the only person who didn't like problem C? •  » » Disappointedly not a decent explanation. Where understanding is so tough, there solving is just a fun  » can somebody explain what is the meaning of the below line's from problem c, thanks?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. Count the number of successful commands. Note that it is possible that an ignored command is successful. •  » » At time t0, robot receives a command from point a to point b. Robot receives another command at time t1 when the robot is at point c, if c is between a and b, you call the command of t0 is successful. Here is my code.101684995 •  » » » if i am not wrong you are trying to say that command is successful if robot receive command at t[i] which robot ignores when moving to x[i-1], if that's the case then why in the first test case why the last command is successful. •  » » » » Sorry i got wrong with a,b and c.But, the key point is t[i] is successful only if robot passes through p[i] betweeen time t[i-1] and t[i].Last commad is sucessful because of the problem statement t[n+1]=inf. So t3=6 and t4=inf.Between t3 and t4, robot did pass through 4. •  » » » » » I think I got it, but I have a little doubt, for the ignored command to be successful we had to measure the distance from the point(max) where our previous command had been successful (i.e: from the next point it had been unsuccessful)? •  » » » » » » if you change the second command of the first case which is 3 0 to 3 4.Then,at time t2=3,robot(at point 2) is moving,so this command is ignored.However,at time t3 = 6,during t2=3 and t3=6, the robot is moving from 2 to 5,and passes through 4.As a result, the second command is ignored but still successful •  » » » » » » » got it, thanks man.  » Can anybody help me in my submission of C submission. Thanks in advance. •  » » 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. •  » » » 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.  » 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.  » Can someone tell approach of problem D?  » 19 months ago, # | ← Rev. 3 → does anyone else feels that Problem: C could have been more clearly explained ? •  » » 19 months ago, # ^ | ← Rev. 2 → 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... •  » » » Why do we not consider the first command as successful command? •  » » » » Why do you think it always satisfies the condition for being successful? •  » » » » » We start at t0 and reach our destination at t1 seconds. •  » » » » » » You start at$t_1$and should reach it before$t_2$. •  » » » » » » » 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. •  » » » » » » » » Yes but you are moving 1 unit per second, have you noticed that? •  » » » » » » » 19 months ago, # ^ | ← Rev. 3 → 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] •  » » » » » » » » 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. •  » » » » » » » » » 19 months ago, # ^ | ← Rev. 4 → 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. •  » » » » » » » » » 19 months ago, # ^ | ← Rev. 3 → 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). •  » » » » » » » » » 19 months ago, # ^ | ← Rev. 2 → DELETED •  » » » » » » » » » 19 months ago, # ^ | ← Rev. 3 → EDIT : understood the question in the wrong way  » I think there is a O(n) solution for problem E. I not sure about it. But it pass the test. •  » » 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).  » 19 months ago, # | ← Rev. 2 → 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  » Practice! Happy New Year!  » 19 months ago, # | ← Rev. 4 → In problem A: for the case :8 1 8 why can't we go through like this? (1)7 1 8 (2)6 1 8 (3)5 1 8 (4)5 1 7 (5)5 1 6 (6)5 1 5 (7)4 0 4 (8)3 0 4 (9)2 0 4 (10)1 0 4 (11)1 0 3 (12)1 0 2 (13) 1 0 1 (14)0 0 0 the code says NO,but what's wrong here? •  » » 19 months ago, # ^ | ← Rev. 2 → 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.
 » In problem div2B, can't we write all n elements as 1? What's wrong with this approach?
•  » » 19 months ago, # ^ | ← Rev. 2 →   That approach won't work because the third condition for the array to beautiful won't be satisfied. You can easily find such test cases.
 » Pls have a look at my solution to Div 2 C. It is failing on testcase 2. I dont seem to find the answer.https://codeforces.com/contest/1463/submission/101779953
 » very good man this fucking problem is very hard thank u so much