### ditoly's blog

By ditoly, history, 5 weeks ago, ,

Hello everybody!

I'm glad to invite you to Codeforces Round #511 which will take place on Sep/21/2018 17:35 (Moscow time).

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, gritukan, 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.

•
• +157
•

 » 5 weeks ago, # |   -79 Is it as hard as IOI?
•  » » 5 weeks ago, # ^ |   -43 It will be as easy as IOI
 » 5 weeks ago, # |   +43 A red problemsetter round, nice!
•  » » 5 weeks ago, # ^ |   +33 Mathforces?
 » 5 weeks ago, # |   -11 I hope I will come to Expert after this contest :3
 » 5 weeks ago, # |   +29 Yet Another Chinese Round. :PSounds good!
 » 5 weeks ago, # |   +1 I thought FallDream had retired :p
•  » » 5 weeks ago, # ^ |   +14 It's really a big pity :(
 » 5 weeks ago, # |   -39 Is It Unrated?
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   -8 No
 » 5 weeks ago, # |   +10 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.
•  » » 5 weeks ago, # ^ |   +2 AFAIK people who registered for div2 in advance and then got promoted will get unregistered by the system sometime before the round starts.
 » 5 weeks ago, # |   +1 Aren't Candidate Masters div2-div1, as it changed recently? I can't register for div2 contest
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   +6 You can register for a div 2 round if there is only one div-2 of this round. Current round has 2 divisions separately.
 » 5 weeks ago, # |   -12 I bet there will be a 10 minutes delay
•  » » 5 weeks ago, # ^ |   +1 Bet. There won't.
 » 5 weeks ago, # | ← Rev. 2 →   +26 Good luck and have fun with the round!!!!!!!!!111111111Upd. I mean, enjoy round #111111111
•  » » 5 weeks ago, # ^ |   +49 What if a gray guy say this?!
•  » » » 5 weeks ago, # ^ | ← Rev. 2 →   +14 This comment is hidden... this will appear on his comment
•  » » » 5 weeks ago, # ^ |   +21 Don't be graycist
•  » » » » 5 weeks ago, # ^ |   0 I didn't see that coming.
 » 5 weeks ago, # |   +4 Good luck and happy Mid-Autumn Festival!
 » 5 weeks ago, # |   0 i'm coming expert , i wish i will not carry when can't solve B in contest and back to pupil xD
 » 5 weeks ago, # |   +10 Update : Top 10 will be awarded a mooncake as a gift from Codeforces for Mid-Autumn Festival :D
 » 5 weeks ago, # |   -24 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.
 » 5 weeks ago, # |   -35 i wish you all to derank
 » 5 weeks ago, # | ← Rev. 2 →   0 https://i.postimg.cc/ZB9rzZ6n/Screenshot_from_2018-09-21_17-13-29.pnghttps://i.postimg.cc/sQt5V8Jc/Screenshot_from_2018-09-21_17-13-57.pngthese are screenshots of registered users. Very strange utkarsh_7330 has registered twice. How could this happen?
•  » » 5 weeks ago, # ^ |   0
•  » » 5 weeks ago, # ^ |   0 I also registered twice... see here
 » 5 weeks ago, # |   +6 I hope the problem statements will be just like this blog: short and sweet :)
•  » » 5 weeks ago, # ^ |   0 However, they're short, and with "love" (between little C and 3).
 » 5 weeks ago, # |   +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
•  » » 5 weeks ago, # ^ |   0 Reading commands :D
•  » » » 5 weeks ago, # ^ |   0 And replying to them :D
 » 5 weeks ago, # |   0 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
 » 5 weeks ago, # | ← Rev. 3 →   +7 Why is the rating predictor not working? UPD: It's working now
 » 5 weeks ago, # |   0 IDEJNIJ KONTEST, VERY INDEJNIY
 » 5 weeks ago, # |   +45 why am i so bad lol
 » 5 weeks ago, # |   +11 another mathforces or digitforces?
 » 5 weeks ago, # |   +1 Looks like I'm gonna get hacked so hard :) . Please test cases be strong.
 » 5 weeks ago, # | ← Rev. 2 →   -62 ahha this contest is just trash like im just the best programmer the world has ever known and the contest is so badly made. Test 8 on C is rigged and i assure you that , because im the best programmer the world has ever known.i have the best solution for C and still Im getting TLE TLE TLE TLE TLE but then again its those CIA ngers fault , not mine, because im the best programmer the world has ever known.
