By Radewoosh, history, 3 years ago,

• +167

 » 3 years ago, # |   -22 Fastest Editorial release *_*
•  » » 3 years ago, # ^ |   +45 There is a feature now, that it cannot be earlier than the systests, so don't hope for much in the future :P
 » 3 years ago, # |   +8 wow! thank you its realy useful
 » 3 years ago, # |   +32 When there where 35 minutes left in the contest, I thought "F**k it, let's assume that F is convex and write this thing with crazy treaps". Unfortunately, my treaps skills weren't good enough for this to work. Did you assume that we should believe that it is convex?C and E are nice, thanks. D is weird and easy, didn't get your intentions.
•  » » 3 years ago, # ^ |   +7 Well, I think that we should always assume that people have to believe a bit, but ofc during the preparation it's good to have proofs.
•  » » 3 years ago, # ^ |   +64 A priority queue is enough to maintain the function. You can just maintain the turning points of the increasing and decreasing parts. Adding |x| will result in the movement of $O(1)$ turning point between two parts.61176125
•  » » 3 years ago, # ^ |   -29 ya you are right c is hard as compare to D .
 » 3 years ago, # |   +17 Good contest with Fast Tutorial :: Thanks Radewoosh
 » 3 years ago, # |   0 I spent a lot of time thinking how to solve Div2D in $O(n)$ instead of $O(n^2)$WTH is wrong with me!
•  » » 3 years ago, # ^ |   +134 We actually don't think this problem can be solved in $O(n^{2 - \varepsilon})$ time for any $\varepsilon > 0$ — we can prove that it's at least as hard as 2-Orthogonal Vectors problem (definition 6 in this paper). If we assume that the Strong Exponential Time Hypothesis is true, then 2-Orthogonal Vectors (and therefore Div2D as well) cannot be solved faster than $O(n^{2 - \varepsilon})$.
•  » » » 3 years ago, # ^ |   +76 Chill out, dude.Yeah, I thought the same thing during the contest. Sure.
 » 3 years ago, # |   -11 Editorial speed = INT_MAX CF Queqe speed = INT_MIN 
 » 3 years ago, # |   +7 Dear Radewoosh,I have a question about the intended solution for E. My E is accepted while I was expecting to get a TLE: 61172291I knew that the number of primes will not be beyond $\log(10^{12})$, and for each gcd operation, the number of primes will not increase. Therefore, I decided to implement a naive approach, by caching the node id and the current gcd of nodes from one of its ancestor. Honestly, I didn't expect to get it accepted (I just tried my chance).I see better solutions that ended up with less than 400 ms while mine is very close to the time limit.I am wondering if you purposefully intended to accept solutions like mine.
•  » » 3 years ago, # ^ |   +1 At every node, we are sending all the possible gcds from the ancestor as well as the current node. Now, this current node can take logn different values and if the height of the tree is n, wouldn't it become nlogn different values. Can you help me where I am going wrong?
 » 3 years ago, # | ← Rev. 2 →   +3 In "**Dawid and Bags of Candies**" problem, how did you come to the conclusion that "**one of them should take only the biggest bag or the biggest and the smallest bag**"?I have checked all the possibilities which are as follows (a,b,c,d are inputs)a + b = c + da + c = b + da + d = b + ca + b + c = da + b + d = cb + c + d = ac + d + a = b
•  » » 3 years ago, # ^ | ← Rev. 2 →   0 without loss of generality a>=b>=c>=d how about a = b+c+d and 1 guy takes a and other b,c,dU missed this case
 » 3 years ago, # | ← Rev. 3 →   0 For Div1A, what should be the output of following test : 4 5 5 2 6 3 6 10 1 Shouldn't it be optimal to take all the guys in the group since their skill sets are such that for everyone, for every jth skill there is a guy with same skill ? So No one will think he is better than everyone.Hence answer should be 20. But I am getting 9 while running this case on some ACed code. Or I guss, I still didn't get the question. Edit: Sorry, my bad. The question says that any person in the group should not be better than every other person in the group.
•  » » 3 years ago, # ^ |   0 I have not understood yet. why not 20?can you explain this case 10 3 3 5 5 6 6 1 2 4 7 1 1 1 1 1 1 1 1 1 1ans : 9
•  » » » 3 years ago, # ^ |   0 Hi, sorry i was wrong earlier. I edited the previous edit. see again. According to the problem, the person with ai == 7 will consider himself best so we can not include it in group. I hope you get it.
 » 3 years ago, # | ← Rev. 2 →   0 can somebody explain how to solve the 3rd problem Anadi and Domino (Div 2) for n=7 case
