Rating changes for the last round are temporarily rolled back. They will be returned soon. ×

### Glebodin's blog

By Glebodin, history, 3 years ago, translation,

Hi everybody!

On August 29, в 18:05 MSK Codeforces Round #430 (Div. 2) will be held. As usual, Div.1 participants can join out of competition.

The problems are prepared by me glebodin and Ilya Ilua Maximov. Many thanks to Alexey Perforator Ripinen for help in preparations of the round. Great thanks to Alexey Livace Ilyukhov, Ildar gainullin.ildar Gainullin, Daniil qoo2p5 Nikolenko for testing the round, Nikolay KAN Kalinin for helping us preparing the round, Maxim HellKitsune Finutin and Ivan BledDest Androsov for testing this round and Mike MikeMirzayanov Mirzayanov for the Codeforces and Polygon systems.

The scoring is : 500 — 1000 — 1500 — 2000 — 2500

Congratulations to the winners:

Div. 1:

uwi

gritukan

natsugiri

kmjp

victoragnez

Div. 2:

fatego

sufficiently_large_boss

qscqesze6

white_flag

cwy1212

Editorial : http://codeforces.com/blog/entry/54179

• +312

 » 3 years ago, # |   +9 Auto comment: topic has been updated by glebodin (previous revision, new revision, compare).
 » 3 years ago, # | ← Rev. 2 →   +29 Wow, very short announcement and very fast publish of scoring!
•  » » 3 years ago, # ^ |   +11 yeah, why are they always publishing the scoring distribution in the last 10 minutes.
•  » » » 3 years ago, # ^ | ← Rev. 3 →   +9 I think, because testers say something like "it's a bit harder, then i think" and they must wait for their decision.
•  » » 3 years ago, # ^ |   0 I hope the problems will short too :)
 » 3 years ago, # |   +75 Obligatory comment about hoping the problem statements to be as short as announcement..
•  » » 3 years ago, # ^ |   +14 +Fast system test
•  » » » 3 years ago, # ^ |   +2 By the way. Who can explain why there is a big lag between contest finish and system testing start?
 » 3 years ago, # |   +2 it is the shortest announcement I have ever seen .
 » 3 years ago, # |   +151 Is this the best month or what!
•  » » 3 years ago, # ^ | ← Rev. 2 →   +33 It is nice because of many contests, but some of the contests from this summer weren't really nice. Back in autumn or winter the contests were nicer. Hopefully this will change soon because i see that people stop participating on CF. Some months ago 8000 people were registering and 5000+ were participating, but now around 3500 participate, but i love CF, it is the website were i have the most emotions while participating.
 » 3 years ago, # |   +135 I'll leave this picture as a reminder for the russian problem setters =)
•  » » 3 years ago, # ^ |   +68 sorry for my bad english
•  » » » 3 years ago, # ^ |   +1 It's completely ok that your english is not ideal. It would be nice if there was someone to review the statements before the competition starts. Non-russian problem setters aren't (as far as I know) expected to know russian well enough to write the problem statements without help. Russian problem settlers shouldn't be expected to do the same either.
•  » » 3 years ago, # ^ | ← Rev. 2 →   +17 Maybe on the russian site they say the same about russian statements when there is a non-russian setter.
•  » » » 3 years ago, # ^ |   -17 You are god damn right.
•  » » » 3 years ago, # ^ |   +1 Not at all. The Russian translations are pretty much always spot on because they get native Russian speakers to do them.
•  » » » » 3 years ago, # ^ |   0 But then again, native speakers can skrew up translations into Russian if the original statements were written in English.
•  » » 3 years ago, # ^ |   +28 i love codeforces and want to see it improve day by day, and that's why i think they really need a professional English editor because i keep seeing these kinds of grammar mistakes in many problems
•  » » » 3 years ago, # ^ |   +25 In the past, Delinur has either translated or reviewed the translations of statements in nearly every contest. Does this position not exist any more?
•  » » » 3 years ago, # ^ | ← Rev. 3 →   0 Perhaps learning to capitalize your I's would be a good start.
•  » » » » 3 years ago, # ^ |   -23 just too lazy to press shift bro, LOL
•  » » » » 3 years ago, # ^ |   +1 that's punctuation not grammar
•  » » » » » 3 years ago, # ^ |   0 Orthography, you mean, which is part of grammar in the greater sense of the word.
•  » » » 3 years ago, # ^ |   +1 Nobody needs a "professional editor" for problem statements, a native English speaker with some CF experience will suffice.
•  » » 3 years ago, # ^ |   +15 yes. i was going to say the same thing. and don't forget their explanation to the sample test cases were awful too. And when i asked for an explanation (this exact same problem) they told me to read the problem statement carefully. Man, because of your awful statements, i asked you for an explanation. -_- I think they should consider that CF has become a global coding contest site and so they should give more importance in their English statements. :)
 » 3 years ago, # |   +5 It's nice and short. But can someone tell me why can't I see the test cases in usual practice submissions? This has been troubled me for almost a week!
 » 3 years ago, # |   -6 Before anything else,
•  » » 3 years ago, # ^ |   +61 Why must you use memes incorrectly?
 » 3 years ago, # |   -30 You didn't say if it is rated. Is it rated?
•  » » 3 years ago, # ^ |   -24 finally correct is it rated? question. Yes it is.
 » 3 years ago, # |   -86 is it rated?
 » 3 years ago, # |   -93 I am a boy. I am a thirteen. I get up at nine o'clock. I have for breakfast a burger. I play a game with friends. I have for lunch a burger, a cola. I help for construction. I eat a pizza. I drink a cola. I sleep at twenty o'clock.
•  » » 3 years ago, # ^ |   +2 Why did you write this
•  » » 3 years ago, # ^ |   +5 Bravo :|
•  » » 3 years ago, # ^ |   +26 Are you on drugs?
•  » » 3 years ago, # ^ |   +79 Did you forget to log out your Codeforces account on your friend's laptop?
•  » » » 3 years ago, # ^ |   +43 He's 13, He gets up at 9 and sleep at 20, he surly doesn't have friends
•  » » » 3 years ago, # ^ |   +34 Is this your own experience ?
•  » » » » 3 years ago, # ^ |   +36 Right in the feelings
•  » » 3 years ago, # ^ |   -13 baba Khafan amsal shoma hamishe naghsheshoon kam rang bood
 » 3 years ago, # |   +2 wow ............ Total: 7983 Contestants: 7600 Out of competition: 383
 » 3 years ago, # | ← Rev. 2 →   -15 RTE in problem A (python 3), no idea why >_
 » 3 years ago, # |   -6 problem: C. Ilya And The Tree what it the biggest common divisor if one of the numbers are 0?
