Hi everyone. I'm glad to announce that the Codeforces Round 520 (Div. 2) will be held on 14.11.2018 18:35 (Московское время).
The round will be rated for Div 2 participants (whose ratings are lower than 2100). However, all the other participants can compete as well, without worrying about ratings being changed.
You will be given 2 hours to solve 6 problems. It's better to read all the problems. The scoring distribution will be announced soon before the contest starts.
All the problems were prepared by myself, with some help from my friend GiraffeCoder. I want to thank cdkrot for coordinating me in preparing the problems, vintage_Vlad_Makeev, isaf27, demon1999 and Arpa for testing my solutions. I also want to thank csacademy for their graph editor tool. You can check it out at this link.
This is the first round I propose. I put a lot of work into it so I hope that you will enjoy it (smiley face).
Wish you do your best and get a high rating!
Update 1: If you want to discuss about the problems after the contest, here is the link to the CP Community on Discord. Please make sure that you don't give the solutions to other participants during the contest.
Update 2: The score distribution will be the standard one: 500 1000 1500 2000 2500 3000.
Update 3: Congrats to the winner
Official participants:
Unofficial participants:
Tutorial UPDATED
You forgot to thank MikeMirzayanov!!! for awesome codeforces and polygon platform.
Why vintage_Vlad_Makeev became blue?
Hi 300iq — 17iq + 2000iq — 200iq * 10iq
I think he was faking his red all this time.
Because when they make post he was blue, but now he is cyan.
Maybe he let someone rent his account.
Because he wants to get vertical rating graph. Positive or negative is just direction, we only care magnitude.
He will definitely break this (Maximum rating change in CF history) record.
I asked his friends and he wants his team on the list in front of the icpc with nicknames and ratings to look funny. A team of two red and blue.
I think you should hope that none of your problems or your checkers would have had mistake instead.
-8 your favorite number amiterite?
Happy to see another round from Vietnamese.
In China,520 means "I love you."
I prefer high rating :)
But my girlfriend and I just broke up,I am so sad that I don't know how to do it.
Sorry about hearing that bad news.
振作起来，哥们。
Hi warriors,I'm back;
Oh! So the prophecy was true!
Why gritukan became blue?
I asked his friends and he wants his team on the list in front of the icpc with nicknames and ratings to look funny. A team of two red and blue.
Isnt it unrated??
It was at this moment that i know i fucked up
Can someone get rid of fake accounts in places 3-8. It's obviously just one or two people modifying their codes and submitting again. JATC
now he is even first place, lol
If there is any cheating those accounts will be disqualified probably :)
I think there's some mistake happening here. Only 3 of those are cheaters, but coffee_chicken is not, but they all seem to be banned simultaneously. Is there any way to fix this?
I'm not sure since it's the decision of the admins.
They all got banned. Thanks, admins!
What's wrong with pretest 9 of Problem B? Anyone with a clue...
Probably something like 93184 which is 1024*7*13. You may be having overflow issues.
How to solve E????? I tried Mo's algorithm + LCA the left/rightmost but got TLE every single time. I think the set is the main problem...
I think you just need to have the lca of (i and i+1) and (i and i+2) pre-calculated for all i and then do with segment tree.
Oh, it was that simple!!!!! LOL!!!!!! Thanks.
I couldn't implement it as I forgot to make a simple observation in D but I think that should pass.
My solution is like this: say that dfn[x] represent the order of vertex v when you do dfs, then the LCA of a set of vertices is just the LCA of the vertices with the lowest dfn and the highest dfn, so we can use a segment tree to maintain the vertex with the lowest dfn, second lowest dfn, highest dfn and second highest dfn, to answer a query, just do case analysis (3 cases here, erase the vertex with the lowest dfn, erase the vertex with the highest dfn, or neither). The solution is
. You can do the LCA part using whatever technique, both binary lifting and euler sequence+RMQ would do.
What hacks are there? (for any problem)
Hacks for B:
18 (ans=6 2)
144 (ans=6 3)
What is case 9? Hack is too far away
Try this:
24 (ans=6 3)
Does this work for E?
Find maximal L that lca(l, L) != lca(l, r)
Find minimal R that lca(R, r) != lca(l, r)
If L + 1 == R — 1 and lca(lca(l, L), lca(R, r)) != lca(l, r) answer is L + 1.
Is this correct? I tried implementing the same but got WA on 6th test. https://ideone.com/kr0ZCY
D is too easy, innit? Or i will drop on full tests...
Just 10 more seconds :(
Is this not the correct formula for C?
(2^noOfOnesInLtoR-1)+((2^noOfOnesInLtoR-1)*noOfZerosInLtoR)
nope dude, try this test case 4 1 0001 1 4
Got my mistake. Thank you!! Instead of noOfZerosInLtoR it will be (2^noOfZerosInLtoR)-1.
I first thought so and got several WAs.
must be aware that after eatings ones, which were initially zeroes now have some values which even gets larger and larger eating those.
(2^noOfOnesInLtoR-1)+((2^noOfOnesInLtoR-1)*(2^noOfzerosInLtoR-1))
It's just
2^(num zeroes + num ones) - 2^(num zeroes). Other formulas are looking kind of complicated.All naruto characters are in the standings www
Я только одного не понял, а сегодняшнее соревнование было все-таки по программированию или по математике?
What is solution for D?
My solution was simply to find all factors of every number from 2 to n. Now for each number from 2 to n, sum up all factors except 1 and the number itself. Now add all of these sums and multiply by 4 to get the answer.
Build the graph where there's an edge between a and b with weight
if you can go from one to the other. Whenever you have an edge between a and b, you also have one from a to - b, so the degree of each vertex is even, and thus the graph is eulerian, and you can traverse every edge. So it suffices to find the sum of all of the edges, which is easy.
that was a great observation.
Suppose you have an integer i.You can always make a cycle of size 4 for every k which is less than n and divisible by i.For any k which is divisible by i,just add 4 * (k/i) to your ans.Suppose that i has p multiples <=n.So for i,add 4 * ((p * (p+1))/2 — 1) to your ans.(-1 because i can not form a cycle to itself).
Does this work for E? I did dfs to find time in for every node. Then for each query, used seg tree to find node with minimum and maximum time, say mini and maxi. Then I took a node from l to r which is neither the max nor the min time, say x. I found lca(mini, x) and lca(maxi, x) and reported the one with maximum level and removed the other one.
RIP my rate :)
anyone knows B pretest 3?
I think it's 10^6
meh it was a silly mistake I knew the solution idea but I done it terribly :( I should have just checked if the last sqrt equals prime factors multiplied to know if we should multiply or not
It's 256 or 64 I guess..
Problem F is simply this but with more cases.
I think the factor of the "semi-important" cities makes the problem significantly more interesting and hard.
anyone knows problem B test 32?
18
In problem A, it would have been better if constraint for n was upto 1000, because for n = 1000 answer would be 1000. Some people might have missed this test case. I have also printed 999 in my current solution.
exactly. I've got at least 3+ people in my room who've made this mistake. What was the reason for n being 100, I don't understand.
Well, you can't call it a "mistake" if it doesn't lead to an incorrect solution. I knew this, but since n < 100, I didn't bother putting that case.
Calling it a "mistake" was wrong actually. But n = 100 made it easier I think
Really? What a disgrace.
However this allows to handle less cases in the solutions, which is also not very bad
How is my system test B(submitted at ~45mins) still running on test 50? while many other people's submissions finished running.
https://codeforces.net/contest/1062/submission/45725683
ACCEPTED XD
Pretests for A were very weak.
I'm sorry this happens but it's seem too hard to cover all the cases in just a few tests. Too much tests and the server will die.
The problem A pretests are one of the top-10 pranks that went too far.
I was wondering in Problem E if i wanted to count the number of nodes instead of just printing one what would the solution be ?
I guess there can be only two nodes (at max) the ones with min start and max finish (dfs) times.
the case of x nodes being direct children to LCA or choosing a subtree the answer will be x not sure if this is just a corner case thou.
If x nodes are children to LCA, with x > 2, then u can never increase the answer right? by just performing one remove operation. So the count is zero.
i think he asks for the nodes when removed will result in the best answer so i think the answer will be all of them however, my question is does handling this assures that the answer for all other cases is <= 2.
I would consider the count to be x, since you can remove any of the children and it will be true that the "level of the project manager required is as large as possible."
it was hard for me. But in any case, thanks for the round and interesting problems.
It was really a prank with the problem "A Prank". Missed the last line :'(. Yet didn't get AC.
deleted
How can the fastest solution in Python be 171 ms for even shortest test (e.g. problem A. tc #1)? Status order by consumed time (choose language, e.g. Python 2, and status: acc). Seems it doesn't depend on which problem but all Pythons (2, 3, pypy-2-3) have >100ms to pass any test case. Strange.
Maybe it is to load the runtime environment, just like how java always eats 100ms start time.
But its first time I see ~170 ms (almost 1/6 of TL). If you look at much earlier contests this minimal time was usually faster, e.g. Contest #839
I get 247 rated! Thank you!!!!
Ye.
same here :(
I realized that after the contest is finished XD
Codefores is the best!!!
It seems that H.D.T and trungttt cheated during the contest. The codes are basicly the same but with random stuff added to hide it.
The common parts of code seem to originate from http://e-maxx.ru, which is allowed.
E-maxx has implementations for standard algorithms, not specific problems. It is clear that all the solutions are identical. And why are the solutions filled with var-=a, var+=a, then?
It is written that Tutorial is UPDATED. where is the editorial link?
here
Thanks