•  » » 3 years ago, # ^ |   0 For n=7 it's similar to n<=6 but we can have two nodes having same number as long as the number of dice and given condition ensured.So, iterate on pair of nodes for having same colour and find max among all cases
•  » » » 3 years ago, # ^ |   0 can you explain for this test case how answer is 14 not 13..7 15 4 6 7 3 3 1 6 5 2 7 3 6 7 6 2 6 7 5 3 5 5 4 4 7 2 1 2 4 2 3
•  » » » » 3 years ago, # ^ |   0 You will get 14. Just consider giving the domino with one dot to the 7th vertex. Also consider the case of giving (1,1) domino to edge 2-7 or 3-7.
 » 3 years ago, # |   0 Am i the only one who used brute force for C by check all 7^6 possible assignments of x for all vertices?
•  » » 3 years ago, # ^ | ← Rev. 2 →   0 I did that too, and it worksJust keep an array of all dominoes you have left, by their upper half number and their lower half number
•  » » » 3 years ago, # ^ |   0 I was thinking too, like this in contest about assigning each vertex a number by recursion for all possible color vertex-color combination, but after that I was confused by how to check it, may be I am missing, can you explain your approach if possible
•  » » » » 3 years ago, # ^ |   0 61159724 Check this out
•  » » » » » 3 years ago, # ^ |   0 I actually did that too, but this code is brutal haha. Follow my implementation : 61155872
 » 3 years ago, # | ← Rev. 2 →   -34 [DELETED]
 » 3 years ago, # |   -7 Fast editorial but no code:(
 » 3 years ago, # |   0 For problem Div1 A: Can someone describe how do we decide if two students can atudy calm? For the first test case, I couldn't get it. Thanks.
•  » » 3 years ago, # ^ | ← Rev. 2 →   0 Edit : A person in the group should not be better than every other person in the group.
•  » » » 3 years ago, # ^ |   0 Thank you.
•  » » » » 2 years ago, # ^ |   0 Would you explain sample test 2?I'm not able to understand why can't we send all people. Thanks in advance...
•  » » » » » 2 years ago, # ^ |   0 In the second test, in each group of at least two students someone will always think that he is better than everyone else in the subset
•  » » » » » » 2 years ago, # ^ | ← Rev. 2 →   0 001 010 011 So if we take group of all 3 people than nobody will think that he is better than everybody else. So why we can't send all 3 people?
•  » » » » » » » 2 years ago, # ^ |   0 Sorry, not sure
•  » » » » » » » » 2 years ago, # ^ |   0 It's okay:D If you get an answer then please tell me.
•  » » » » » » » 18 months ago, # ^ |   0 Maybe, 011 will think that he's better than 001 (skill #2) and better than 010 (skill #3).
•  » » » 3 years ago, # ^ |   0 how we decide which person is better?
•  » » » 2 years ago, # ^ |   0 Why can't we send all people in sample test 2? 001 010 011 So if we send all people no one will think that he is better than everyone else.
 » 3 years ago, # |   +5 Can anyone explain why the number of swaps is proportional to the change in potential for Div1 C? How about all the in-edges going from left to right initially that now point right to left? Also in the editorial did the author mean to write each vertex can have no more than root(2m) adjacent vertices to the right, not left?
•  » » 3 years ago, # ^ |   +20 I understood it as follows.Consider the change in potential after each query: (number of edges that start pointing left to right but were pointing from right to left before) (positive change) — (number of edges that start pointing right to left but were pointing from left to right before) (negative change).Consider the process of adding edges too at the beginning (while forming the graph, before performing any query) as adding 1 to potential if edge is left to right.Now, the positive change can only happen at most sqrt(2*m) times for each query and hence all the positive change would sum to m+q*sqrt(2*m) at best.The negative potential change sum can't exceed the positive change sum (as potential can't be negative), hence its max value is also m+q*sqrt(2*m).One operation of one query basically only increases or decreases the potential by 1. So, the total number of operations would be (positive change sum) + (negative change sum) which is 2*(m+q*sqrt(2*m)) at best.
•  » » » 3 years ago, # ^ |   +5 Oh so you're starting off with an initially empty graph, and treating the process of building the graph as part of the total cost? This is a nice way to guarantee that the initial potential is zero. Thanks for your explanation.
 » 3 years ago, # |   0 Kamil Making a Stream : YT Advertisement Alert!! Jk thanks for the problems :)