•  » » 3 years ago, # ^ |   -8 +1
•  » » 3 years ago, # ^ |   0 If one of the numbers is 0, the GCD of both of them is the other number. You shouldn't be asking questions here while the constest was running =P Try to send a clarification next time (by the way, there was an announcement about this hahaha)
 » 3 years ago, # | ← Rev. 2 →   0 Where is the perfect place to ask questions related to testcases?? I am trying to hack some solutions but it's giving invalid input but a/c to question it should be valid. I can't ask here Because this is public and contest is still going on so..
•  » » 3 years ago, # ^ |   +3 write me (if you want)
 » 3 years ago, # | ← Rev. 4 →   -15 In problem D. Vitya and Strange Lesson:The first pretest case: 2 2 1 3 1 3 The xor arrays are as follows: [0, 2] [2, 0] Therefore the output should be: 1 1 And not as in the example given: 1 0 Am I correct or do I miss something?
•  » » 3 years ago, # ^ | ← Rev. 3 →   0 1)0 2 mex = 12)3 1 mex = 0
•  » » » 3 years ago, # ^ |   0 Thank you, I missed the line about the array updating for each query :)
•  » » 3 years ago, # ^ |   +1 "Note that after each query the array changes." So the second array will be constructed by using the XOR operator on the first array, not the original one.
•  » » 3 years ago, # ^ |   0 Seriously??? Can people comment during the contest???
•  » » 3 years ago, # ^ |   0 Why am I receiving negative votes on this comment ? I was asking a question regarding the pretest cases. Nothing relating to the solution :/
•  » » » 3 years ago, # ^ |   0 I guess you will get downvotes for this complain too.
 » 3 years ago, # |   0 is it necessary to solve B with integer calculations only ? i spent lots of time to solve it without doubles
•  » » 3 years ago, # ^ |   +1 You can use double but don't forget epsilon
•  » » » 3 years ago, # ^ |   +26 My faith is stronger than epsilon !
 » 3 years ago, # |   +10 How to solve C and D?
•  » » 3 years ago, # ^ |   0 C : You only need to check parents and vertex divisors.
•  » » » 3 years ago, # ^ |   0 Please explain.
•  » » » » 3 years ago, # ^ | ← Rev. 3 →   +1 You can make value g gcd of path, if it divides h(depth of vertex) — 1 or h values in the path. So it must divide current vertex or parent of current vertex. Complexity is O(N * d) where d is 480.
•  » » » » » 3 years ago, # ^ |   0 I seem to have some trouble understanding you algorithm. Could you explain it for a path (root) 6 - 3 - 4 - 14 (leaf)?
•  » » » » » » 3 years ago, # ^ | ← Rev. 3 →   +1 For 1st vertex answer is 6 because 6 divides 1 nodes. For 2nd vertex answer is 6 because 6 divides 1 nodes. For 3rd vertex answer is 3 because 3 divides 2 nodes. For 4th vertex answer is 2 because 2 divides 3 nodes.
•  » » » » » » » 3 years ago, # ^ |   0 For 3rd vertex, you can make the beauty 3 by making it's value 0
•  » » » » » » » » 3 years ago, # ^ |   0 sorry, mistype.
•  » » » » » » » » » 3 years ago, # ^ |   0 why is d 480?
•  » » » » » » » » » 3 years ago, # ^ | ← Rev. 2 →   0 I think it should be 450. Because sqrt(200000) <= 450 . for each node you are traversing the factors in sqrt time to check if at this level a particular divisor of this node also is a divisor of all or all — 1 of its ancestors.
•  » » » » » » » 3 years ago, # ^ |   0 My code implementation is weak, will you please explain me how to proceed to write the code? I know that we need to use dfs in this case? But what modification we need to do in dfs to make the logic work?
•  » » » » » 3 years ago, # ^ | ← Rev. 2 →   0 Diversity What about this simple solution that FAILS !! http://codeforces.com/contest/842/submission/29887074 at every node we store two GCD values, valueOne with exactly one node off in the path till here, and valueTwo with no one off in the path till here.
•  » » » » » » 3 years ago, # ^ | ← Rev. 2 →   0 try this data:412 3 4 31 22 33 4The correct answer should be:12 12 4 3
•  » » » » » » » 3 years ago, # ^ |   0 Thanks !! I was asking about the reason why that reasoning fails.
•  » » » » » » » » 3 years ago, # ^ |   0 The reason is that except the node and its parent, other nodes on the path to root can also be changed to 0. (please ignore my grammer mistakes)
•  » » » » » » » » » 3 years ago, # ^ |   0 But that is already incorporated in the DP right ?
•  » » » » » » » » » 3 years ago, # ^ |   0 The decision may change while going down the tree.
•  » » » » » » » » » 3 years ago, # ^ |   0 I am unable to understand that. please explain a bit more.
•  » » » » » » » » » 3 years ago, # ^ |   +2 Let's use the previous example.. When querying node 3, the decision is changing the value on the 2nd node to 0. But when querying node 4, the decision is changing the value on 3rd node to 0. Your algorithm wasn't able to handle this case.
•  » » » » » 3 years ago, # ^ |   0 excuse me , what does gcd mean ? i don't understand .
•  » » » » » » 3 years ago, # ^ |   0 GCD = Greatest Common Divider.
•  » » » 3 years ago, # ^ |   0 It is possible more in detail please
•  » » » » 3 years ago, # ^ | ← Rev. 2 →   0 For vertex u, record unchanged value and changed values.Since most changed values need to gcd with u, so the number of values will decrease to 2*root(2*10^5). record them and dp!
•  » » 3 years ago, # ^ | ← Rev. 3 →   +6 D can be solved by building a binary tree. Consider a tree of depth 19 where the leaf nodes represent 00...0, 00...1, ..., 11...11, i.e. all numbers of length 19 in binary. This choice is made because 2^19 is the smallest power of two larger than 3*10^5. The higher levels are represent if number p, the child nodes are 2*p and 2*p+1.For each x (assume the set doesn't change for a moment) the smallest number not in the set is the one most similar to x (starting from higher digits) XOR x. Therefore, we start from the top most node and if possible make the choice towards that which is the same as x. If there are no viable nodes in that direction, we go the other way.The value of each node is either true or false, false representing if the value is in the original set. As you move higher up the tree the value of the nodes are defined so node p is true if either 2*p or 2*p+1 is true.You don't have to change the set but keep XOR-ing each successive query. Total complexity is O(n + A + m log A).
•  » » » 3 years ago, # ^ |   0 Why don't have to update the entire array, can elaborate a bit?
•  » » » » 3 years ago, # ^ |   +9 Let's say the queries come in x, y, z. If we know how to solve by not changing the array for x, we can do the same and solve by not changing and solving for x^y, not changing and solve for x^y^z, because XOR is commutative.
•  » » » » 3 years ago, # ^ |   0 In first operation, you xor every element with x.In second operation, you xor every modified element with y.This is same as, xoring original elements with (x^y).In third operation, xor original elements with (x^y^z) instead of changing array after every operation.
•  » » » 3 years ago, # ^ |   +3 the smallest number not in the set is the one most similar to x (starting from higher digits) XOR x Could you elaborate this?
•  » » » » 3 years ago, # ^ |   0 Say x=11010. And we need to choose between a=11101 and b=10010. a^x is smaller than b^x.
 » 3 years ago, # |   0 How to solve C?
