Всем привет!
29 августа 2017 в 18:05 (по московскому времени) состоится рейтинговый Codeforces Round #430 для участников из второго дивизиона. Как всегда, участники из первого дивизиона смогут принять участие вне конкурса.
Задачи для вас готовили Глеб Glebodin Лобанов, и Илья Ilua Максимов. Большое спасибо Алексею Perforator Рипинену за помощь в подготовке раунда, Даниилу qoo2p5 Николенко, Ильдару 300iq Гайнуллину и Алексею Livace Илюхову, Ивану BledDest Андросову, Максиму HellKitsune Финютину за тестирование задач и конечно же Михаилу MikeMirzayanov Мирзаянову за замечательные системы Codeforces и Polygon.
Участникам будет предложено пять задач и 2 часа на их решение.
Разбалловка — стандартная: 500 — 1000 — 1500 — 2000 — 2500.
Надеемся, раунд вам понравится! Всем удачи!
Поздравляем победителей!
Div. 1:
Div. 2:
Auto comment: topic has been updated by Glebodin (previous revision, new revision, compare).
Автокомментарий: текст был обновлен пользователем Glebodin (предыдущая версия, новая версия, сравнить).
Wow, very short announcement and very fast publish of scoring!
yeah, why are they always publishing the scoring distribution in the last 10 minutes.
I think, because testers say something like "it's a bit harder, then i think" and they must wait for their decision.
I hope the problems will short too :)
Obligatory comment about hoping the problem statements to be as short as announcement..
+Fast system test
By the way. Who can explain why there is a big lag between contest finish and system testing start?
it is the shortest announcement I have ever seen .
Is this the best month or what!
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.
I'll leave this picture as a reminder for the russian problem setters =)
sorry for my bad english
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.
Maybe on the russian site they say the same about russian statements when there is a non-russian setter.
Not at all. The Russian translations are pretty much always spot on because they get native Russian speakers to do them.
But then again, native speakers can skrew up translations into Russian if the original statements were written in English.
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
In the past, Delinur has either translated or reviewed the translations of statements in nearly every contest. Does this position not exist any more?
Perhaps learning to capitalize your I's would be a good start.
that's punctuation not grammar
Orthography, you mean, which is part of grammar in the greater sense of the word.
Nobody needs a "professional editor" for problem statements, a native English speaker with some CF experience will suffice.
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. :)
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!
Before anything else,
Why must you use memes incorrectly?
You didn't say if it is rated. Is it rated?
finally correct
is it rated?question. Yes it is.А Семён Романенко тоже помогал готовить задачи?(надеюсь не очень сложно пошутил)
Вегда было сложно на контестах от синих юзеров, не знаю почему :)
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.
Why did you write this
Bravo :|
Are you on drugs?
Did you forget to log out your Codeforces account on your friend's laptop?
He's 13, He gets up at 9 and sleep at 20, he surly doesn't have friends
Is this your own experience ?
Right in the feelings
baba Khafan amsal shoma hamishe naghsheshoon kam rang bood
ypa!!ypa a a a
wow ............ Total: 7983 Contestants: 7600 Out of competition: 383
problem: C. Ilya And The Tree what it the biggest common divisor if one of the numbers are 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)
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..
write me (if you want)
In problem D. Vitya and Strange Lesson:
The first pretest case:
The xor arrays are as follows:
Therefore the output should be:
And not as in the example given:
Am I correct or do I miss something?
1)0 2 mex = 1
2)3 1 mex = 0
"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.
Seriously??? Can people comment during the contest???
Why am I receiving negative votes on this comment ? I was asking a question regarding the pretest cases. Nothing relating to the solution :/
I guess you will get downvotes for this complain too.
is it necessary to solve B with integer calculations only ?
i spent lots of time to solve it without doubles
You can use double but don't forget epsilon
My faith is stronger than epsilon !
How to solve C and D?
C : You only need to check parents and vertex divisors.
Please explain.
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.
I seem to have some trouble understanding you algorithm. Could you explain it for a path
(root) 6 - 3 - 4 - 14 (leaf)?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.
For 3rd vertex, you can make the beauty 3 by making it's value 0
sorry, mistype.
why is d 480?
Len
What about this simple solution that FAILS !!
http://mirror.codeforces.com/contest/842/submission/29887074
at every node we store two GCD values, valueOne with exactly
one node offin the path till here, and valueTwo withno one offin the path till here.try this data:
4
12 3 4 3
1 2
2 3
3 4
The correct answer should be:
12 12 4 3
Thanks !!
I was asking about the reason why that reasoning fails.
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)
But that is already incorporated in the DP right ?
The decision may change while going down the tree.
I am unable to understand that. please explain a bit more.
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.
excuse me , what does gcd mean ? i don't understand .
GCD = Greatest Common Divider.
It is possible more in detail please
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!
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).
Why don't have to update the entire array, can elaborate a bit?
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.
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.
Could you elaborate this?
Say x=11010. And we need to choose between a=11101 and b=10010. a^x is smaller than b^x.
How to solve C?
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.
Check my solution: 29886456
You 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, ifcanSkip=true,dfs(adjacent, currentVertex, false, currentGcd). To compute the answer we must calldfs(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 vectoranswhere, in each state, you computeans(currentVertex) = max(ans(currentVertex), gcd(value(currentVertex), currentGcd))and, ifcanSkip = 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.
What is pretest 7 on problem C?
And what is 15 ? :)
keep getting wa on pretest 7 ...
Try
Answer should be
7 7 3. For me I had to change my approach completely to get AC.my program runs correctly for such tc ._.
What is the hack test for A ?
7 7 3 6 2
Answer: NO
thanks
May be -> 22 26 2 6 7 Answer : NO
Hints fo E problem:
my first div1 round
-is yet to come.
n * logn * logn is too much for D ?
It's about 10^8, so it could be too much if your constant is big enough.
just needed one minute . did it in n * log right now
map trie ??? no need array trie was enough as highest node will be <=(1<<20)
Just got AC with n*logn*logn solution 29901340
Hack case for A ?
8 13 1 4 7
The answer is NO right ???
yes
How to solve statement of problem E?
If I understood correctly you are given a tree, find number of vertexes that can be endpoint of diameter.
The statement is ridiculous. They should let it be pure graph statement!
what was wrong on pretest 4 on C ?
Answer is
3 4 33 2 5 8 1 2 2 3
Ans: 2 5 2
Hack for C:
3
7 3 3
1 2
2 3
Answer should be: 7 7 3.
How to solve div 2 C?
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 :(
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.
How do you know the number of distinct gcd will always be less than cubroot(max value of node) ?
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
RIP rating
RIP color
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.
elegant solution!
Lucky Guy!
It was me :P
задача А 6 6 1 2 4 ответ NO
Hack for A problem: 7 7 3 6 2
Answer: NO
This happened because 7 is not divisible by 2. So you cant solve this using formula.
UPD: My fault, you can: http://mirror.codeforces.com/contest/842/submission/29883923
http://mirror.codeforces.com/contest/842/submission/29883923 This is a mathematical solution.
You can avoid division by doing this : http://mirror.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 checkif 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
athere exist a value of
bwhich isa/kin the interval [x, y], which is same asaalso belonging to[kx, ky].Unfortunately the test cases are not visible.
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.
How to solve D? Please explain if you can.
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
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
I solved it using trie
Did you find the Mex using trie?
yes
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.
He knows русский
Why mex(a) = minimum element of a?
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]
The same solution but you don't need trie. Normal sorted array is enough. You just make lower_bound for every bit.
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 ?
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.
Why ?
I've explained that in my video: https://www.youtube.com/watch?v=PKDQO8B0V3A
Thanks :)
Thanks :) got it now .
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).
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.
@jvj_iit can you explain why A[i] += A[i-1] and how sumLR() works ?
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.
For this testcase for problem B: 5 3 1 5 0 1 What should be the answer?
It's 0.
But I hacked a solution whose output was 1. It showed me unsuccessful hack!!
solution code: 29883956
edit: sorry my bad. The code gives correct output i.e. 0.
yes it should be 0
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 !!
Plus people scored 12-13 hacks on A which got them points equal to C, although both the things aren't the same.
Maybe they like repeating :)
Less ACC for A than B too!
Is O(nsqrt(maxval)) good enough in c?
firstly i got tle, then optimize it and changed to printf and got ac in pretest
Any ideas for C? Problem was intersting, but a litle more difficult than standard for "C"(Div 2).
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).
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
http://mirror.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.
thank u, but now TLE :P how to get rid of that?
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://mirror.codeforces.com/contest/842/submission/29931449
Turns out you are making O(divisors * n) modulo operations and modulo is really costly on codeforces if you use long long.
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?
You can change the frequency of divisors running through the list of divisors as in my solution: http://mirror.codeforces.com/contest/842/submission/29885607
You 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://mirror.codeforces.com/blog/entry/54120?#comment-382225
ok, this is getting weird!
why am i getting TLE now? -_- 29931793
As you said, the way you coded is too close to TLE :/
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. :)
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.
There are atmost root(n) divisors of n??Not Really !!
Divisors for 12 : 1, 2, 3, 4, 6, 12
root(12) -> 3.46
I meant complexity wise , if you're talking constants 2*root(n)
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
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
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.
So was I, and that is the reason why I submitted :D
According to the execution time, the sizes shouldn't exceed log(n) per set.
Thank you all)
Good thing we have the comments or else there would be no other way to ask questions during the contest.
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.
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://mirror.codeforces.com/contest/842/submission/29896449
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
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.
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.
How long do you have you wait to submit for practice? Is it once system testing is done?
my reaction when a solution strikes me during the last 5 minutes
I want someone saw! http://mirror.codeforces.com/contest/842/submission/29888162
ABC
What happened to rating change predictor? I am unable to see it.
https://cf-predictor-frontend.herokuapp.com/contestSelector.jsp
It's takes some time to load rating change, probably you should wait few more seconds.
Very bad, that there is no explanation to sample testcases. I couldn't understand problem E for 10 minutes.
Is it only my problem, or show unofficial button changes randomly when refreshing.
happened for me.
yeah just keeps changing
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.
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
Can you give a link probably to SPBGU?
Go to the training tab Choose the complexity of the 2 stars Find the last workout on this list
Do I miss something?
http://mirror.codeforces.com/gym/100166
He's talking about SPb SU trains.
How to solve about D ?
Is python so slow? Couldn't even perform 10^7 operations in 2 seconds!
Link
|
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 .
Input First string contains five integer numbers l, r, x, y, k (1 ≤ l ≤ r ≤ 107, 1 ≤ x ≤ y ≤ 107, 1 ≤ k ≤ 107).
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?
look 1e7 * log(1e7) * const > 2e9, so you can get tl
oh. got it. but why MLE here? what's the reason behind MLE?
Sorry i read TLE, for MLE the same 1e7 * long long > 70 MB and map his big constant
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.
and math with 1 line also wrong...
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..!
Link
Try 5 5 2 3 2, this should be NO. Your solution says YES.
Thanks..that was the missing case..!
1) Где разбор? 2) Объясните кто-то как решать С. Я так понял там ДП.
Сделаем обход графа в глубину из корня дерева. При обработке вершины будем считать для нее ответ.
1) Пусть мы НЕ будем занулять текущую вершину. Тогда ответом является один из делителей числа в этой вершине. Будем перебирать делители до корня. Теперь необходимо проверить, что данный делитель подходит как ответ. Он подходит, если все предки текущей вершины кроме одного делятся на этот делитель. Чтобы быстро это проверять, заведем глобальный массив, в котором будем хранить сколько на текущий момент вершин делится на это число. То есть в начале дфса при переборе делителей делаем +1, а при выходе из вершины -1. 2) Если мы хотим занулить это число, то ответ — НОД всех предков текущей вершины ( можно просто передавать как параметр в дфсе)
Ответ для вершины — максимум из 2ух случаев
Спасибо за решение. Можете подсказать, почему не работает следующая динамика:
dp[v][0/1][0/1] -- ответ в вершине v, при условии что мы меняем/не меняем данную вершину и нам можно/нельзя менять предков (dp[v][1][1] не используем)
dp[v][0][0] = gcd(a[v], dp[par[v]][0][0])
dp[v][1][0] = dp[par[v]][0][0]
dp[v][0][1] = max(gcd(a[v], dp[par[v]][1][0]), gcd(a[v], dp[par[v]][0][1])
У меня чувство, что дело в максимуме, но я не могу придумать тест, на котором это ломается.
Попробуйте такое:
7 35 5 35 7 35 5 7 1 2 2 3 3 4 4 5 5 6 6 7
Ответ: 35 35 35 7 7 5 1
Спасибо! Сломалось:)
Why can't we see the testcases?
When will the rating be updated?
Помогите, пожалуйста!
Подскажите, что я делаю не так в задаче A? Вот моя программа: http://mirror.codeforces.com/contest/842/submission/29897053. Подскажите, пожалуйста, тест 8.
My solution for C keeps failing for pretest 4, does anybody have any idea about what that case may be?
Try this:
7 35 5 35 7 35 5 7 1 2 2 3 3 4 4 5 5 6 6 7
answer: 35 35 35 7 7 5 1
works fine. Link
try this:
8 4 8 7 3 2 4 10 1 1 2 1 3 2 4 4 5 3 6 3 7 7 8
answer: 4 8 7 4 2 4 2 1
Value of the root node can be changed to 0 in computing gcd for any of the children nodes.
Help me, please!
Tell me, what I'm doing wrong in problem A? Here is my program: http://mirror.codeforces.com/contest/842/submission/29897053. Please, tell me testcase 8 if you can.
you reversed ranges, we have b*k =a you checked k*a=b
Thank you very much!!!
It looks like in testcases 1-7 k = 1... It's very sad...
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.
I'm sorry, I can't (same problems) and this is the reason i can't post editorial
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:
Now I am still trying to hack other solutions...
UPD: I give up and dicide to go sleeping.
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.
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.
I knew that my code would fail before systest so I'm wondering why my code passed.
Can you see the mistake in this picture? ._.
rating--
if new_color != prev_color: print prev_colorStill a Newbie :(
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://mirror.codeforces.com/contest/842/submission/29874288
You have long i and k. So i * k overflows before getting assigned to val.
nice contest with fast testing and rating update, thank you
Not fair if you're holding a contest, with a bug, Not allowing test cases to be seen. How am i able to upsolve?
Can't figure out the mistake in A. Could someone please provide a test case, thanks.
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.
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
Even this passed the pretests,very weak test cases.
Am i wrong? I see no problem in this code
There's no i in the if statement.
???
Check for loop carefully There is no index i inside the loop.
Oh i see it. But was it accepted? If it hadn't
passedbeen accepted then the test cases wouldn't be weakNo it was not accepted but it passed the pretests.
I would have helped you find this bug if you were in my room =)
By the way, does anyone see the problem with this solution? (Doesn't pass test 26: 29901876)
same problem as most hacked solutions, try this test 5 5 1 10 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 =)
I am a simple man, I see a naive solution that will pass the constraints, I implement it :D
http://mirror.codeforces.com/blog/entry/54120?#comment-382174
Hmm..
Now I'm confused. What's the difference between my solution and that one?
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
Why can't we see the test cases?
Кажется, здесь необходимо в сотый раз напомнить, что не стоит использовать питон для тяжелых операций :)
Can anyone write shorter solution to A than this?
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?
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.
when is the editorial going to release.
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!
Sorry to say,I can't totally understand the statement in the beginning until the announcement.But the problems are nice.
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?
Your solution will fail for tests some thing like this:
Answer should be8 8 1. But I think your code will output8 8 9For 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.
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.
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.
Does anyone know what is test 6 in problem D, why am I keep WA on test 6?
My submission: http://mirror.codeforces.com/contest/842/submission/29896373
insert into the Trie unique values only
I was such an idiot in this contest. Thank you very much. I now realized my mistakes!
What I get for underestimating the slowness of Ruby...
Разбор будет? Все ждут его...
Why Memory limit exceeded on test 43 in Problem A(Kirill And The Game) My code Can someone please help?
You don't need to convert those
rangeobjects tolist.And there is about
10 ** 7actions in your solution. Python is just not so fast for doing this (but you could try PyPy).is there no editorial??
Where is the editorial?
When will the editorial be added?
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 :) )
Look at point 3 here: http://mirror.codeforces.com/blog/entry/456.
Every minute after the start of the contest, each of the problems lose 0.4% of their base score value per minute passed.
Because here is time-penalty system. Task's cost decreases every minute.
29910536 Can somebody tell me why I get a RTE in test case 6 in DIV2 C?
Your
Earray is of sizeNwhile it should be of size2 * N.Thanks! So much help!
I wonder for problem D,if I have a trie with reversed bitset of every element(for example,3 will be 11 but 4 will be 001),how can I get the mex number from this trie in less than O(n)? Or tell me my solution is not correct at all...QAQ
You can do it with trie quite easily. If there was no update queries, you need to go to 0 subtree if it isn't full, and 1 subtree otherwise. You can just maintain inv array, so that you need to go to inv[i] first. Here's my code.
Oh...I understood your great solution(My English is bad...) (I realized reversed bitset to inserted is not meaningful...) Thank you very much ><
When do you have any clothes?
Разбор будет?
Why cant i see the test cases of problem on which i am getting WA??
Will there be editorial for this round?
For the trie solution to problem D, I got WA test 45. Then, after I changed the initial index in the trie from 0 to 1, it magically ACs. Why is that?
Submissions for comparison:
29917934 — WA 54
29918066 — AC
Will there be an editorial?
http://mirror.codeforces.com/blog/entry/54179
Which data structure do I need to study for solving problem D of DIV2?
trie
How to apply trie in this question? I tried to think about it but could not find any way. Please guide me. Thank you.
All the numbers can be presented in binary form as words with length 20 (220 > 3·105). So we can build trie (with edges 0 and 1) on these words and we can calculate weight of each vertex (amount of words that use this vertex)
We will add in trie only unique numbers
To find mex on trie we have to find the least number that is not in trie. So if we want to use any edge we need to understand if next vertex is full (all the numbers are written there). For this we calculated a size for each vertex. If is is equal to 2i (where i is a number of bit which is presented with this vertex) than vertex is full and we have to use another one.
Algorithm to find mex if array doesn't change is quite easy: while we can use edge 0 we use it, else we add 2i to answer and use edge 1
If array changes with number p than we need to present it to binary form. For example, p = 100010101010. It means that next time in levels 1, 3, 5, 7, 11 we will have to choose edge 1 instead of edge 0 firstly (because xor has changed edges on these levels). If we cannot do it, we use edge 0 and add 2i to answer
But if next time we will have p = 1010, than we will "swap" edges only in levels 5, 7, 11. So for each bit we calculate how many time it was changed. And if it was changed odd times than we swap edges on this level
Sorry for my bad English
Here is my code: 29929754