•  » » 3 years ago, # ^ |   +22 Or maybe it's a subliminal message to make his channel more popular than T-Series. Who knows :P
•  » » » 3 years ago, # ^ | ← Rev. 2 →   0 Maybe who knows :thinking: :p
 » 3 years ago, # |   +22 In Div1 C Editorial:"It now turns out that each vertex is adjacent with at most sqrt(2m) vertices to its left"How is this true? Simple counterexample is just a tree (degree 1, 1, ..., N — 1). The last vertex will be adjacent to N-1 vertices from the left.Or am I missunderstanding something?
•  » » 3 years ago, # ^ |   +27 Thanks for finding a typo!s/increasing order/decreasing order/We'll push a fix shortly.
•  » » » 3 years ago, # ^ | ← Rev. 2 →   +3 I am also not sure how the number of flips is proportional to the change of the potential.For a query about a node u, the edges joining u with the nodes on its left side should decrease the potential if it's being flipped, while the edges on the right should increase it.So, for example, if the number of edges being flipped on its left side is equal to those on its right side, the potential will not change after the query even though there could be lots of edges being flipped.
•  » » » » 3 years ago, # ^ | ← Rev. 2 →   +13 I was wondering the same thing as you (I left a comment above, unfortunately no response), but I think I might understand how Radewoosh's solution works. (This is my first time learning amortized analysis so please correct any error I might've made.)Consider the operation of swapping $u$'s incoming edges into outgoing edges. If $u$ has $A$ incoming edges from the left and $B$ incoming edges from the right, the change in potential is $\Delta \phi = B-A$. However, the total cost of removal is $C_{actual} = B+A$, so the amortized cost is $C_{amortized} = C_{actual} + \Delta \phi = (B-A)+(B+A) = 2B \leq 2\sqrt{2m}$, since $B \leq \sqrt{2m}$.It is not always true that $\phi(0) \leq \phi(q)$, but it is true that $\phi(0) \leq n \sqrt{2m} \leq \phi(q) + n \sqrt{2m}$.Edit: We can also bound $\phi(0) \leq m \leq \phi(q) + m$ which is much simpler.Therefore the sum of the amortized costs is $\sum_{i=1}^{q} C_{amortized, i}=\phi(q) - \phi(0) + \sum_{i=1}^{q} C_{actual, i} \geq \sum_{i=1}^{q} C_{actual, i} - n\sqrt{2m}$, where the first equality follows from a telescoping sum.Therefore the total cost is bounded by $\sum_{i=1}^{q} C_{actual, i} \leq n \sqrt{2m} + \sum_{i=1}^{q} C_{amortized, i} \leq n \sqrt{2m} + 2q\sqrt{2m}$
•  » » » » » 3 years ago, # ^ |   0 I don't understand whyC_amortized = C_actual + (Change of Potential)The sum of amortized time should be equal to the sum of the actual time, if my understanding about the amortized analysis is correct.
•  » » » » » » 3 years ago, # ^ |   0 The way I understand it is the amortized cost is just a function with certain properties. I could have replace $C_{amortized}$ with $f$ and the argument would not change.
•  » » » » » » » 3 years ago, # ^ |   0 Ok. I think I now understand the solution as well.Thanks a lot :D
•  » » » » » 3 years ago, # ^ |   0 even I didnt understand how you wrote C_amortized = C_actual + (Change of Potential) can you give some source from where you studied this?
•  » » » » » » 3 years ago, # ^ |   +10 I just read these notes https://www.cs.cmu.edu/afs/cs/academic/class/15451-s07/www/lecture_notes/lect0206.pdf
•  » » » 3 years ago, # ^ |   0 mnbvmarI think there are more typos based on this typo. In the next paragraph, I think "left to right" should be "right to left" and vice versa.
•  » » » » 3 years ago, # ^ |   +5 Thanks for the feedback, I'll try to rewrite this part of the editorial today.
 » 3 years ago, # |   0 Can anyone help me with my solution for div2D/div1A. I implemented the same idea as the editorial, but somehow get wa in test 7 https://codeforces.com/contest/1230/submission/61167796
 » 3 years ago, # |   +56 Thanks for the contest!I have accepted the following cute solution for E1 in upsolving (had to leave ~35 minutes before the end of the contest, so didn't debug in time then): let's just run the normal algorithm for maximum matching, and every time it needs to check if a given edge exists, we branch to try both options. The intuition is that in most branches, we won't care about the state of many edges, and this will run in time. Practically it took 5.3 seconds out of 7 in Java :) To implement this, our recursive search function needs to take the current state of the dfs stack as input: https://codeforces.com/contest/1229/submission/61184672
 » 3 years ago, # |   -7 For Div 2 D, why is the ans for this test case 9 and not 10? 10 3 3 5 5 6 6 1 2 4 7 1 1 1 1 1 1 1 1 1 1 aren't all the skills subset of skills present in 7?