•  » » 3 years ago, # ^ | ← Rev. 4 →   +3 Do dfs on graph.In the dfs, Calculate the divisors of the current node.If this divisor divides atleast 'depth[cur_node] — 1' nodes on the path from root to this cur_node,then it can be a possible value for the gcd .Take maximum of all such values possible for that node — This is maximum beauty of that node.Or gcd(Parent of cur_node) is also a possible contender.Complexity — O(Nsqrt(Max_Val))..We keep an array(200005) that keeps track of how many nodevalues are divisible by a number in the path from root to cur_node.Sadly, it didn't pass pretest 7.
•  » » 3 years ago, # ^ | ← Rev. 9 →   +7 Check my solution: 29886456You can do a dfs dfs(currentVertex, parent, canSkip, currentGcd) where you go to the adjacent nodes as follows: dfs(adjacent, currentVertex, canSkip, gcd(value(currentVertex), currentGcd)) and, if canSkip=true, dfs(adjacent, currentVertex, false, currentGcd). To compute the answer we must call dfs(root, -1, true, 0). You can keep a set of states to avoid repeating vertices. That is, once you have computed a particular state, add it to a set and, if you end up there again, just return and do nothing. You may also have a vector ans where, in each state, you compute ans(currentVertex) = max(ans(currentVertex), gcd(value(currentVertex), currentGcd)) and, if canSkip = true, ans(currentVertex) = max(ans(currentVertex), currentGcd).Why does this work? Well, according to https://en.wikipedia.org/wiki/Highly_composite_number the most composite number in [1, 200000] has 160 divisors. We must note that gcd(a, b) will always give a value that is both a divisor of a and b. In our approach, this means that a vertex may only generate at most 160 new gcds. Also, we must take into account that we can skip a single vertex, so we can "inherit" the gcds from above, so a vertex may emit at most 320 values. This means that we have at most 200000 × 2 × 320 = 1.2 × 108 distinct configurations. Given that we have two seconds, it seems that this may fit into the time limit. However, we must note that this is an upper bound. In practice, the numbers are much smaller. To be honest, I do not know how to bound even more these numbers. During the contest, I generated random graphs with numbers with many divisors, or random graphs with only numbers of the form 2a × 3b and I saw that I was not able to make it fail, no matter what I tried. I also generated arrays of numbers and computed the amount of distinct gcds I could get by ignoring zero or one numbers at a time, and I also saw that the numbers were very small.
 » 3 years ago, # |   +9 What is pretest 7 on problem C?
•  » » 3 years ago, # ^ |   0 And what is 15 ? :)
•  » » 3 years ago, # ^ |   0 keep getting wa on pretest 7 ...
•  » » » 3 years ago, # ^ |   0 Try 3 7 3 3 1 2 2 3 Answer should be 7 7 3. For me I had to change my approach completely to get AC.
•  » » » » 3 years ago, # ^ |   0 my program runs correctly for such tc ._.
 » 3 years ago, # |   0 What is the hack test for A ?
•  » » 3 years ago, # ^ | ← Rev. 2 →   +7 7 7 3 6 2Answer: NO
•  » » » 3 years ago, # ^ |   0 thanks
•  » » » 3 years ago, # ^ |   0 Thanks
•  » » 3 years ago, # ^ |   +1 May be -> 22 26 2 6 7 Answer : NO
 » 3 years ago, # | ← Rev. 2 →   -13 Hints fo E problem: The farthest vertex from any vertex is one of diameters centres. After adding new vertex you can easily recalculate diameter ends. Let a and b be old ends and c is a new vertex. Then new diameter will be (a,b), (a,c) or (b,c). There are only 1 or 2 centres of diameter and after adding new vertex only one of them can change. You can build segment tree on euler tour of this tree. You can serve maximum distance to the nearest centre and number of vertexes that satisfy that condition.
 » 3 years ago, # |   0 my first div1 round
•  » » 3 years ago, # ^ |   +38 -is yet to come.
 » 3 years ago, # |   +49
 » 3 years ago, # |   0 n * logn * logn is too much for D ?
•  » » 3 years ago, # ^ |   0 It's about 10^8, so it could be too much if your constant is big enough.
•  » » » 3 years ago, # ^ |   +3 just needed one minute . did it in n * log right now
•  » » 3 years ago, # ^ |   +18 map trie ??? no need array trie was enough as highest node will be <=(1<<20)
•  » » 3 years ago, # ^ |   0 Just got AC with n*logn*logn solution 29901340
 » 3 years ago, # |   0 Hack case for A ?
•  » » 3 years ago, # ^ |   0 8 13 1 4 7
•  » » » 3 years ago, # ^ |   0 The answer is NO right ???
•  » » » » 3 years ago, # ^ |   +9 yes
 » 3 years ago, # |   +36 How to solve statement of problem E?