•  » » 5 weeks ago, # ^ |   -26 I possess divine intellect stop downvoting haters
 » 5 weeks ago, # | ← Rev. 2 →   0 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 mistakeedit:I'm gonna get Tle for a stupid '}' I'm out :)
 » 5 weeks ago, # | ← Rev. 2 →   +29 C gets hacked... Meanwhile this!
•  » » 5 weeks ago, # ^ |   0 for what reason was div2c getting hacked ?
•  » » » 5 weeks ago, # ^ |   +29 Bugs
 » 5 weeks ago, # |   +4 The hell is the solution for problem C ?
•  » » 5 weeks ago, # ^ |   0 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.
 » 5 weeks ago, # |   +5 read 4 first problems Mathforces confirmed.
 » 5 weeks ago, # |   0 Anybody knows test 8 problem D(of course div2)??
•  » » 5 weeks ago, # ^ |   +13 I think that is 2 7.
•  » » » 5 weeks ago, # ^ |   0 What's the answer?? 12?? So why my code gets WA??
 » 5 weeks ago, # |   +44 IMO 2019?
 » 5 weeks ago, # |   +27 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!
 » 5 weeks ago, # |   +36 Problem D div2 / B div1 was a very bad problem for me, what is the point of problems with no ideas but just conditions ?
•  » » 5 weeks ago, # ^ |   +3 This problem included the idea, to figure out the conditions.
 » 5 weeks ago, # |   +24 constraints of C is too strict. :(
•  » » 5 weeks ago, # ^ |   -6 no
•  » » » 5 weeks ago, # ^ |   +1 I was unable to think a good solution... Can you tell me what is complexity of the expected solution?
•  » » » » 5 weeks ago, # ^ | ← Rev. 2 →   +3 max = 1.5 * 10 ^ 7 complexity max * log(log(max)) to find least prime divisor and n * log(max) for finding prime divisor of every number So complexity = O( max * log(log(max)) + n * log(max) ) 
•  » » » » 5 weeks ago, # ^ |   +3 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 .
 » 5 weeks ago, # |   +76 I thought I registered for Codeforces contest, not Project Euler...
 » 5 weeks ago, # | ← Rev. 2 →   +5 Can anyone tell me what is test case 8 for Problem D (Div-2) ?
•  » » 5 weeks ago, # ^ |   0 Try 3 7 and 2 7
•  » » » 5 weeks ago, # ^ |   0 input: 3 7output: 20input: 2 7output: 12Is it ok??
 » 5 weeks ago, # |   0 How to solve Div2C and Div2D?
•  » » 5 weeks ago, # ^ |   0 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
 » 5 weeks ago, # |   +6 It's a pity that i can not hack myself.
 » 5 weeks ago, # |   +8 Math Problems.
 » 5 weeks ago, # |   +19 Look around, life has many interesting problems. But dude, you chose math :DGood contest by the way.
 » 5 weeks ago, # |   +18 how do you solve B?
•  » » 5 weeks ago, # ^ |   +21 nvm, i see it is all casework like i expected, too bad
•  » » » 5 weeks ago, # ^ |   +13 can't believe i wasted an hour and a half on that and still got it wrong LOL
•  » » » 5 weeks ago, # ^ |   +42 There is no need to check all the tricky cases by hand. You can write bruteforce and find all of them.
•  » » » » 5 weeks ago, # ^ |   0 I don't understand how you get all tricky cases by bruteforce. Can you explain briefly? (maybe with code?)
•  » » » » » 5 weeks ago, # ^ |   +3 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.
•  » » 5 weeks ago, # ^ |   +26 just a bunch of if conditions
•  » » » 5 weeks ago, # ^ |   0 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?
•  » » » » 5 weeks ago, # ^ |   +16 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
 » 5 weeks ago, # | ← Rev. 3 →   +7 It seems the pretests of problem div2.C are weak...
•  » » 5 weeks ago, # ^ |   +1 You are scaring me:|
•  » » 5 weeks ago, # ^ |   0 Very, very weak
 » 5 weeks ago, # |   +7 "that of all integers" Nah..
 » 5 weeks ago, # |   +46 And just like that, you wasted 2 hours of my life!
 » 5 weeks ago, # | ← Rev. 6 →   0 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.