•  » » 3 years ago, # ^ |   0 THe problem states that the the '7' can only be in the group, if he isn't better than each of them In that case the 7 is better than all the other numbers (you have to check one by one)
 » 3 years ago, # |   +1 In problem C why did I pass the pretests but finally RE on test 1? Now I submit the same code again but get "accepted".I feel puzzled.
 » 3 years ago, # |   0 I may be wrong but , doesn't the wording of A. Marcin and Training Camp give the impression that we need to take into account only the entire group and not the subsets ?I thought so and didn't bother checking the "Notes" section . Only too late into the contest did I realize from the explanation of pretest 2 that we have check whether the subsets / subgroups of at least 2 students can not have anyone that thinks he's better than everyone else . If you read only the question statement it implies that this constraint only applies to the group as a whole and they will be participating in the contest together . Doesn't it ? 1229A - Marcin and Training Camp
•  » » 3 years ago, # ^ |   0 You have to check the entire group. Pretest 2 is 1,2,3. If the team is 1,2,3 then 3 will think he is better than everyone if the team 1,2; both will think they are better than everyone(only one teammate in this case) if 1,3, 3 will think he is better than everyone
 » 3 years ago, # |   0 I'm unable to understand the editorial for Div. 2 — Problem C Anadi and Domino. Please help.
•  » » 3 years ago, # ^ |   0 mee too :(
 » 3 years ago, # |   0 Can anyone explain div2 C please.
 » 3 years ago, # |   +6 Help in Div2. D. ( I´m getting TLE )My idea:Build a directed graph with students as nodes. There will be a edge from node $A$ to node $B$ if and only if the student $A$ doesn´t think that he is better than student $B$.With this in mind, the solution to the problem is the sum of the skill levels from all those nodes such that there is a path from that node to a cycle.I implemented this and i think that the complexity is $O( V+E ) \approx 2.5 \cdot 10^7$ worst case ( when it is a completed graph ).I tried taking all the students that know exactly the same algorithms as one node but it did´nt work. codeDid i make a mistake in the complexity or i miss something in my code?Thanks in advanced.