•  » » 3 years ago, # ^ | ← Rev. 3 →   +21 If I understood correctly you are given a tree, find number of vertexes that can be endpoint of diameter.
•  » » 3 years ago, # ^ | ← Rev. 2 →   +34 The statement is ridiculous. They should let it be pure graph statement!
 » 3 years ago, # |   +1 what was wrong on pretest 4 on C ?
•  » » 3 years ago, # ^ |   +1 3 3 4 3 2 1 2 3 Answer is 3 4 3
•  » » 3 years ago, # ^ |   0 3 2 5 8 1 2 2 3Ans: 2 5 2
 » 3 years ago, # |   +2 Hack for C:37 3 31 22 3 Answer should be: 7 7 3.
 » 3 years ago, # |   +3 How to solve div 2 C?
•  » » 3 years ago, # ^ |   +9 In a dfs keep a set of all the gcd you can make till the index you are on and then take gcd of value of current node with all element in the set and add one extra element which is total gcd till last element. As, the number of distinct gcd you will hold will always be less than cubroot(max value of node). as, a number has <= cubrt(n) divisors. so your solution would be O(n*cubrt(n))I got the solution 10 minutes before the end of contest and wasn't able to code it :(
•  » » » 3 years ago, # ^ |   +6 I got the same logic for C and coded it but set size as 10^5 and noted it at the end of the contest and couldn't change that value.
•  » » » 3 years ago, # ^ |   +3 How do you know the number of distinct gcd will always be less than cubroot(max value of node) ?
•  » » 3 years ago, # ^ |   0 You can make a DFS(u, depth), depth will be the number of the vertices on the road from 1 to u. In vertex u, you will want to know for every integer i, how many vertices on the road from root to u are multiple of i, assume it's fre[i]. We will get another information, that is Max[x] = y, y will be the maximum value that be the divisor of the value of x vertices on the road from 1 to u. fre[] is easy to calculate, with every divisors v of a[u], fre[v]++, and after each increases, we update Max[fre[v]] = max(Max[fre[v]], v). So res[u] (result of vertex u) will be max(fre[depth], fre[depth — 1]). Just remember, after visiting all u's branches, you have to remake the values of fre[] and max[] to the values before you dfs to u (like how we use back-tracking to generate permutations).My code: 29897727
 » 3 years ago, # |   +24 RIP rating
•  » » 3 years ago, # ^ |   +6 RIP color
 » 3 years ago, # |   +41 For C, the basic observation is that the gcd value will either remain constant as we go down from the root, or it will atleast decrease by half. So there can be atmost 18 different points that we need to consider for removal.
•  » » 3 years ago, # ^ |   +1 elegant solution!
 » 3 years ago, # |   +19 Lucky Guy!
•  » » 3 years ago, # ^ |   +12 It was me :P
 » 3 years ago, # | ← Rev. 2 →   +12 Hack for A problem: 7 7 3 6 2Answer: NOThis happened because 7 is not divisible by 2. So you cant solve this using formula.UPD: My fault, you can: http://codeforces.com/contest/842/submission/29883923
•  » » 3 years ago, # ^ |   0 http://codeforces.com/contest/842/submission/29883923 This is a mathematical solution.
•  » » » 3 years ago, # ^ |   0 You can avoid division by doing this : http://codeforces.com/contest/842/submission/29905885 But then this is wrong solution, I don't know where ? There are two line segments — [l, r] and [kx, ky] we just need to check if they intersect at any point or not. This follows from the fact that, answer will exist if and only if for a given value of a there exist a value of b which is a/k in the interval [x, y], which is same as a also belonging to [kx, ky]. Unfortunately the test cases are not visible.
•  » » » » 3 years ago, # ^ |   0 The whole point of dividing was so that I could take the floor and ceiling of both numbers. By doing this, you can passtaht hack up there.
•  » » » » » 3 years ago, # ^ |   0 I'm not able to understand the ceil and floor usage. Please explain about them.
•  » » » » 3 years ago, # ^ |   0 I solved using a similar approach but did binary search to see if a value (v) exists in the range [x,y] for which v*k lies between l and r
 » 3 years ago, # |   0 How to solve D? Please explain if you can.
•  » » 3 years ago, # ^ |   0 my idea : pre store n * logn numbers first throw out the numbers until there is at most one of each . then just pre calculate the prefix of numbers in binary in an array . for example for 5 : store numbers 0000000000000001 00000000000010 00000000000000101 then the problem is simple ! think for yourself
•  » » » 3 years ago, # ^ |   0 i just stored this numbers as strings in a map but you can put an extra 1 in the beginning and just store the number
•  » » 3 years ago, # ^ |   0 I solved it using trie
•  » » » 3 years ago, # ^ |   0 Did you find the Mex using trie?
•  » » » » 3 years ago, # ^ |   0 yes
•  » » 3 years ago, # ^ | ← Rev. 3 →   +24 Let A be an array of numbers that our original array doesnt consist of.Then mex(a) = minimum element of A.1 useful fact: after operation (a xor x) mex will be minimum of array (A xor x).You dont need to save all changes, just xor new query with old. Like xi = xor(x0, x1, x2 .. xi).Original array A you can store in bit trie. Now you iterate over bits, from large to small. You mission is to decrease y (the number you get from trie) xor xi. So if j-th bit of xi is equal to 1 you should go through "1" edge in the trie if you can. Similarly for "0" bit. Answer will be y (the number you find) xor xi.Sorry for my bad English.
•  » » » 3 years ago, # ^ |   0 He knows русский
•  » » » 3 years ago, # ^ |   0 Why mex(a) = minimum element of a?
•  » » » » 3 years ago, # ^ |   0 mex(a) = minimum element of A, where A is an array of numbers, that a doesnt consist of.For example: a = [1, 2], then A = [0, 3, 4, 5, .. 300000]
•  » » » 3 years ago, # ^ |   0 The same solution but you don't need trie. Normal sorted array is enough. You just make lower_bound for every bit.
•  » » » 3 years ago, # ^ |   0 could you please explain "1 useful fact: after operation (a xor x) mex will be minimum of array (A xor x)." ? didnt quite get it . since A is the array that does not contain original given numbers, why are we doing XOR of x(given query) with A ?
•  » » » » 3 years ago, # ^ |   +3 Let mex of the array after (a xor x) be M than after M xor x you get a number which cannot be in the oryginal array.
•  » » » » » 3 years ago, # ^ |   0 Why ?
•  » » » » » » 3 years ago, # ^ |   +3 I've explained that in my video: https://www.youtube.com/watch?v=PKDQO8B0V3A
•  » » » » » » » 3 years ago, # ^ |   0 Thanks :)
•  » » » » » 3 years ago, # ^ |   0 Thanks :) got it now .
•  » » 3 years ago, # ^ | ← Rev. 2 →   0 Greedy by bits. In fact, xor only change the priority of bits. For example, the xor number is 100010, and current number you choose is 101[0]00000, in present bit [0] is greater than [1](because of the effect of xor number). So we first check the number [101100000, 101111111], if all of the values occur, we can put a [0] here, otherwise we can only put [1]. If current bit of xor number is [0], we try [0] first. The checking can be solved by prefix sum. Finally we got the number before xor, so just print after xor. The total complexity is O(nlogn).
•  » » 3 years ago, # ^ | ← Rev. 11 →   0 Used : Bijection Property of function : f(x) = x^k ( k belongs to [0, 2**(n)-1] ) (XOR) : [0, 2**(n)-1] -> [0, 2**(n)-1]. Greedily finding the element which is not in A and closest to X. Instead of modifying Array itself, modifying query's input (Xj) by taking XOR with query input (Xi's) occered so far. int A[1000000]; int sumLR(int l, int r) { return ((r>=1000000)?A[1000000-1]:A[r]) - ((l-1)<0?0:A[l-1]); } int main() { int i,j,k,l,m,n,x,y,z,a,b,r; sd(n); sd(m); for(i=0;i<1000000;i++) A[i] = 1; for(i=0;i=0;i--) { if(sumLR( a | ((1<
•  » » » 3 years ago, # ^ |   0 @jvj_iit can you explain why A[i] += A[i-1] and how sumLR() works ?
•  » » » » 3 years ago, # ^ |   0 Array A is basically used here to maintain a Prefix sum array of counts of elements which are in [0, 2**(n)-1] (assume sufficiently large n), but not in set of input elements, i.e. A[i] stores count of elements which are less than equal to i and not in set of input elements. sumLR(l, r) simply returns count of elements which are lie in [l,r] but not in set of input elements.
 » 3 years ago, # |   0 For this testcase for problem B: 5 3 1 5 0 1 What should be the answer?