•  » » 5 weeks ago, # ^ |   0 I've also thought of it, but I couldn't see a way to use this.
•  » » » 5 weeks ago, # ^ | ← Rev. 3 →   0 I think if that holds, you can solve the problem pretty easily. Find sum(T) for every subtree T in the tree. Store these in vector subtree-sums subtree-sums <- gcd(subtree-sums, sum(tree)) find all divisors of sum(tree), and index them Create subtree-counts, where subtree-counts[j] is the amount of appearances of divisor j of sum(tree) in subtree-sums do SOS-dynamic programming over this set, to set subtree-counts[i] <- amount of elements in subtree-sums such that divisor i divides them make array subtree-ans, where subtree-ans[i] = 1 iff subtree-counts[i] = sum(tree) / (divisor i) loop over all divisors i of sum(tree) from smallest to largest, and do subtree-ans[j] += subtree-ans[i] for all j, such that divisor-j / divisor-i = p for some prime p. Remember to take mod Output subtree-ans[i], where divisor-i = sum(tree) 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
•  » » » » 5 weeks ago, # ^ | ← Rev. 3 →   +8 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))
•  » » » » » 5 weeks ago, # ^ |   0 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?
•  » » » » » » 5 weeks ago, # ^ |   +10 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.
•  » » » » » » » 5 weeks ago, # ^ |   0 Ohh okay, I get it now. Nice solution!
•  » » 5 weeks ago, # ^ |   +8 Yes, your statement holds.
•  » » 5 weeks ago, # ^ |   0 The idea is probably correct, I have used it before on another problem. I couldn't really do anything with it though.
 » 5 weeks ago, # | ← Rev. 2 →   +8 Div2C Converting all ll divisions to int divisions drastically changed the running time... How does it even affect though?
•  » » 5 weeks ago, # ^ |   +3
•  » » » 5 weeks ago, # ^ |   0 Fair enough... Never considered memory level optimizations.
 » 5 weeks ago, # |   0 What happens if I resubmit a solution to a problem which I have already submitted a solution which passed the pretests?
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   0 The first solution which passes the system tests is considered and any WA before that will be an unsuccessful submission as usual.
•  » » » 5 weeks ago, # ^ |   0 That is not accured, the system ignore all submmits but the last one, you shoould read Skipped in the previos pretests passed.
 » 5 weeks ago, # |   0 What will be the approach for problem Div2 C (Enlarge GCD). I had TLE in 8th pretest.
•  » » 5 weeks ago, # ^ |   0 Did something like sieve. Only marginally avoided TLE. Wonder what will happen after systest.
•  » » » 5 weeks ago, # ^ |   0 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??
•  » » » » 5 weeks ago, # ^ |   0 Instead of calculating power, I just checked how many numbers are divisible by for all numbers > gcd
•  » » » 5 weeks ago, # ^ |   +3 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?
•  » » » » 5 weeks ago, # ^ |   0 Use the O(NloglogN) sieve. I used it and ran C in merely 0.5 seconds. NlogN sieve will obviously be tight.
•  » » » » » 5 weeks ago, # ^ |   0 I used sieve of eratosthenes, its complexity is nloglogn.
•  » » » » » » 5 weeks ago, # ^ | ← Rev. 2 →   0 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
•  » » » » » » » 4 weeks ago, # ^ |   0 Okay I saw the editorial. I get the difference now. Thank you so much for the suggestions DrumpfTheGodEmperor :)
 » 5 weeks ago, # |   +106 Sorry, but it was one the worst contest I've ever seen (I saw rounds of GreenGrape)
 » 5 weeks ago, # |   +31 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?
•  » » 5 weeks ago, # ^ |   -8 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.
 » 5 weeks ago, # |   0 Problem 1 and 2 pretest is weak
 » 5 weeks ago, # |   0 I was using this as generator to hack Div2 C:https://ideone.com/6yWmn9It 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?