•  » » 3 years ago, # ^ |   +4 I solved it with the same idea. I add an edge from $i$ to $j$ iff $j$ has all the skills that $i$ has. As you mentioned we can see that we can add all the nodes to the answer that have a path to a cycle (or are part of a cycle). I run $dfs$ on every node but keep a $dp$ which prevents to run $dfs$ if you already know whether this node leads to a cycle or not. — 61210128.
•  » » » 3 years ago, # ^ |   +5 I did the same $dp$ but on a bool array, maybe i made a mistake. I will try it again, thank you for your response.
•  » » » » 3 years ago, # ^ |   +3 Now that I saw your solution again, I noticed when you are building the graph you are doing it in $O(60n^2)$ which is almost $2\cdot10^9$ in the worst case and that is not surprising that you are getting TLE on a test case with $7000$ nodes. The problem with your implementation is probably validEdge. You need to do it faster.
•  » » » » » 3 years ago, # ^ |   0 Yes, you were right! I did it in the same way as you and now i got AC. But i always thought that bit operations ( ans & , or | , xor ^ ) had the same complexity to do a loop over the bits. So now i´m a little bit confused, how is that doing this is really much faster?AC.
•  » » » » » » 3 years ago, # ^ | ← Rev. 2 →   0 Modern computers are capable of doing bitwise operations in almost 1 clock cycle which is really really fast compared to looping over bits! You can always assume that bitwise operations are done in $O(1)$ time. That's because of the computer's architecture.
•  » » » » » 3 years ago, # ^ |   0 Hi! I also used same approach(and doing same style of implementation) and was getting TLE, then I did what you said and I was able to reduce execution time by significant amount for first 15 cases. But I m still getting TLE on 16th case.I use Java hence, may be it does it in a bit slower way so if you mind having a quick look at my submission. I m sure that it is while building graph as I tried some debugging. Here is submission: 61288151
•  » » » » » » 3 years ago, # ^ |   0 Hi! I think that you are building the graph fast enough. Try to debug you $dfs$. You are probably running $dfs$ multiple times.
•  » » 20 months ago, # ^ |   0 I also solved this building a directed graph. But instead of finding cycles I stored out degree of nodes and the reverse graph. Then for each node with out degree 0, decreased out degree of every other node that it came from(From the reversed graph). And finally took the values with at least one out degree remaining. Code
 » 3 years ago, # |   0 my code is wrong in test 10 of problem C i hope anyone help me explain test 10 my result is 13 while correct answer is 14
 » 3 years ago, # |   +13 If you didn't fully understand $Div1$ $C$, you can think about it like this:Assume the list in which employees are sorted in decreasing order of their degrees is $S$. Now, when Employee $v$'s salary is revised, we process all incident edges at $v$ to reverse them. So, what is the upper bound of all reversals count?When we reverse an incident edge at $v$, we have $2$ cases: The edge isn't reversed before. So, the upper bound for this case is $O(m)$ across all queries. The edge is reversed before. Since the upper bound for new edges going from right to left in $S$ after processing any employee is $\sqrt{2m}$, therefore the upper bound of the incident edges at $v$ which are reversed before and are coming from right to left across all queries is $Q*\sqrt{2m}$. And the upper bound of those coming from left to right (whether reversed before or not) is $\sqrt{2m}$ per query.
 » 3 years ago, # |   +5 could you give me more elaborated explanation on problem C (div 2) in case $n = 7$. I still don't understand it.
 » 3 years ago, # |   0 In problem Div2C Since, I can't understand editorial, can anybody explain in easier way?
•  » » 3 years ago, # ^ |   0
•  » » 3 years ago, # ^ | ← Rev. 3 →   +3 Note that $n \leq 7$ by problem constraints.For $n \leq 6$, the answer is just $m$, since we can always place dominoes such that the ones point to node 1, the twos point to node 2, etc, and we end up using the dominoes with the same pip numbers as the edge numbers given in the input. Since there are no duplicate edges, every edge can have a domino placed on it.For $n = 7$, things get slightly trickier, as two vertices must have the same domino number pointing to it. We can brute-force every pair of vertices as a candidate for same-domino-number assignment. For each such pair $u$ and $v$, the number of "colliding" edges is equal to $|S_u \cap S_v|$, where $S_u$ is the set of vertices connected to vertex $u$ (or in other words, the number of vertices connected to both candidate vertices). Find the pair with the minimum collisions, and subtract the collisions from $m$ for the final answer.Sample code (in Kotlin) 61213061
 » 3 years ago, # |   0 Why wrong answer verdict for my code for "Ania and Minimising" was showing during the contest and was failing on test case no 5 But giving the right answer when I checked it later with these inputs on other online compiler.
•  » » 3 years ago, # ^ |   +1 Codeforces runs on 32-bit systems, hence long int is only 32 bits long here.
 » 3 years ago, # |   +45 While working on problem E2 (matching, hard version), I found this: A227414, which is the number of nxn bipartite graphs with a perfect matching for $n \le 7$.I actually think our model solution can be used to extend this entry by $n=8$ (or maybe even $n=9$, but this may take hours or even a couple of days). The idea is to solve the problem for all probabilities = $\frac12$, and then multiply the result by $2^{n^2}$.I think that the result for $n=8$ is Result17190232260306391039Can someone confirm it?
•  » » 3 years ago, # ^ |   +30 Just put those values in Berlekamp–Massey, easy xd
•  » » 3 years ago, # ^ |   0 +1
 » 3 years ago, # |   +1 can anyone plz explain the solution for div 1 B. I am not getting the editorial.