•  » » 3 years ago, # ^ |   0 It's 0.
•  » » » 3 years ago, # ^ | ← Rev. 3 →   0 But I hacked a solution whose output was 1. It showed me unsuccessful hack!!solution code: 29883956edit: sorry my bad. The code gives correct output i.e. 0.
•  » » » » 3 years ago, # ^ |   0 yes it should be 0
 » 3 years ago, # |   +15 Why in each round you make a big hardness difference between (C & D) or (B & C) like this round !! 4102 ACC for B , 446 ACC for C !! WTF !!
•  » » 3 years ago, # ^ |   +23 Plus people scored 12-13 hacks on A which got them points equal to C, although both the things aren't the same.
•  » » 3 years ago, # ^ |   0 Maybe they like repeating :)
•  » » 3 years ago, # ^ |   +5 Less ACC for A than B too!
 » 3 years ago, # |   0 Is O(nsqrt(maxval)) good enough in c?
•  » » 3 years ago, # ^ |   0 firstly i got tle, then optimize it and changed to printf and got ac in pretest
 » 3 years ago, # |   +3 Any ideas for C? Problem was intersting, but a litle more difficult than standard for "C"(Div 2).
•  » » 3 years ago, # ^ |   +1 Check the frequency of divisors of the node you're on. If there's at most one missing, it can be an answer. As soon as a number has one missing, it might be an answer for one more node and then the rest must have this number as divisor otherwise there will be 2 missing and it won't be an answer. So just check the current node and parent node's divisors (or send the maximum from the current node that has no missing frequency to the next nodes).
•  » » » 3 years ago, # ^ |   0 hello, I am trying to implement exactly what u said, but getting WA on test case number 7. Can you please, find what is wrong in my code?or provide me some critical test cases? thanks.29930421
•  » » » » 3 years ago, # ^ | ← Rev. 2 →   0 http://codeforces.com/contest/842/submission/29931334 at line 200 you need to mark 1 as visited otherwise the path will go back to 1. Edit: other than that, long long might be causing TLE.
•  » » » » » 3 years ago, # ^ |   0 thank u, but now TLE :P how to get rid of that?
•  » » » » » » 3 years ago, # ^ |   0 You have a few options:Get rid of vis and just keep the edges you need.Get rid of long long as in here: http://codeforces.com/contest/842/submission/29931449Turns out you are making O(divisors * n) modulo operations and modulo is really costly on codeforces if you use long long.
•  » » » » » » » 3 years ago, # ^ |   0 thank u. you already did it for me. :D you are too fast brother :)but the execution time is 1996 ms. that is too tight. how to improve my solution?
•  » » » » » » » » 3 years ago, # ^ | ← Rev. 3 →   0 You can change the frequency of divisors running through the list of divisors as in my solution: http://codeforces.com/contest/842/submission/29885607You can also optimize this solution to O(nlog(maximum value)). You need to optimize the second part, running it through every prime in the prime factorization (and every possible exponent for that prime) and multiplying the answers to get the second part of the answer.For example: if you have 2^5 * 3^4, you can run it for 2^1, 2^2, 2^3... and take the largest power of 2 you can for every node and the same for 3.Edit: I'm not sure about the second part actually. Someone did something similar but what I wrote looks wrong. Edit2: it was this guy http://codeforces.com/blog/entry/54120?#comment-382225
•  » » » » » » » » » 3 years ago, # ^ |   0 ok, this is getting weird!why am i getting TLE now? -_- 29931793
•  » » » » » » » » » 3 years ago, # ^ |   0 As you said, the way you coded is too close to TLE :/
•  » » » » » » » » » 3 years ago, # ^ |   +5 brother, u told me "Get rid of vis and just keep the edges you need.".i just add: if(d<=(lvl-2)) return;and got acc in 951 ms.(faster than yours :D :D )thank u so much for ur help. :)
•  » » 3 years ago, # ^ |   +1 There are atmost root(n) divisors of n. For node 1 calculate all it's divisors and run a dfs with a divisor assumed as answer and see how far you can go with only change (a number to 0 in path) and maintaining gcd equal to that number. Do it for all the divisors. That's a n root(n) solution. One more case when you change node 1 to 0 can be handled by just changing it and running dfs with no further number change and taking gcd of all the nodes in path. Not to mention every time you reach a node ans[node]=max(ans[node],current). Put all answers to 1 by default.
•  » » » 3 years ago, # ^ |   0 My idea is very much similar to yours, but i am getting wa.can you please help?my code: 29930421
•  » » » 3 years ago, # ^ |   0 There are atmost root(n) divisors of n ?? Not Really !! Divisors for 12 : 1, 2, 3, 4, 6, 12 root(12) -> 3.46
•  » » » » 3 years ago, # ^ |   0 I meant complexity wise , if you're talking constants 2*root(n)
•  » » 3 years ago, # ^ |   +3 n Log n solution: you factorize the root, (at most there are log n factors) for each prime factor you solve the problem separetely: for each vertex and prime factor you save if it is possible to get the factor down so far, and if yes then save which vertex you changed to zero doing so(if you did)(for each prime factor can be done in O(n)), when you preprocessed all of this, for each vertex you check how much of those prime factor you can get down here changing only one(or less) vertex to 0.Also you need to consider the case when the root node is replaced by zero, which is trivial to solve. My submission: 29900204
•  » » 3 years ago, # ^ |   0 An O(idk) solution: for each vertex store a set of gcds of all possible numbers on the path to root with one element excluded. And try to prove that in the long run (like when the depth of the vertex is huge enough) its set will contain a negligibly small number of gcds :) 29884556
•  » » » 3 years ago, # ^ | ← Rev. 2 →   +5 Simplified Version : You cannot do skips, then you will have at most logai distinct values. (easy to prove).It should be intutive that the number wouldn't be much larger with skips. I was convinced it's bounded by sqrtN in worst case.
•  » » » » 3 years ago, # ^ | ← Rev. 2 →   +5 So was I, and that is the reason why I submitted :DAccording to the execution time, the sizes shouldn't exceed log(n) per set.
•  » » 3 years ago, # ^ |   0 Thank you all)
 » 3 years ago, # |   0 Good thing we have the comments or else there would be no other way to ask questions during the contest.
 » 3 years ago, # | ← Rev. 3 →   0 look at fatego's code, his for loop in problem c and in problem d is different. I think it is obvious that he cheated.
 » 3 years ago, # |   0 how to solve B. I took 5 points from the x,y given and checked if all of them lie in crust or not. Apparently that is not how its supposed to be done :(. http://codeforces.com/contest/842/submission/29896449