•  » » 5 weeks ago, # ^ |   +3 In my memory, you should give newline as endl(instead of '\n') in hack data generator code.
•  » » » 5 weeks ago, # ^ |   +3 I use printf("\n") without problem. The problem is that it should have a "return 0;"
•  » » » » 5 weeks ago, # ^ |   0 In this case cf should give a better error :/ Is there any way to test the generator now?
•  » » » 5 weeks ago, # ^ |   0 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?
•  » » 5 weeks ago, # ^ |   +3 You wrote if(i!=n); so it generates an extra space at the end of the second line.
•  » » » 5 weeks ago, # ^ |   0 I don't get it? That was written specifically to avoid printing an extra space at the end of the last (nth) element.
•  » » » » 5 weeks ago, # ^ |   +13 if(1 > 2); cout << "1 is greater than 2"; 
•  » » » » » 5 weeks ago, # ^ |   0 Oh wow, just saw it, that was pretty stupid lol. Thank you guys for pointing it out!
 » 5 weeks ago, # |   +46 DIV. 1 B is the kind of problem that when you submit it you just pray you didn't forget any if -_-
 » 5 weeks ago, # | ← Rev. 2 →   +1 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: 3 100069 100069 1000103 These codes gives answer as "-1", while it is "1".Hope to see a round with better constraints, and better pretests, of course.
 » 5 weeks ago, # | ← Rev. 3 →   0 what is wrong in this submission(DIV 2 B).43208324
•  » » 5 weeks ago, # ^ |   0 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.
•  » » » 5 weeks ago, # ^ |   0 but 0 5 is not a valid input
•  » » 5 weeks ago, # ^ |   0 All you had to do was print the max possible sum of coordinates.
•  » » » 5 weeks ago, # ^ |   0 you are saying what you have done . My approach was: calculate the point with maximum difference from the origin.and just output the sum of coordinates
 » 5 weeks ago, # |   +1 How to solve Div2 D?
 » 5 weeks ago, # | ← Rev. 2 →   +36 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?
•  » » 5 weeks ago, # ^ |   0 Codeforces got hacked after System Tests. Mike should find the bug of his code.JK
 » 5 weeks ago, # | ← Rev. 2 →   0 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?
•  » » 5 weeks ago, # ^ |   0 There were many cases source code in C++ works properly with complexity of O(n), when n ≤ 109.Try with 105 points instead.
 » 5 weeks ago, # |   +8 Is it just me or do you also think this one for Div.1 was extra hard?
•  » » 5 weeks ago, # ^ |   +17 You can usually anticipate super hard contest with Chinese authors. I especially like problem E, but my bit mojo is weak.
•  » » » 5 weeks ago, # ^ | ← Rev. 2 →   0 I especially like problem E... 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.
 » 5 weeks ago, # |   +4 For C, just divide the array elements by initial GCD, and then https://www.geeksforgeeks.org/largest-subsequence-gcd-greater-1/
•  » » 4 weeks ago, # ^ |   0 This method is the most intuitive IMO, thanks for this short solution :)
 » 5 weeks ago, # |   0 How to solve Div2-C?
•  » » 5 weeks ago, # ^ |   0 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
 » 5 weeks ago, # |   +41 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
•  » » 5 weeks ago, # ^ |   +8 Thanks, Bae
 » 5 weeks ago, # |   0 Can someone find the bug in this log(n) method for finding the smallest prime of a number for problem C ? http://codeforces.com/contest/1047/submission/43217032Repeatedly failed test case 9.
•  » » 5 weeks ago, # ^ |   0 UPD: mistake found.
 » 5 weeks ago, # |   +4 Div2C constraints aren't fair for Java users x)Same solution in C++ passes in around ~600ms & around ~990ms in JAVA.
•  » » 5 weeks ago, # ^ |   +67 Java isn't fair for Java users
 » 5 weeks ago, # |   +98 I got TL on test 15 in A :( isn't it too harsh to set n = 300000, MAX = 15000000 for A?
 » 5 weeks ago, # |   +8 So many math problems... This contest is not friendly to me at all
•  » » 5 weeks ago, # ^ |   +13 This is not friendlyToMeContestForces.
 » 5 weeks ago, # |   +20 I'm not good in Mathematics, so I used bipartite matching in div1B. It was terrible for me. :(
 » 5 weeks ago, # |   +26 Div2C/Div1A should have had 1 more second time limit
 » 5 weeks ago, # |   0 can anyone help me with 3rd question in div2
 » 5 weeks ago, # | ← Rev. 3 →   +20 After C — that memory in right corner
 » 5 weeks ago, # |   +10 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!!!
 » 5 weeks ago, # |   +5 I'm the only one who solved the problem div2 B with Binary Search by answer? I dont understand solutions
•  » » 5 weeks ago, # ^ |   +8 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)
•  » » 5 weeks ago, # ^ |   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: int ans = 0; for(int i=0; i
•  » » 5 weeks ago, # ^ |   +5 My first thought was that too
 » 5 weeks ago, # |   +19 Hey guys. This two guys cheated on problem C. Just check these two submissions. http://codeforces.com/contest/1047/submission/43207716 http://codeforces.com/contest/1047/submission/43197339 The first submission is really similar to the second