•  » » 3 years ago, # ^ | ← Rev. 11 →   0 Let $S_u$ be the multiset of all values $f(t, u)$ where $t$ is an ancestor of $u$. Then if $v$ is a direct child of $u$, $S_v = \{x_v\} + \mbox{map}(S_u, \{ i \mapsto \gcd(i, x_v) \})$. ($\mbox{map}$ refers to the higher-order function that makes a new collection with each element in the old collection transformed by the given function)How is this derived? The $\{x_v\}$ part comes from the new element $f(v, v) = x_v$, while the $\mbox{map}$ part comes from the fact that $f(t, v) = \gcd(f(t, u), x_v)$The number of distinct values in $S_v$ for any vertex cannot be more than $\log_2 \max(x)$, as noted in the editorial.This transition can thus be efficiently implemented by computing $S_u$ as a hashmap, then passing that map to the children for use in computing their own $S$ multisets.Example code (in Kotlin): 61249254
 » 3 years ago, # |   0 can someone please explain the common solution for problem C? most people(like this submission) are using 3 loops and checking the adjacency matrix but I can't understand what are they doing. can anyone help?
 » 3 years ago, # |   0 Can somebody tell more about the solution of div1B / div2E / (Kamil and Making a Stream) that using jump-pointer(binary lifting, i guess) ?. It would be nice
•  » » 3 years ago, # ^ |   +3 Hi, i did that approach.The main idea is that for a fixed node $u_0$ you can decompose the path from $u_0$ to $1$ in differents paths like this ( let $f[v]$ be the parent of node $v$ ) :From $u_0$ to $u_1$ , from $f[u_1]$ to $u_2$ , ... , from $f[ u_{k-1} ]$ to $u_k = 1$, such that $u_1$ is an ancestor of $u_0$. Such that the $gcd$ from node $u_0$ to a node $v$ its equal to the $gcd$ from node $u_0$ to a node $w$ if and only if $u$ and $w$ are in the same semi-path.In other words, the nodes of a same semi-path has the same $gcd$ to node $u_0$ and nodes from different semi-paths has different $gcd$ to node $u_0$.And to do this, you can use binary lifting to find first node of every semi-path.I don´t know if i explained it well, but here is my code 61246386, ask me every thing you want. :D
•  » » » 3 years ago, # ^ |   0 now understood, thank you!
 » 3 years ago, # |   0 Can someone explain why I can pass Div2D/Div1A by using n^3 method? 61205254
 » 3 years ago, # |   0 unable to understand Div 2 D why secind test case answer is not 6 ?explain pls thanks
•  » » 3 years ago, # ^ |   0 Binary representation of $1$, $2$ and $3$ are $01$, $10$ and $11$ respectively. If you put all these people in a group then $11$ will think he is better than $10$ because he knows an algorithm that the $10$ doesn't know. And again $11$ will think he is better than $01$ because he knows an algorithm that $01$ doesn't know. So he will think he is better than everybody else. That's why you can't group $1$, $2$, and $3$. Both $10$ and $01$ will think that they are better than the other one. So you can't find a group at all.
•  » » » 3 years ago, # ^ |   0 ohh thanx i misunderstood d pronpm evn after reading 3 times
 » 3 years ago, # |   0 Can't understand Div 2 E can anybody explain this problem's editorial in easier way?
•  » » 3 years ago, # ^ |   +3 In this problem you need to find the cummulative gcd of vertices from the current vertex to it's ancestor and then sum it all up. The way it's to be done is using the fact that there won't be more than logn different blocks with same gcd for a given vertex.Take an example [2 3 6 6]. Suppose u are at vertex 6, there are 3 blocks here 6,6 with gcd 6, 3 6 6 with gcd 3 and 2 3 6 6 with gcd 1. Basically each time you go left you will either get the same gcd or a gcd that divides your current gcd. And as the smallest divisor in this case can be 2. It proves that there will be atmost log(n) different blocks with same gcd. Now seeing this the rest in implementation and easy to do. just go through each node and then store all the gcd along with their counts in a map. Now what you can do is use the gcd of parent vertex and then find gcd wit the current vertex and add to answer cnt*gcd(prev_accumulatedgcd,va[current]. After doing this for all prev_accumulated gcds update the map with all the gcd's you just found and then do dfs. This way you will get your sum. So overall complexity is O(n -> for dfs * logn -> for inserting values into map * logn -> for counting of values with logn blocks of previous gcd).
•  » » » 3 years ago, # ^ |   0 Thanks , but if i start from the root , then the map will store values of gcd from the root to all the vertecies untill the vertex u , but i will need gcd's from vertex u to all of it's ancestors , do you mean i starting dfs from leaves ?
•  » » » » 3 years ago, # ^ |   +3 No, i mean starting dfs from root and storing values upwards. Initially the gcd,cnt pair will be empty when u call first dfs the value of root will be added with cnt 1 and then u will pass this to the next dfs call to the children and rest procedure i have already explained above. I will do dfs from top to bottom and calculate gcd of children using the gcd's i calculated above
•  » » » » » 3 years ago, # ^ |   0 I have understood you and got Acc , thank you for your help
•  » » » » » » 3 years ago, # ^ |   +3 np
•  » » » » » » 3 years ago, # ^ |   0 Hi, I have implemented same idea. But I think I am missing a small thing. Code is very straightforward. can you help me out ? https://codeforces.com/contest/1230/submission/61536704
 » 3 years ago, # |   +10 How to prove the lemma in problem F?