•  » » 3 years ago, # ^ |   0 Let d_i be the distance from the center of the sausage to the origin. Then, the sausage is on the crust iff r — d + r_i <= d_i <= r — r_i
•  » » » 3 years ago, # ^ |   0 kind of did the same. I have center as x,y. let rr be the radius of sausage. I checked if dist(x-rr,y), dist(x+rr,y), dist(x,y-rr), dist(x,y+rr),dist(x-rr,y), dist(x,y) all lie in r-d.
•  » » » » 3 years ago, # ^ |   0 That won't necessarily work though. You can imagine a situation where a sausage just has a small upper-right portion sticking out of the crust.
•  » » » » » 3 years ago, # ^ |   0 that did not seem possible to me at that time. :(
 » 3 years ago, # |   +3 How long do you have you wait to submit for practice? Is it once system testing is done?
 » 3 years ago, # |   +67 my reaction when a solution strikes me during the last 5 minutes
 » 3 years ago, # |   -27 ABC
•  » » 3 years ago, # ^ |   +23
 » 3 years ago, # |   0 What happened to rating change predictor? I am unable to see it.
•  » » 3 years ago, # ^ |   +1
•  » » 3 years ago, # ^ |   +1 It's takes some time to load rating change, probably you should wait few more seconds.
 » 3 years ago, # |   +38 Very bad, that there is no explanation to sample testcases. I couldn't understand problem E for 10 minutes.
 » 3 years ago, # |   +3 Is it only my problem, or show unofficial button changes randomly when refreshing.
•  » » 3 years ago, # ^ |   0 happened for me.
•  » » 3 years ago, # ^ |   0 yeah just keeps changing
 » 3 years ago, # |   0 I really want to understand graphs better (like in problem C). Can someone please suggest some good tutorials (using C++ STL only please) other than Hackerrank.
•  » » 3 years ago, # ^ |   0 Read the analysis and all And solve the problem SPBGU in training with 2 stars when you solve all probably will already fumble in the graphs there is a problem purely on the algorithms that are in the internet but these algorithms are the most important
•  » » » 3 years ago, # ^ |   0 Can you give a link probably to SPBGU?
•  » » » » 3 years ago, # ^ |   0 Go to the training tab Choose the complexity of the 2 stars Find the last workout on this list
•  » » » » » 3 years ago, # ^ |   0 Do I miss something?
•  » » » » » » 3 years ago, # ^ | ← Rev. 2 →   +2 http://codeforces.com/gym/100166He's talking about SPb SU trains.
•  » » » » » » » 3 years ago, # ^ |   0 Thanks. Are there more?
 » 3 years ago, # |   0 How to solve about D ?
 » 3 years ago, # |   0 Is python so slow? Couldn't even perform 10^7 operations in 2 seconds!Link
•  » » 3 years ago, # ^ |   0 My Solution gave TLE on main test case 101. I was considering k to be non integer type(decimal). But after reading i found out it was integer. Link..
 » 3 years ago, # | ← Rev. 2 →   0 |
•  » » 3 years ago, # ^ |   0 "First string contains five integer numbers l, r, x, y, k", this is mentioned.
•  » » 3 years ago, # ^ |   0 he said the efficiency is non integer which means that a/b can be non integer , but he didn't say that k can be a non integer .
•  » » » 3 years ago, # ^ |   0 Input First string contains five integer numbers l, r, x, y, k (1 ≤ l ≤ r ≤ 107, 1 ≤ x ≤ y ≤ 107, 1 ≤ k ≤ 107).
 » 3 years ago, # |   0 someone plzz tell logic of ques C??
 » 3 years ago, # |   +1 I got MLE for mapping values in the range l to r using C++ STL map.. i know max value of r was 10^7 but as far i know STL map can handle this unlike Array.. can anyone explain what is the reason for MLE here?