•  » » 5 weeks ago, # ^ |   0 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
 » 5 weeks ago, # |   +22 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?
•  » » 5 weeks ago, # ^ |   +19 Solve it for n, m ≤ 20 with max flow, then make a spreadsheet of all these values and recognize the pattern.Solution
•  » » » 5 weeks ago, # ^ |   0 Or just use pen and paper — thought it might be a little slower.
•  » » » » 5 weeks ago, # ^ |   0 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?
•  » » » 5 weeks ago, # ^ |   0 Awesome, thanks so much Ben! I guess I spent too much time trying to think of insights instead of analyzing the patterns haha
•  » » » » 5 weeks ago, # ^ |   0 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.
•  » » » » » 5 weeks ago, # ^ |   0 Hey zscoder! Thanks so much for that advice, that really makes a lot of sense to me!
•  » » » » » 4 weeks ago, # ^ |   0 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?
 » 5 weeks ago, # |   +5 Is there anyone solve problem C with java ?
•  » » 5 weeks ago, # ^ |   0 http://codeforces.com/contest/1047/submission/43209921Just barely x)
 » 5 weeks ago, # |   -13 does anyone have the test case #44 of Div1 C/ Div2 A. I got WA on this test :((
 » 5 weeks ago, # |   +12 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)
 » 5 weeks ago, # | ← Rev. 3 →   -11 --Del--
•  » » 5 weeks ago, # ^ |   -16 Yeah, you feel proud of copy-pasting GeeksforGeeks's code LOL
•  » » » 5 weeks ago, # ^ | ← Rev. 2 →   -8 --Del--
 » 5 weeks ago, # |   0 you know a contest is bad when 100 points=2000 position difference
 » 5 weeks ago, # |   +40 The constraints for C are plain bullshit. Spoiled the contest for me.
•  » » 5 weeks ago, # ^ |   0 You created the sieve needlessly large (MAXN = 2e7+5). But I agree, the time limit should have definitely been 2s.
•  » » » 5 weeks ago, # ^ |   0 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.
•  » » » » 5 weeks ago, # ^ |   +19 Does copy-pasting linear sieve really make problem more interesting? Not sure about it
•  » » 5 weeks ago, # ^ |   +8 I didn't even try to optimize my sieve, still pass
 » 5 weeks ago, # |   +42 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!
•  » » 5 weeks ago, # ^ |   0 At least someone here gave an encouraging constructive feedback towards an author who have just made his debut
 » 5 weeks ago, # |   +5 Screencast of the round(div2). https://youtu.be/NMyhboAp0DI problems solved: A, B, C
 » 5 weeks ago, # |   +7 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 :)
 » 5 weeks ago, # |   +3 http://codeforces.com/contest/1047/submission/43216650http://codeforces.com/contest/1047/submission/43220019Find the difference. SpoilerThere is no.
 » 5 weeks ago, # |   0 Couldn't figure out some critical cases for Problem C.
 » 5 weeks ago, # | ← Rev. 3 →   +3 missed many test cases in div2C... Done :(
•  » » 5 weeks ago, # ^ |   0 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
•  » » » 5 weeks ago, # ^ | ← Rev. 3 →   0 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..
•  » » » » 5 weeks ago, # ^ |   0 No, it is not. For example it is not enough to find prime factors of 4553947. It is 2131*2137, multiplication of 321th and 322th prime numbers. Your solution fails on the following test case: 3 2137 4541161 4553947 2137 = 322th prime number 4541161 = square of 321th prime number 4553947 = multiplication of 231th and 232th prime numbers Your program outputs 2, whereas right answer is 1(we can delete 2137). P.S. You are very lucky as I hacked your wrong solution after the contest:) 
 » 5 weeks ago, # |   -7 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.
•  » » 5 weeks ago, # ^ |   -24 you can't copy/past code from geeksforgeeks or some other site, am sure many users did the same and got skipped like you.
•  » » » 5 weeks ago, # ^ |   +10 "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.
•  » » » 5 weeks ago, # ^ |   +10 Can we use code from Emaxx?
•  » » » 5 weeks ago, # ^ |   +13 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.
•  » » » » 5 weeks ago, # ^ |   -13 You are right, its my mistake, actually every thing is clear hereHowever, anyone should try to solve the problem by his eforts, goggling the solution wont help anyone improve.
 » 5 weeks ago, # |   0 Div 2 C Submission : 43222119 I am not sure why it is producing Runtime Error. I ran the code locally with Test Case 24, and it is working fine on my machine.