•  » » 3 years ago, # ^ | ← Rev. 2 →   +20 (1) The answer won't change if xi could be any arbitrary real values.You can model the problem as minimum-cost flow: take $n$ vertices $v_1, \dots, v_n$ corresponding to the scales, and add a source $s$ and a sink $t$. The units of flow will correspond to the paths taken by each coin. Let $M > \max(n, \sum_{j=1}^n a_j)$. The edges go as follows: $s \to v_i$, with flow $a_i$ and cost $0$ (we put $a_i$ coins on the $i$-th scale), $v_i \leftrightarrow v_{i+1}$, with flow $M$ and cost $1$ (we can move the coins along the circle), $v_i \to t$, with minimum flow $l_i$ and maximum flow $r_i$ and cost $0$ (the number of coins after all shifts has to be in some interval). We can implement this e.g. by adding two edges: one with flow $l_i$ and cost $-M$, and the other with flow $r_i - l_i$ and cost $0$. We can see that the minimum cost of the maximum flow in this network is equal to the minimum time needed to solve the riddle, minus $M \cdot \sum_{j=1}^n a_j$. Now, it's a well-known fact that in the flow instances with integer capacities, there exists an optimal flow using only integer flows (even if we allow any real flows). This solves part (1).(2) The arithmetic mean of two feasible solutions is a feasible solution.If $(p_1, p_2, \dots, p_n)$ and $(q_1, q_2, \dots, q_n)$ are feasible solutions, consider a solution $(r_i)$ where $r_i = \frac{p_i + q_i}{2}$. We only need to prove that $a_i - r_i + r_{i-1} \in [l_i, r_i]$. However, the left-hand side is the arithmetic mean of $a_i - p_i + p_{i-1}$ and $a_i - q_i + q_{i-1}$. Both these expressions were in $[l_i, r_i]$ interval, therefore $a_i - r_i + r_{i-1}$ is good as well. This solves part (2).Let's now prove that $F(p) + F(q) \geq F\left(\frac{p+q}{2}\right)$ for any real $p$, $q$. Take $(p_1, \dots, p_n)$ as the optimal solution for which $p_1=p$, and $(q_1, \dots, q_n)$ as the optimal solution for which $q_1=q$. Now, notice that $x \to |x|$ is a convex function. Therefore, $|r_i| = \left|\frac{p_i + q_i}{2}\right| \leq \frac{|p_i|}{2} + \frac{|q_i|}{2}$ for each $i$. As $(r_1, \dots, r_n)$ is some solution (not necessarily optimal) for which $r_1 = \frac{p+q}{2}$, we have that $F\left(\frac{p+q}{2}\right) \leq \sum |r_i| \leq \frac12 \left(\sum |p_i| + \sum |q_i|\right) = \frac12 (F(p) + F(q))$.Therefore, $F$ is convex and has an optimum at some integer point. Hence integer ternary search works.
 » 3 years ago, # |   +1 In Div1 A, what is meant by "a smaller set of skills"? Are you talking about the number algorithms the student knows? If so, the solution doesn't make any sense because a potential student having a smaller set of skills than another student doesn't guarantee that the condition will be satisfied after he is added.
 » 3 years ago, # | ← Rev. 2 →   0 Radewoosh, I'm having trouble understanding why your Div1D solution has complexity $O(nk!k)$. It is clear that you calculate the (at most) $k$ distinct groups that end in $r$, and obviously do this for every $r$ from $1$ to $n$.However, you assume that every time you insert a new permutation into a specific group, the DFS/BFS algorithm you apply to obtain the new bigger group has time complexity of $O(k!)$, but isn't it $O((k!)^2)$ at worst?Correct me if/where I'm wrong:By definition BFS/DFS has complexity of $O(n + m)$, where $n$ is the number of nodes, and $m$ is the number of edges. It is obvious that $n = k!$ in this case. But $m$ can go up to $n^2$. When you insert a permutation to a group you have to compose it to every other one in the group. This produces several other new permutations for the group, so each of them should similarly be composed to all the existing permutations in the group. This process is repeated on and on, until no new permutations are produced. Therefore, the $xth$ permutation added was composed with $x - 1$ other permutations. So in order to obtain a group of cardinality $n$, the complexity is $O(n^2)$.I'm a rookie in group theory, so I don't know if there's some property on groups/composition that brings up a heuristic that reduces the number of operations on the proposed solution. I'd like to know if this is the case, or the actual complexity is $O(n(k!)^2k)$, and it passes in time thanks to microoptimizations/a good constant factor.Thanks for the contest btw, it was challenging and interesting.