•  » » 3 years ago, # ^ |   0 look 1e7 * log(1e7) * const > 2e9, so you can get tl
•  » » » 3 years ago, # ^ |   0 oh. got it. but why MLE here? what's the reason behind MLE?
•  » » » » 3 years ago, # ^ |   0 Sorry i read TLE, for MLE the same 1e7 * long long > 70 MB and map his big constant
 » 3 years ago, # |   +64 Seeing how a lot of submission for A got hacked, I feel fortunate being able to come up with my super elegant 107 for-loop solution.
•  » » 3 years ago, # ^ |   0 and math with 1 line also wrong...
•  » » 3 years ago, # ^ |   0 I just checked whether there is an intersection of range..but it failed system tests.. As test-cases are not visible, I'm am not able to get that case..Can someone please help..!
•  » » » 3 years ago, # ^ |   +1 Try 5 5 2 3 2, this should be NO. Your solution says YES.
•  » » » » 3 years ago, # ^ | ← Rev. 2 →   0 Thanks..that was the missing case..!
•  » » » » 3 years ago, # ^ |   0 Why this is NO ? 5/2 == 2, and so you found (a,b) = (5, 2).
•  » » » » » 3 years ago, # ^ |   0 The problem statement states that efficiency is a non-integer number, so 5/2 is 2.5
•  » » 3 years ago, # ^ |   0 I got TLE in double for loop :(. forgot to check for integer in single for loop. got hacked
 » 3 years ago, # | ← Rev. 2 →   +4 Why can't we see the testcases?
 » 3 years ago, # |   0 When will the rating be updated?
 » 3 years ago, # |   0 My solution for C keeps failing for pretest 4, does anybody have any idea about what that case may be?
•  » » 3 years ago, # ^ |   0 Try this:7 35 5 35 7 35 5 7 1 2 2 3 3 4 4 5 5 6 6 7answer: 35 35 35 7 7 5 1
•  » » » 3 years ago, # ^ |   0 works fine. Link
•  » » » » 3 years ago, # ^ | ← Rev. 2 →   0 try this:8 4 8 7 3 2 4 10 1 1 2 1 3 2 4 4 5 3 6 3 7 7 8answer: 4 8 7 4 2 4 2 1
•  » » 3 years ago, # ^ |   0 Value of the root node can be changed to 0 in computing gcd for any of the children nodes.
 » 3 years ago, # |   0 Help me, please!Tell me, what I'm doing wrong in problem A? Here is my program: http://codeforces.com/contest/842/submission/29897053. Please, tell me testcase 8 if you can.
•  » » 3 years ago, # ^ |   +1 you reversed ranges, we have b*k =a you checked k*a=b
•  » » » 3 years ago, # ^ | ← Rev. 2 →   0 Thank you very much!!!It looks like in testcases 1-7 k = 1... It's very sad...
 » 3 years ago, # |   0 glebodin I understand that there is some problem with codeforces right now and we are unable to see the test cases. If possible, could you share the test cases in form of some repository for now. I think it would be of great help for many users.
•  » » 3 years ago, # ^ |   +3 I'm sorry, I can't (same problems) and this is the reason i can't post editorial
 » 3 years ago, # | ← Rev. 8 →   +81 To some extent, the test cases for problem E are weak.There exists a solution that maintain the points meeting the condition by using brute force. See these two solutions 29894980 and 29894566 for more details. Both of them can be easily hacked by building a star graph and then adding a long chain to the root. To be more specific, here is the test case: 300000 1 1 1 1 ...(149995 ones omitted) 1 150001 150002 150003 ... 300000 Now I am still trying to hack other solutions...UPD: I give up and dicide to go sleeping.
•  » » 3 years ago, # ^ | ← Rev. 2 →   0 Can you hack this one: 29901727.Though it seems like an amortized O(N) because each element is moved at most 3 times, I'm not totally sure. It just seems a bit unclear why dividing the nodes in 3 sets like this makes it work. For example it's clear when the diameter is odd we keep a left and right part, but when it is even, we have a center and it gets more complicated.
•  » » » 3 years ago, # ^ |   +13 Well, I think your solution is correct but I am also not sure.Also I have found a similar solution 29892728 that divides the nodes into two parts and tried to hack it but in vain. It seems that if a node moves from one set to another, it will never come back or otherwise it will never meet the condition.
•  » » 3 years ago, # ^ |   0 I knew that my code would fail before systest so I'm wondering why my code passed.
 » 3 years ago, # |   +11 Can you see the mistake in this picture? ._.
•  » » 3 years ago, # ^ |   0 rating--
•  » » » 3 years ago, # ^ |   +3 if new_color != prev_color: print prev_color
•  » » 3 years ago, # ^ | ← Rev. 2 →   +8 Still a Newbie :(
 » 3 years ago, # |   0 Can Someone tell me the corner test case that my code fails on for Problem A. It fails on Test case #38. Link to my code is: http://codeforces.com/contest/842/submission/29874288
•  » » 3 years ago, # ^ |   0 You have long i and k. So i * k overflows before getting assigned to val.
•  » » » 3 years ago, # ^ |   0 Thank you
 » 3 years ago, # |   +20 nice contest with fast testing and rating update, thank you
 » 3 years ago, # |   0 Not fair if you're holding a contest, with a bug, Not allowing test cases to be seen. How am i able to upsolve?
 » 3 years ago, # |   +1 Can't figure out the mistake in A. Could someone please provide a test case, thanks.
•  » » 3 years ago, # ^ |   0 3 3 1 2 2 is a possible test. The idea is to find [l,r] such that no multiples of k lie in this interval.
•  » » 3 years ago, # ^ |   +3 I think someone pointed to this, try for example 5 5 1 10 3, it will give yes in your code but it has to be no
 » 3 years ago, # |   0 Even this passed the pretests,very weak test cases. int main() { long long int l,x,r,y,k; cin>>l>>r>>x>>y>>k; int flag=0; for(int i=x;i<=y;i++) { if(l<=x*k&&x*k<=r) //this line though :) {flag=1;break;} } if(flag) cout<<"YES\n"; else cout<<"NO\n"; } 
