Hello everybody!
I'm glad to invite you to Codeforces Round #511 which will take place on 21.09.2018 17:35 (Московское время).
There will be 7 different problems in total, and 5 problems in each division. You will be given 2 hours to solve them.
The problems are prepared by me (ditoly), FallDream and ACMLCZH.
Thanks to 300iq who helps a lot in the round coordination, vintage_Vlad_Makeev, V--o_o--V, demon1999, isaf27, cyand1317 for problem testing and MikeMirzayanov for the platform.
This is my first Codeforces round. Hope you can enjoy it. Good luck!
UPD: The scoring contribution:
Div.1 : 750 — 1000 — 1500 — 2000 — 2500
Div.2 : 500 — 1000 — 1750 — 2000 — 2500
UPD2: Congratulations to the winners!
Div. 1 :
Div. 2 :
UPD3: The editorial is published. There are many things about problem-setting in it. Do not miss it.
Is it as hard as IOI?
It will be as easy as IOI
A red problemsetter round, nice!
Mathforces?
I hope I will come to Expert after this contest :3
Yet Another Chinese Round. :P
Sounds good!
I thought FallDream had retired :p
It's really a big pity :(
[deleted].
I have just become CM in Edu Round 51. Can I participate in this div.2 round as a official participant? (I knew that if there are div.1 and div.2 contests at the same time, I can only participate in div 1). I registered div.2 before the update rating of Edu Round 51.
AFAIK people who registered for div2 in advance and then got promoted will get unregistered by the system sometime before the round starts.
Aren't Candidate Masters div2-div1, as it changed recently? I can't register for div2 contest
You can register for a div 2 round if there is only one div-2 of this round. Current round has 2 divisions separately.
I bet there will be a 10 minutes delay
Bet. There won't.
Good luck and have fun with the round!!!!!!!!!111111111
Upd. I mean, enjoy round #111111111
What if a gray guy say this?!
This comment is hidden... this will appear on his comment
Don't be graycist
I didn't see that coming.
Good luck and happy Mid-Autumn Festival!
i'm coming expert , i wish i will not carry when can't solve B in contest and back to pupil xD
Update : Top 10 will be awarded a mooncake as a gift from Codeforces for Mid-Autumn Festival :D
Let's see what this CP thing is about. I've heard about it from some techs at the studio, so I thought "Hey! It'll be a nice distraction from acting", and here I am.
Oh, by the way, if you're near a cinema, go check out La Obra Maestra, a wonderful film with my personal friend (and great actor) Luis Brandoni.
https://i.postimg.cc/ZB9rzZ6n/Screenshot_from_2018-09-21_17-13-29.png
https://i.postimg.cc/sQt5V8Jc/Screenshot_from_2018-09-21_17-13-57.png
these are screenshots of registered users. Very strange utkarsh_7330 has registered twice. How could this happen?
MikeMirzayanov ?
I also registered twice... see here
I hope the problem statements will be just like this blog: short and sweet :)
However, they're short, and with "love" (between little C and 3).
What do u guys do in the ~5 min before every contest?? I just keep refreshing and browsing CF.. I wonder if it's just me ... ? :D
Reading comments :D
Yeah looking forward to a nice set of problems.
A red problem setter. Wow !!
Best of luck for your first round as a problem setter ditoly
Why is the rating predictor not working?
UPD: It's working now
IDEJNIJ KONTEST, VERY INDEJNIY
why am i so bad lol
another mathforces or digitforces?
Looks like I'm gonna get hacked so hard :) . Please test cases be strong.
Больше математики!!! Больше цифр!!!
that moment when you waste one hour trying to find what's the mistake in your algorithm and in the end you just wrote one letter by mistake
edit:I'm gonna get Tle for a stupid '}' I'm out :)
C gets hacked... Meanwhile this!
for what reason was div2c getting hacked ?
Bugs
The hell is the solution for problem C ?
Strip the gcd off all the numbers. Now just find the largest set of numbers with gcd > 1. You can do this by looking for numbers divisible by a common prime factor.
read 4 first problems Mathforces confirmed.
Anybody knows test 8 problem D(of course div2)??
I think that is 2 7.
What's the answer?? 12?? So why my code gets WA??
IMO 2019?
Every time a chinese guy prepares a contest, I say to myself this chinese contest won't be as bad as the last one. And yet here we are!
Problem D div2 / B div1 was a very bad problem for me, what is the point of problems with no ideas but just conditions ?
This problem included the idea, to figure out the conditions.
constraints of C is too strict. :(
no
I was unable to think a good solution... Can you tell me what is complexity of the expected solution?
Here is my solution. The idea is to find the cheapest cost for making the gcd a prime factor p greater, for each prime p ≤ amax. This is done by dividing all numbers by the initial gcd, and then counting how many numbers are missing a factor p.
Factorization of the numbers can be done by precalculating an O(amax) prime sieve to find the smallest prime factor (SPF) of every number ≤ 1.5 * 107. With SPF precalculated it is possible to factorize numbers in
.
All in all it has the time complexity
.
I thought I registered for Codeforces contest, not Project Euler...
Can anyone tell me what is test case 8 for Problem D (Div-2) ?
Try 3 7 and 2 7
How to solve Div2C and Div2D?
GCD is min prime factorization for all number example : gcd (9 , 4 , 2) = 2^min(2 , 1 , 0) * 3^(min(2 , 0 , 0)) * 5 ^min(0 , 0 , 0) .. etc so to make gcd bigger you need to loop over every prime factorization and the answer for this prime frac is the number of number that not have this prime you can find it by find every prime frac for all number and add it for freq array then the ans for prime will we just in case n != freq[prime fac] n — freq[prime fac] — ( number of one ) ans = min for all frac don't forget to handle this case 1 2 3 4 => 1 remove (1) 3 3 3 9 9 => 3 remove (3 , 3,3) my solution https://ideone.com/zHLllz i wish it will not get WA at main test and sorry for my bad english
It's a pity that i can not hack myself.
Look around, life has many interesting problems. But dude, you chose math :D
Good contest by the way.
how do you solve B?
nvm, i see it is all casework like i expected, too bad
can't believe i wasted an hour and a half on that and still got it wrong LOL
There is no need to check all the tricky cases by hand. You can write bruteforce and find all of them.
I don't understand how you get all tricky cases by bruteforce. Can you explain briefly? (maybe with code?)
Recursive backtracking should be enough for very small grids.
Alternatively, you can also find the max matching of the bipartite graph where each vertex is a square of the grid and two squares are connected iff their Manhattan Distance is 3 via Max Flow or any other matching algorithm.
just a bunch of if conditions
What is the better way of training for solving these problems?
Also, what philosophy does one need to follow when solving them? Doing a bruteforce solution, then trying a bunch of test cases until one finds a pattern?
i am really not the good person to ask :V but anyway if i didn't find any reasonable solution to a problem i make a bruteforce solution ans observe the pattern if there is one
It seems the pretests of problem div2.C are weak...
You are scaring me:|
Very, very weak
"that of all integers" Nah..
And just like that, you wasted 2 hours of my life!
In div1C, does the following hold?
We can divide the kingdom into sections with each having sum X, iff sum(tree)%X = 0, and exactly sum(tree) / X subtrees T have sum(T)%x = 0. The division can be done by cutting edges to the parent from such nodes.
I couldn't find a counterexample, but unfortunately didn't have time to code either.
Edit: Proof:
Clearly we need X divides sum(tree), and that there exist at least sum(tree) / X such subtrees, for X to work. Now assume that there are K such subtrees. Cut their parents. Now we have K different parts (one of the subtrees was our root), each of them has sum divisible by X, and of course holds
. If K > sum(tree) / X, we have a contradiction. If 
, we have a contradiction. Therefore the sum of every part is X, and we're done.
I've also thought of it, but I couldn't see a way to use this.
I think if that holds, you can solve the problem pretty easily.
We use a few facts here:
sum(tree) has at most like 1e5 divisors
If X is a possible number, and Y is a possible number, and X % Y = 0, then we can first divide into X, then into Y. This follows from the way we select the nodes whose parents we cut.
The way to cut the parents is unique for any value X
It's even more easier. Let number x be "good" if you can divide T with subtree size sum(T) / x. dp[i] = 0 if i is not good,
otherwise. Time complexity is 
using harmonic sums.
Checking if
is good can be done with similar way in 
, after you know gcd(sum(subtree), sum(T))
Doesn't doing the harmonic sum naively with something like unordered maps give you complexity O(sum(tree) log(sum(tree))? How do you get it to n log n?
The number in form of sum(T) / i for
are only relevant, so you don't need unordered map, just an array of size N.
Ohh okay, I get it now. Nice solution!
Yes, your statement holds.
The idea is probably correct, I have used it before on another problem. I couldn't really do anything with it though.
Div2C Converting all ll divisions to int divisions drastically changed the running time... How does it even affect though?
https://stackoverflow.com/questions/39779880/c-int-vs-long-long-in-64-bit-machine
Fair enough... Never considered memory level optimizations.
What happens if I resubmit a solution to a problem which I have already submitted a solution which passed the pretests?
The first solution which passes the system tests is considered and any WA before that will be an unsuccessful submission as usual.
That is not accured, the system ignore all submmits but the last one, you shoould read Skipped in the previos pretests passed.
What will be the approach for problem Div2 C (Enlarge GCD). I had TLE in 8th pretest.
Did something like sieve. Only marginally avoided TLE. Wonder what will happen after systest.
I used sieve and then calculated the minimum power of each prime in each number so as to evaluate the minimum number of terms to delete to get an enlarged GCD. How did you solve @from_bd_with_depression??
Instead of calculating power, I just checked how many numbers are divisible by for all numbers > gcd
Yes I also had the issue that if I use all primes upto MAX=1.5x10^7, then I got TLE on test case 8, whereas if I use numbers upto sqrt(MAX), then the pretests passed (but the solution is wrong, you have to take all primes upto MAX). Why do they keep such tight time limits?
Use the O(NloglogN) sieve. I used it and ran C in merely 0.5 seconds. NlogN sieve will obviously be tight.
I used sieve of eratosthenes, its complexity is nloglogn.
Same as me then. How on earth did you TLE that out. I ran that sieve on custom test and it resulted in a mere 138ms EDIT: Nvm I just saw your complexity. Obviously you will TLE with that O(N * max(A)) algorithm, even with 5 seconds
Okay I saw the editorial. I get the difference now. Thank you so much for the suggestions DrumpfTheGodEmperor :)
Sorry, but it was one the worst contest I've ever seen (I saw rounds of GreenGrape)
I used custom test for my E before submitting it. It ran more than 10s when n = 21 on custom test. Then I spent about 30 min on how to squeeze my code in to TL, but failed. After that, I decided to submit one similar to my first code and it got PP in 499ms. Anyone knows what had just happened to me?
From what you said, looks like you lost 300 pts, 30 min * 10 pts per minute and you got 9'th instead of 3'rd. That's what happened to you.
I was using this as generator to hack Div2 C:
https://ideone.com/6yWmn9
It kept giving me an invalid input error with the following:
"Validator 'validator.exe' returns exit code 3 [FAIL Expected EOLN (stdin, line 2)]"
Can someone tell me how to fix it?
In my memory, you should give newline as endl(instead of '\n') in hack data generator code.
I use printf("\n") without problem. The problem is that it should have a "return 0;"
In this case cf should give a better error :/ Is there any way to test the generator now?
Oh wow, I didn't know there was any difference between the two. Is there anyway I can test if replacing "\n" with endl would fix the generator now?
You wrote
if(i!=n);so it generates an extra space at the end of the second line.I don't get it? That was written specifically to avoid printing an extra space at the end of the last (nth) element.
Oh wow, just saw it, that was pretty stupid lol. Thank you guys for pointing it out!
DIV. 1 B is the kind of problem that when you submit it you just pray you didn't forget any if -_-
Pretests of Div2 C was weak I think. I see some codes(including mine) which only calculates primes to
sqrt(1.5*10^7), and they all passed. But the case above makes them broken:These codes gives answer as "-1", while it is "1".
Hope to see a round with better constraints, and better pretests, of course.
what is wrong in this submission(DIV 2 B).43208324
Test 3 4 0 5 You are actually calculating max distance from origin rather than max of sum of x+y because since two sides are equal the equation of third side is of the form x/a+y/a=1 we have to find a.
All you had to do was print the max possible sum of coordinates.
How to solve Div2 D?
Really strange thing happened...
When I submitted A, it said I had submitted the same code before:
Then I tried to modify my code, and add some annotations, but it's no use. I tried B, still the same.
I don't know why but I came up with the idea of using VPN, and I found myself not registered yet, but I remembered that I had registered. However, I registered again, and I was able to submit my codes.
Later, I turned off the VPN, and I could not submit my codes again. I turned it on and I could submit again.
The most incredible thing is, I found that I had registered twice..
I just wanna know what happened?
Codeforces got hacked after System Tests. Mike should find the bug of his code.
JK
I am confusing...
I tried to hack the problem, but there no success.
Please see code link, this solution should be time limit exceeded, but codeforces system said everything ok and I got wrong hack attempt with this test
1 10^9 10^9. I tested it in my local computer, the code isn't working in IDE.How can I understand?
There were many cases source code in C++ works properly with complexity of O(n), when n ≤ 109.
Try with 105 points instead.
Is it just me or do you also think this one for Div.1 was extra hard?
You can usually anticipate super hard contest with Chinese authors. I especially like problem E, but my bit mojo is weak.
I have only read A, B and C and solved nothing during the contest anyway. I think I came up with a solution for B during the contest and finished writing it a few minutes after the contest finished but I can only check after the system testing.
Anyway, (if I were to finish and submit 'B' in time) I would probably only lose rating for the single problem solved few minutes before the finish.
For C, just divide the array elements by initial GCD, and then https://www.geeksforgeeks.org/largest-subsequence-gcd-greater-1/
This method is the most intuitive IMO, thanks for this short solution :)
How to solve Div2-C?
For C just find gcd and then use sieve to find numbers of multiples in given array for every number above this gcd. Now the maximum number of multiples among these numbers will remove minimum integers from array. However due to strict time limit we cant use this algo. So to optimize it we see that if we find number of multiples for a number then we dont need to check this for its multiples as number of their multiples will be less than or equal to this answer. this is my solution
Solved exactly div 1 E a few days back but didn't read it the whole contest. :)
Solution if anyone's interested: https://people.csail.mit.edu/rrw/presentations/subset-conv.pdf
Thanks, Bae
Div2C constraints aren't fair for Java users x)
Same solution in C++ passes in around ~600ms & around ~990ms in JAVA.
Java isn't fair for Java users
I got TL on test 15 in A :( isn't it too harsh to set n = 300000, MAX = 15000000 for A?
So many math problems... This contest is not friendly to me at all
This is not friendlyToMeContestForces.
I'm not good in Mathematics, so I used bipartite matching in div1B. It was terrible for me. :(
Div2C/Div1A should have had 1 more second time limit
After C — that memory in right corner
really you can define array of size 1.5 * 1e7 when i am define array with size 1e6 the codeblocks became slow, That's why I did not think about sieve and get TLE in case 10!!!
I'm the only one who solved the problem div2 B with Binary Search by answer? I dont understand solutions
You have to search the point further to the point (0,0) whit this point (x,y) we need to know which is the begining of the hipotenuse of the triangle that passes fot that point and this is (0,x+y) and the end is (x+y,0)
It's very simple, you need to cover all n points with an isosceles triangle that uses X and Y axis as sides, so you will use a line y = mx + b such that the points (0, x) and (x, 0) belong to it for any x.
We see that x = b and m = - 1, and also notice that the sides in the axis are the smallest ones from the triangle, so we only need to find b and it will be our answer.
Now, if we set an "order" to the points by using the b they would generate, we notice that the maximum b generated will cover all of the points, so that's what we do.
We compute the b by using
, that's why all do something like this:
My first thought was that too
Hey guys. This two guys cheated on problem C. Just check these two submissions. http://mirror.codeforces.com/contest/1047/submission/43207716 http://mirror.codeforces.com/contest/1047/submission/43197339 The first submission is really similar to the second
Codeforces before the update of ratings search for similary solutions and if codeforces find some solutions similary all the participants except the first participant who uploaded the solution are disqualified from the contest
Hey guys, I really want to improve my problem solving skills. During the competition, I had no idea what to do for Div 1B/Div 2D and gave up.
I noticed a lot of accepted solutions were if-else statements. Could I kindly ask for advice on strategies to reach these solutions?
Solve it for n, m ≤ 20 with max flow, then make a spreadsheet of all these values and recognize the pattern.
Solution
Or just use pen and paper — thought it might be a little slower.
Hey, thanks for your reply! Yeah, I was trying to do that, but couldn't see any patterns... I also stopped solving it by hand at around N = 4, M = 6 -ish.
Could I ask how many examples you did by hand?
Awesome, thanks so much Ben! I guess I spent too much time trying to think of insights instead of analyzing the patterns haha
If you don't want to analyze the pattern, you could make an educated guess that since 1 × 6 grid can be completely covered so it is likely that for larger grids you can delete 6 × m or n × 6 blocks from it and the answer will remain the same. Thus, you can keep subtracting n and m by 6 until you reach a small enough value where you can solve it via max flow.
Hey zscoder! Thanks so much for that advice, that really makes a lot of sense to me!
I got your point. But missing few things. Can you please tell me, what are source node and target node for Max Flow execution? As well as, what will be the flows on edges?
Is there anyone solve problem C with java ?
http://mirror.codeforces.com/contest/1047/submission/43209921
Just barely x)
does anyone have the test case #44 of Div1 C/ Div2 A. I got WA on this test :((
Despite losing rating again, well, I can proudly say that I've succeeded in achieving something (maybe) no Codeforces users have done before :D
(Look at the execution time of my C solution, it even overrides time limit LOL)
--Del--
Yeah, you feel proud of copy-pasting GeeksforGeeks's code LOL
--Del--
you know a contest is bad when 100 points=2000 position difference
The constraints for C are plain bullshit. Spoiled the contest for me.
You created the sieve needlessly large (MAXN = 2e7+5). But I agree, the time limit should have definitely been 2s.
The time constraint was the only thing that made this problem interesting. With some optimization in sieve we can easily pass this problem in 1s.
Does copy-pasting linear sieve really make problem more interesting? Not sure about it
I didn't even try to optimize my sieve, still pass
A had a faulty description, which I needed a clarification to solve. and I didn't liked problem B.
However, after then the problems were interesting (especially D). Too bad my optimal strategy was just bashing hacks.
Thank you for the great problems!
Screencast of the round(div2). https://youtu.be/NMyhboAp0DI problems solved: A, B, C
Funny fact, My friend place at standing and mine difference is 3 our score differs by 3 and he accepted C 3 minutes after me I guess Little C really loves 3 :)
http://mirror.codeforces.com/contest/1047/submission/43216650
http://mirror.codeforces.com/contest/1047/submission/43220019
Find the difference.
There is no.
missed many test cases in div2C... Done :(
I dont know about the test but i read your code i know what the problem is,
When you want find the div you go till 320 which isnt the square root of 15e6 clearly you’re trying pass the timelimit with a solution that is completely time
checking with the 1st 320 primes is enough to find the factors of a number <=10^7.. i guess.. my code passed with just 320 primes..
Hi,
My submission, abhisheksince97/43197368 has been flagged for coinciding with solutions vbbvaddd79506/43196786, priyasen54/43197486, fibo1/43201480, gennadykorotkevichaz/43202067, cpp19/43202087, milanmas/43202887.
I can prove that the solution is mine and the others have copied it. You can open all my recent past submissions, I have used the same template for .cpp file as I have done in this one. The rest have clearly copied.
Also, the solution that I have written is available on geeksforgeeks (https://www.geeksforgeeks.org/largest-subsequence-gcd-greater-1/). This could also be the reason for the match.
I was really foolish and naive to have tested my code on ideone. Please verify that I am the true author of this solution and please let this contest be rated for me as I put a lot of effort into it. I have never done such a mistake before and wont do it ever again.
you can't copy/past code from geeksforgeeks or some other site, am sure many users did the same and got skipped like you.
"If you have conclusive evidence that a coincidence has occurred due to the use of a common source published before the competition, write a comment to post about the round with all the details." This is the message that I got from Codeforeces System. Above, I have provided a conclusive evidence that the coincidence has occurred because of a similar problem on geeksforgeeks. If you put a little bit of effort, you will be able to see that the exact problem on geeksforgeeks is different from the question asked in the Round. I used the approach taken by the geeksforgeeks solution.
Can we use code from Emaxx?
you can't copy/past code from geeksforgeeks or some other site, am sure many users did the same and got skipped like you.Actually, you can do that as long as that code is published before contest and it's not copyrighted.You are right, its my mistake, actually every thing is clear here
However, anyone should try to solve the problem by his eforts, goggling the solution wont help anyone improve.
Where is editorial?:c
I think these guys cheated and got away with it.
http://mirror.codeforces.com/contest/1047/submission/43211821
http://mirror.codeforces.com/contest/1047/submission/43209970
almost same?! coincidence? i don't think so
Can someone help me with my solution. I am not able to figure why it failed in system tests. solution
Around 180 soln of C/D failed in top 380.
WTF, wasn't packing product (E) really never asked before?
Old and kind div2 contests, where is possible to come up with only two first problems... Mmm, i have missed it too long
Little C is so cute(qwq)...But this round looks like a math round and it's a little difficult
I'm the one who suggested raising the constraints of 2C/1A. The original version had 1e7, and a simpler
solution exists (see code below) which the author doesn't intend to accept. Thus the final version had 1.5e7 with a higher TL.
Though I wouldn't consider it good to let
make a difference, I did nothing afterwards in attempts to improve the situation. If the current limits ever causes unintended FSTs, I'm the de facto person to bring about all these.
Some may say the problems don't fit a CF round well, but I've spend 4+ hours on the problems only as a tester (not to say authors and coordinators) and I don't feel it's been wasted. Maybe my time isn't as valuable as yours, but isn't it nice just to have some intellectual challenges?
Round #111111111 draws the curtain on the good old 9-bit days. Wish you can get your affected rating (if any) back in the new era! :)
Thank you for the simplify of the problem discription!!! It is easy to understand it! A nice math round!(Even though the pretest C is weak :D)
I just finished coding div1-C but the queue is too long and it doesn't seem to progress...
Div2 C, I think the number of the remaining integers must be two at least because gcd needs two or more integers. (https://en.wikipedia.org/wiki/Greatest_common_divisor) So, I think the answer of pretest 4 is not 1, but -1. Is this wrong?
https://www.quora.com/What-is-the-greatest-common-divisor-of-a-single-number-Is-it-1-or-the-number-itself
Thanks, I understand.
for D(div2)why(n=7;m=1)answer is 6?
1 2 3 1 2 3 x
MikeMirzayanov, why is the queue so long, when will the submissions start getting judged ? Please look into the matter at the earliest :(
So where is the editorial?
I think this round is not a good round.ABCD is easy and E is hard.If you code very fast,you'll get a satisfying rank.In fact,this round has little discrimination.
ABC are easy simulations.D is a easy math problem.But I'm so young that I don't finished C.
On bzoj?
I read the question wrong.My bad.Sorry.
Где разборто?
Waiting for Editorial ! Can anyone help with Div 2 Problem C ?
You can get the factorization of all numbers in nearly linear time using Pritchard's sieve. Then you choose the second maximum among all the prime divisors and n — secondmax is the answer.
Initially i didnt know what to do but finally i read this
https://www.geeksforgeeks.org/largest-subsequence-gcd-greater-1/
this is similar to div 2 c give it a try i hope u wil be able to solve c after that..
thankyou
Many thanks! It's was of great help.
From the past contests we all apreciate codeforces for organize frequent contests and fast editorials .I think they misplaced their track but right now they are on their track so guys editorial will be in 2-3 days...hullaaaaaa
It's published now.
How to solve Div1 C / Div2 E ??
Low memory solution for Div.2C / Div.1A
http://mirror.codeforces.com/contest/1047/submission/43263896
Btw, maybe you guys can add some more optimizations for this solution(except custom i/o), i'd appreciate it.