•  » » 3 years ago, # ^ |   +10 We create a set of $O(k)$ generators: $g_1, g_2, \dots, g_\ell$. Each element of the subgroup is then a product of these generators in some order, possibly with some generators occurring multiple times (or not at all). You can therefore have at most $|V| \cdot k$ edges in your graph: you only need to multiply by $g_1, g_2, \dots, g_\ell$ in each BFS/DFS iteration.Therefore, each BFS/DFS will take at most $k!k$ time. This would suggest that the total runtime of processing each prefix is $k!k^2$. It's not true, though — each new subgroup in the subgroup chain is at least twice as large than the previous one. Therefore, the running time is something like $\sum_{i=0}^k 2^{-i} k!k = O(k!k)$.
•  » » » 3 years ago, # ^ |   0 Got it. I thought you needed to keep $O(k!)$ generators, but you're right, $O(k)$ is enough. Then you perform a BFS/DFS on all the $O(k!)$ permutations, but only considering those $O(k)$ generators as transitions per each node.However, this means I coded a $O(n(k!)^2k)$ solution and got AC instead of TLE: 61572593. Weak testing?Either way, thanks a lot for the quick response.
•  » » » » 3 years ago, # ^ | ← Rev. 4 →   +8 Is it $O(n(k!)^2k)$ or $O(n(k!)^2)$? If you compute a subgroup in $O(\mathrm{size}^2)$ time, then computing all the subgroups in the chain is $O((k!)^2)$ (same geometric progression thing).Actually, it was really hard to make $O(n(k!)^2)$ much slower than $O(nk!k)$, so we were okay with someone squeezing the former in TL. Setting $k=6$ was not really an option, as $n$ would have to be significantly lower and we had some quick $O(n^2 + f(k))$ solutions (for some function $f$) that would pass without any problems.
 » 3 years ago, # |   0 In Div2D/Div1A, what is meant by "strictly smaller set of skills"? Do you literally just compare the bitmasks like numbers? Also, shouldn't there be a proof for this, as part of the editorial?
•  » » 3 years ago, # ^ |   0 "strictly smaller set of skills" means the algorithms that the person to be included in the group should be a "proper subset" of algorithms that a person already present in the group knows ( there should be at least one such person present in the group).
 » 3 years ago, # |   0 Why am i getting WA in test 11 of 1230B ? I tested my code quite a lot of times and also tried big values of N and still got the correct results. Can anyone please help ?
•  » » 3 years ago, # ^ |   0 nvm, i got ac now :D. I forgot to add a case
 » 3 years ago, # |   0 Regarding Marcin and Training Camp . It is written that if any student has a set of skill strictly less than the skills of everyone in any group then he can be safely included.Consider this example in which the group consists of skills 4(100) and 4(100) ,now including 1(001) will make him think himself better than others because no one else in the group has first bit set. Am i missing something ??
•  » » 2 years ago, # ^ |   0 did u get this, iam struggling with this...plz help.
 » 3 years ago, # |   0 I know its pretty late, but in Div1C/Div2F , can someone explain the sqrt(2m) bound a little more elaborately ? I am not understanding the bound, where it is coming from.
 » 3 years ago, # |   0 Can anyone explain the Div 2C ? Didn't get the result for n = 7.
 » 20 months ago, # |   0 abe chutiyo jiska contest hai usske tutorials laago na
 » 17 months ago, # |   0 I am unable to understand question A. Marcin and Training Camp. Can someone please explain especially test case 2?1-> "01" 2-> "10" 3-> "11" if we take all 3 as a group then no one in the group thinks that he is better than everyone else right? . Why ans=0?