•  » » 3 years ago, # ^ |   0 Am i wrong? I see no problem in this code
•  » » » 3 years ago, # ^ |   +12 There's no i in the if statement.
•  » » » » 3 years ago, # ^ |   0 ???
•  » » » » » 3 years ago, # ^ |   +13 Check for loop carefully There is no index i inside the loop.
•  » » » » » » 3 years ago, # ^ | ← Rev. 2 →   0 Oh i see it. But was it accepted? If it hadn't passed been accepted then the test cases wouldn't be weak
•  » » » » » » » 3 years ago, # ^ |   +10 No it was not accepted but it passed the pretests.
•  » » 3 years ago, # ^ |   +5 I would have helped you find this bug if you were in my room =)
•  » » 3 years ago, # ^ | ← Rev. 2 →   0 By the way, does anyone see the problem with this solution? (Doesn't pass test 26: 29901876) long long l, r, x, y, k; cin >> l >> r >> x >> y >> k; auto min_v = k * x; auto max_v = k * y; bool inside = l <= min_v && max_v <= r; bool outside = min_v <= l && r <= max_v; bool intersect = l <= min_v && min_v <= r || l <= max_v && max_v <= r; bool exist = inside || outside || intersect; cout << (exist ? "YES" : "NO"); 
•  » » » 3 years ago, # ^ |   0 same problem as most hacked solutions, try this test 5 5 1 10 3
•  » » » » 3 years ago, # ^ |   +3 Oh, thank you. I get it now. So it looks like we can't solve this task in O(1), because we can't just intersect the segments. Good thing I wasn't trying to be smart during the contest and just did a simple for loop =)
•  » » » » » 3 years ago, # ^ | ← Rev. 2 →   +16 I am a simple man, I see a naive solution that will pass the constraints, I implement it :D
•  » » » » » 3 years ago, # ^ |   0
•  » » » » » » 3 years ago, # ^ |   0 Hmm..Now I'm confused. What's the difference between my solution and that one?
•  » » » » » » 3 years ago, # ^ |   0 I think this solution is based on finding a range r2 which contains all possible numbers that if any number of them in multiplied by k the result will be a number in the range l to r, so if x to y contains any number from the range r2 so the answer exists, really nice solution
 » 3 years ago, # | ← Rev. 2 →   +4 Can anyone write shorter solution to A than this?
 » 3 years ago, # |   +3 For problem D I could not figure out how to find the least xor with an element NOT in the trie. What I ended up doing was putting in every number except for those in the array and did a least element query with that. How did everyone else do it?
•  » » 3 years ago, # ^ |   0 I used subtree size in trie to find min element. If there is xor 0 at that position and if left subtree in incomplete go to left else go to right. If there is 1 then check the same for right subtree and then left.
 » 3 years ago, # |   +2 when is the editorial going to release.
 » 3 years ago, # |   0 So there are no official solutions for each problems? I see there are "problem tags" which can be used as a hint, but no more detail one? Thanks!
 » 3 years ago, # |   +11 Sorry to say,I can't totally understand the statement in the beginning until the announcement.But the problems are nice.
 » 3 years ago, # |   0 WA 29905833 Instead of storing all the divisors of current nude in a vector because of memory constraints, I tried to iterate through all divisors of current node again and decremented the count. Why does this fail?
•  » » 3 years ago, # ^ |   0 Your solution will fail for tests some thing like this:  3 8 1 9 1 2 2 3  Answer should be 8 8 1. But I think your code will output 8 8 9
 » 3 years ago, # |   +22 For a purely Div. 2 contest, please list the Div. 2 winners first in the editorial. They deserve their moment in the sun! Otherwise, I don't understand the purpose of the "Div. 2 only" contest: - The Standings show all divisions, which is dominated by Div. 1. - Then the editorial shows the Div. 1 winners first.So what is the point? Is it about rating? Even there, I believe that NOT including D1 players in the rating calculation hurts D2 players — because D2 is expected to rank lower than D1, so if we included the top division in the rating, the D2 players can only gain.If I am missing something, please let me know, otherwise I would love for there to be an editorial guideline at CF to show D2 winners first, in the D2 contests. I can never dream of being in the D1 top 5, but I CAN dream of being in the D2 top 5 list one day!Thanks for your consideration.
•  » » 3 years ago, # ^ |   +2 All the people who are purple in the top 5 rating of the 2nd division have already become purple after the recalculation of the rating in this round.
•  » » 3 years ago, # ^ | ← Rev. 2 →   0 Uncheck 'Show unofficial' when on the standings page. The Div. 2 winners are right there, 6 lines below overall winners. Don't whine about it so much.
 » 3 years ago, # |   +5 Does anyone know what is test 6 in problem D, why am I keep WA on test 6?My submission: http://codeforces.com/contest/842/submission/29896373
•  » » 3 years ago, # ^ |   +6 insert into the Trie unique values only
•  » » » 3 years ago, # ^ | ← Rev. 2 →   +5 I was such an idiot in this contest. Thank you very much. I now realized my mistakes!
 » 3 years ago, # |   +12
 » 3 years ago, # |   0 Why Memory limit exceeded on test 43 in Problem A(Kirill And The Game) My code Can someone please help?
•  » » 3 years ago, # ^ |   0 When you're never using list a, why do you create it ?
•  » » » 3 years ago, # ^ |   0 Thanks, that solved memory issue but now I am getting TLE in test case 51. My Submission
•  » » » » 3 years ago, # ^ |   0 Maybe because you're always assuming j to fit into an integer. It may exceed int, try using long long. Or otherwise I think this is because of the language issue. I don't know which function you're using there from Python is causing TLE. You need to do some optimization perhaps.
•  » » 3 years ago, # ^ |   +3 You don't need to convert those range objects to list.And there is about 10 ** 7` actions in your solution. Python is just not so fast for doing this (but you could try PyPy).
 » 3 years ago, # |   +9 is there no editorial??
 » 3 years ago, # |   +5 Where is the editorial?
 » 3 years ago, # |   +5 When will the editorial be added?
 » 3 years ago, # |   +2 This was my First Contest (I m new in here). I solved 1000 points problem in my second attempt (on my first I missed a trivial edge case) but I got 698 points though at the end of the contest my solution was "Accepted" . Why wasnt I awarded full marks for the solution (I know I made a penalty of 50 points due to incorrect first attempt) . Was it only because of time that I was awarded 698 instead of 950 ? What are the factors on which the awarded marks depend upon ? (any link would also help :) )
•  » » 3 years ago, # ^ |   +4 Look at point 3 here: http://codeforces.com/blog/entry/456.
•  » » » 3 years ago, # ^ |   0 Thanks for the Link . That helped :)
•  » » 3 years ago,