•  » » 5 weeks ago, # ^ |   0 43223018 int -> ll and 15000000 -> 15000005
•  » » » 5 weeks ago, # ^ |   0 Got AC :D
•  » » » 5 weeks ago, # ^ |   0 This is Depressing :(. Just changing 15000000 -> 15000001 worked.SysTest Failed due to this mistake.
•  » » » » 5 weeks ago, # ^ |   0 Yes, codeforces teaches write code without any bug
 » 5 weeks ago, # |   +8 Where is editorial?:c
 » 5 weeks ago, # |   0 I think these guys cheated and got away with it.http://codeforces.com/contest/1047/submission/43211821http://codeforces.com/contest/1047/submission/43209970
•  » » 5 weeks ago, # ^ |   0 almost same?! coincidence? i don't think so
 » 5 weeks ago, # | ← Rev. 2 →   0 Can someone help me with my solution. I am not able to figure why it failed in system tests. solution
 » 5 weeks ago, # | ← Rev. 2 →   0 Around 180 soln of C/D failed in top 380.
 » 5 weeks ago, # |   +19 WTF, wasn't packing product (E) really never asked before?
 » 5 weeks ago, # |   0 Old and kind div2 contests, where is possible to come up with only two first problems... Mmm, i have missed it too long
 » 5 weeks ago, # |   0 Little C is so cute(qwq)...But this round looks like a math round and it's a little difficult
 » 5 weeks ago, # |   +65 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. O(A log A)#include #define MAXN 300004 #define MAXA 15000004 static int n, a[MAXN], cnt[MAXA] = { 0 }; int main() { int i, j; scanf("%d", &n); for (i = 0; i < n; ++i) { scanf("%d", &a[i]); ++cnt[a[i]]; } int ans = 0; for (i = 2; i < MAXA; ++i) { int cur = 0; for (j = i; j < MAXA; j += i) cur += cnt[j]; if (cur != n && ans < cur) ans = cur; } printf("%d\n", ans == 0 ? -1 : n - ans); return 0; } 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! :)
 » 5 weeks ago, # |   +3 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)
 » 5 weeks ago, # |   +1 I just finished coding div1-C but the queue is too long and it doesn't seem to progress...
 » 5 weeks ago, # |   0 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?
•  » » 5 weeks ago, # ^ |   +1
•  » » » 5 weeks ago, # ^ |   0 Thanks, I understand.
 » 5 weeks ago, # |   0 for D(div2)why(n=7;m=1)answer is 6?
•  » » 5 weeks ago, # ^ |   +3 1 2 3 1 2 3 x
 » 5 weeks ago, # |   +3 MikeMirzayanov, why is the queue so long, when will the submissions start getting judged ? Please look into the matter at the earliest :(
 » 5 weeks ago, # |   +39 So where is the editorial?
 » 5 weeks ago, # | ← Rev. 2 →   0 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.
•  » » 5 weeks ago, # ^ |   0 ABC are easy simulations.D is a easy math problem.But I'm so young that I don't finished C.
•  » » 5 weeks ago, # ^ |   0 On bzoj?
•  » » » 5 weeks ago, # ^ |   0 I read the question wrong.My bad.Sorry.
 » 5 weeks ago, # |   0 Waiting for Editorial ! Can anyone help with Div 2 Problem C ?
•  » » 5 weeks ago, # ^ |   0 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.
•  » » 5 weeks ago, # ^ |   0 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
•  » » » 4 weeks ago, # ^ |   0 Many thanks! It's was of great help.
 » 5 weeks ago, # |   0 Still waiting for the editorials.......huh common man be fast.....
 » 5 weeks ago, # |   0 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
•  » » 4 weeks ago, # ^ |   0 It's published now.
 » 5 weeks ago, # |   +6 How to solve Div1 C / Div2 E ??
 » 5 weeks ago, # | ← Rev. 3 →   0 Low memory solution for Div.2C / Div.1Ahttp://codeforces.com/contest/1047/submission/43263896Btw, maybe you guys can add some more optimizations for this solution(except custom i/o), i'd appreciate it.