### DmitryGrigorev's blog

By DmitryGrigorev, 3 months ago, translation, ,

Hi, Codeforces! I'm glad to invite everybody to the #489 Codeforces Round, which will be held as soon as tomorrow, on Monday, June 18, 2018 at 19:35. The round will be rated for all participants from the second division (with rating below than 2100). As usually, we will be glad to see participants from the first division out of competition!

Problems for the round have been invented and prepared by us, pupils of Moscow school №2007, Dmitry DmitryGrigorev Grigorev and Fedor ushakov.fedor Ushakov. We want to give thanks to Andrew GreenGrape Raiskiy for his aid in preparing and testing of the problems, to Ildar 300iq Gainullin and to AmirReza Arpa PoorAkhavan who have tested our problems too and to the coordinator Nikolay KAN Kalinin, since our sometimes strange and undeveloped ideas have become eventually the Codeforces round. Also, we say thank you to Mike MikeMirzayanov Mirzayanov for his unbelievable Codeforces and Polygon platforms.

You will receive 5 problems and 2 hours for solving it. During the round you will be helping for an extraordinary girl Nastya, who has been living in Byteland and sometimes receives very strange gifts for her birthday :).

Score distribution will be announced, traditionally, closer to the start of the contest.

We're holding our the first and, I hope, not the last round in Codeforces, so I hope a lot you will like our problems. Please, read all the problems. Anyway, I wish luck and high rating for all the participants!

UPD Score distribution is standart — 500-1000-1500-2000-2500

UPD2 Thank you for your participation in the contest! It's very-very pleasant for me if you like the problems, and I'm sorry if you don't :) I hope the next my contest will be even better, than this. Thank you for all!

List of the winners of the contest:

Div.2

Div.1 + Div.2

My frank congratulations for all the winners!

UPD3

Editorial is here

•
• +405
•

 » 3 months ago, # |   -56 Is it rated? don't downvote plz, tomorrow is my birthday
•  » » 3 months ago, # ^ | ← Rev. 2 →   +33 Happy Birthday Numb in advance.
•  » » 3 months ago, # ^ |   +5 Not rated for division 1.
•  » » 3 months ago, # ^ |   -33 i hope it rated for the both Division , maybe your luck works in your birthday and you Became International master <3 Anyway happy birthday <3
 » 3 months ago, # |   +17 Finally someone remembered to thank both KAN and MikeMirzayanov.Hoping it would be a good round after the last one.Good Luck everyone.
•  » » 3 months ago, # ^ |   -41 is that true ?? any one mention KAN and MikeMirzayanov will have upVotes ?
•  » » » 3 months ago, # ^ |   0 You got it wrong it's not the name but the thanks part for the work they do for us in preparing contests and updating codeforces on a regular basis.
 » 3 months ago, # |   -27 score distribution ?
•  » » 3 months ago, # ^ |   +2 It will probably be announced before the contest
•  » » 3 months ago, # ^ |   +21 just saw your graph! You have my respect, mate!
•  » » » 3 months ago, # ^ |   -12 we are gladiators ( like viking , icleland football team + mexicans )
•  » » » » 3 months ago, # ^ |   -7 well said!
•  » » 3 months ago, # ^ |   +5 Of course, it will be announced before the contest. I'm sorry, I forgot to write it in the English announcement.
 » 3 months ago, # |   -32 Usually strange gifts will transferred to someone else later. I predict that we will become this "someone else". However, in addition, Nastya will tell us what to do with our gift. Nastya forces us to do strange things. Do not be like Nastya.
 » 3 months ago, # |   -26 SpoilerUnUsual Usual contest time !
•  » » 3 months ago, # ^ |   +1 Do you ever get upvotes ? xD
 » 3 months ago, # |   +18 I was hoping to see one thematic contest of the world cup
•  » » 3 months ago, # ^ |   0 creates confusion for non followers and boring too
 » 3 months ago, # |   +8 hoping to see more of mathematics ,all time favorite GreenGrape
•  » » 3 months ago, # ^ |   +2 Your wish came true :)
•  » » » 3 months ago, # ^ |   +3 true...:D
 » 3 months ago, # |   +4 Getting 502 Gateway error, hope that will be fine at contest time :)
•  » » 3 months ago, # ^ |   0 I think they were doing some server maintenance.
 » 3 months ago, # |   +4 Expecting a good contest....
 » 3 months ago, # |   +6 Score distribution?
•  » » 3 months ago, # ^ |   +3 Updated. Check now.
•  » » » 3 months ago, # ^ |   +3 Yeah, got it. Thanks
 » 3 months ago, # |   0 10 sec to go
 » 3 months ago, # | ← Rev. 2 →   0 In problem B the 2nd test case also includes the pair (2,6) and (6,2) Sorry i realize now that was my mistake
 » 3 months ago, # |   0 Too keked
 » 3 months ago, # |   -10 In the problem C : Also, you should find the answer modulo 10^9+7 Can someone explain what this means,please?
•  » » 3 months ago, # ^ |   +10 You should ask questions on "problems" page. There you can get answer momentarily.If the answer is A, you should print the remainder of division of A on 109 + 7.
•  » » » 3 months ago, # ^ |   +3 Understood,thank you!
 » 3 months ago, # | ← Rev. 3 →   0 Hi, in problem C im having WA on test number 2. However on my computer (with the same code) it gives the correct answer. Can someone check this out please?EDIT:It was my bad, sorry.
 » 3 months ago, # |   +31 Wtf, math contest.
•  » » 3 months ago, # ^ |   +8 :D :D
•  » » » 3 months ago, # ^ |   0 It's not funny
•  » » » » 3 months ago, # ^ |   0 I'm sorry. I'm quite surprised as well. I'm screwed up too.
 » 3 months ago, # |   +84 Mathforces Round #489 (Div. 2)
 » 3 months ago, # |   0 What is unexpected verdict when trying to hack problem C?
 » 3 months ago, # |   +1 Drunken and sleepy ㅜ_ㅜ
 » 3 months ago, # | ← Rev. 2 →   +121
 » 3 months ago, # |   +1 How to solve div-2 B?
•  » » 3 months ago, # ^ | ← Rev. 2 →   +5 There are two numbers. Obviously, since gcd is x, therefore common factor is x. so now both have factor x. So first number is in form a*x and second is in b*x and gcd(a, b) must be equal to 1. Since both number can't have other than x. Now GCD* LCM = first_number * second number. So x*y = (x*a) * (b*x) So y/x = a*b so we need to find all pairs (a, b) where gcd(a, b) ==1 && min(a*x, b*x)>=l && max(a*x, b*x)<=r and damn this count is the answer. There is just one catch, that y must be divisible by x. Otherwise the answer will be 0.
•  » » » 3 months ago, # ^ |   0 I kind of used the same logic, if possible can you please tell why is this solution failing. http://codeforces.com/contest/992/submission/39386988
•  » » » » 3 months ago, # ^ |   +1 Same as I mentioned the catch. When y is not divisible by x. Let's take test case 1 100 3 10 The answer should be 0. But it is giving 2 as output.
•  » » » 3 months ago, # ^ |   0 Thanks go it , i assumed lcm to be divisble by x, which was a stupidity.
•  » » » 3 months ago, # ^ |   0 in form a*x and second is in b*y wont be second number also in form b*x
•  » » » » 3 months ago, # ^ |   0 Yeah typo error Lemme edit it.
•  » » » 3 months ago, # ^ | ← Rev. 2 →   0 Second is b*x. Right? Not b*y.
•  » » » » 3 months ago, # ^ |   0 Yes it was a typo error. Edited !
 » 3 months ago, # |   +1 How to solve Div 2 B ?
•  » » 3 months ago, # ^ | ← Rev. 2 →   +4 If y is not divisible by x, answer is 0. Otherwise, all pair (a, b) that satisfy the condition can be represented by (x * a', x * b'). Let , , . Now the problem is counting number of pair (a', b') in range [l', r'] such that GCD(a', b') = 1 and LCM(a', b') = y'.This can be done by iterate over all divisor d of y' and check if pair satisfy all the condition above.My implementation
•  » » » 3 months ago, # ^ |   0 I think its can be done just by iterate over all divisor d of y and check if each pair count number of pair satisfy all the condition:  l<=a<=r and l<=b<=r and gcd(a,b) = x and lcm(a,b) = y its can be done inO(d^2) where d is number of divisor of y... My implementationyou can check that here: 39390416 ,unfortunately i don't got that along the contest :(
•  » » 3 months ago, # ^ |   +5 There are two numbers. Obviously, since gcd is x, therefore common factor is x. so now both have factor x. So first number is in form a*x and second is in b*y and gcd(a, b) must be equal to 1. Since both number can't have other than x. Now GCD* LCM = first_number * second number. So x*y = (x*a) * (b*x) So y/x = a*b so we need to find all pairs (a, b) where gcd(a, b) ==1 && min(a*x, b*x)>=l && max(a*x, b*x)<=r and damn this count is the answer. There is just one catch, that y must be divisible by x. Otherwise the answer will be 0.
•  » » » 3 months ago, # ^ |   0 why min(a*x, b*x) >= l and not a*x >= l && b*x >= l ??
•  » » » » 3 months ago, # ^ |   +6 You have to check both a*x>=l && a*x<=r && b*x<=r && b*x>=l. I done it in two statements min(a*x, b*x) >=l Since if minimum is greater than l, then the number which is greater than or equal to other number will always be greater than l. Same goes for max(a*x, b*x)<=r Since max of both number is less than r So the other number (which is less then the first one) will always be less than r. You can always check all four statements if you like. a*x>=l && a*x<=r && b*x<=r && b*x>=l.
•  » » » » » 3 months ago, # ^ |   0 Yeah. Sorry that was a stupid question! By the way, can you explain the case for 0. why would it be 0?
•  » » » » » » 3 months ago, # ^ |   0 First of all question was not stupid. It was cool. Your solution got a problem. I, myself got 2 WA on this one. Secondly as i told you two numbers are in form a*x, and b*x Now lcm * gcd = product of number (for 2 numbers) so y*x= a*x * b*x so y=a*b*x so y must be divisible by x. if not divisible you can never find any a, b irrespective of l and r. So the count is 0 in such case.
•  » » » » » » » 3 months ago, # ^ |   +3 Got it Bro, Thanks :) That's what is missing in my solution, The TC 5.
•  » » 3 months ago, # ^ | ← Rev. 3 →   +6 Find the prime factors of y/x For those prime factors which are present more than once, replace them with their product. For example: 12 = 2*2*2*3*5*5 should be made 12 = 3*8*125. Store these in a vector, say, "facts". It can be noted that size of vector "facts" is not more 15. So we can iterate on all subsets of facts to multiply each value of facts to either a or b. (a and b are numbers to be found). This can be done using bitmasks. For calculated values of a and b, check if they are between l and r, and increment the ans variable. Check specially for case when y is not divisible by x, and the case when a=b. Here is my solution 39374707
•  » » » 3 months ago, # ^ |   0 thats exactly wha i did and i get wa on test 9..... https://pastebin.com/bCfGhsx6
•  » » » » 3 months ago, # ^ |   0 You can refer to my solution 39374707
•  » » » » 3 months ago, # ^ |   0 I'm not able to compile yours on JAVA compiler. Just check on test case 1 1000 3 100 The answer must be 0. I think you didn't check if y is divisible by x or not If not divisible then the answer is always 0.
•  » » 3 months ago, # ^ |   0 Simple Explanation is as follows: LCM(a, b) = a * b / GCD(a,b) ....... eq(1) and if g = GCD(a, b) you can write a = p * g ; b = q * g such that p & q are coprime i.e. GCD(p, q) = 1 So above equation 1 can be rewritten as LCM(a, b) = ((p * g)*(q * g))/g LCM(a, b) = p * q * g ; where g is gcd(a,b) So now problem became: for given integers y and r , count number of unordered pair (p,q) such that y = p * q * r and p & q are coprime i.e gcd(p, q) = 1. That you can do in O(sqrt(N)) Ref Solution
 » 3 months ago, # |   +15 How to solve D?
•  » » 3 months ago, # ^ |   0 I thought of Divide & Conquer based solution but couldn't merge efficiently.If somebody solved like this, then please help how!
•  » » 3 months ago, # ^ | ← Rev. 2 →   +76 Notice that the product will get big really fast. So for each starting index you can just iterate over the end index until the product gets too big (e.g.  > 2·1018). This will have runtime .The only problem with this approach is that this doesn't hold if there are a lot of 1s in it. But you can modify the approach from above so that you jump over the 1s, and check in O(1) if there is a solution (there can be only one) with the 1s that you jumped over..
•  » » » 3 months ago, # ^ |   0 Really nice and simple. Thank you!
•  » » 3 months ago, # ^ |   0 Couldn't code it in the time I had, but my idea was something like this:I stored the sum upto n numbers in an array, and the value of k for the first n numbers taken consecutively in another array k[n]. Now, for every element for which k[i]>=k(required), just check if there are consecutive numbers up back till the last element with this property.
•  » » 3 months ago, # ^ |   0 I've compressed segments, that contains only "1". Then you can just bruteforce all segments ([0; 0], [0; 1], ... [0; n-1], [1; 1], [1; 2], ...), refreshing p and s for O(1) and breaking when p>z, where z=(2*10^5)*(10^8)*(10^5).It's working for O(n*log(z)), but you must handle overwflows carefuly.
 » 3 months ago, # |   +2 my incorrect (WA on pretest 7) solution for B — Nastya Studies Informatics is to find all factors of y, then generate all pair, if the pair satisfy gcd(first, second) == x && lcm(first, second) == y then increment resultwhat is wrong with the solution?
•  » » 3 months ago, # ^ | ← Rev. 2 →   0 You should check the case 1 1 1 1It cost me 3 WAs as well :(Edit: Answer for this case is 1 BTW, it gave me 2 due to an error in my code only for this specific case.
•  » » » 3 months ago, # ^ |   0 my code output for case 1 1 1 1 is 1what it should be?
•  » » » » 3 months ago, # ^ |   0 Oh wait... have you checked both numbers in each pair >=l and <=r as well?
•  » » » » » 3 months ago, # ^ |   0 yes, i also checked that
•  » » 3 months ago, # ^ |   +2 You wrote in the program: int lcm(int a, int b) { return (a*b)/gcd(a, b); } If a and b are too big, it can be overflow (109·109 = 1018 >  maximum value of int).For example: test case: 1000000000 1000000000 1000000000 1000000000 correct answer: 1 your output: 0
•  » » » 3 months ago, # ^ | ← Rev. 2 →   0 oh thanks! got accepted on practice submit because of thatthat was some noob mistake :( i should check any overflow case later
•  » » » » 3 months ago, # ^ | ← Rev. 2 →   0 Pro tip: write #define int long long at the beginning of every solution and use signed main().
•  » » » » » 3 months ago, # ^ |   +5 What's the difference between int main() and signed main()?
•  » » » » » » 3 months ago, # ^ | ← Rev. 2 →   +5 I think that if you do the define the compiler will think you wrote long long main and it would say that it's an error, but if you write signed main() it would be alright
•  » » » » » » » 3 months ago, # ^ | ← Rev. 2 →   0 Exact.
 » 3 months ago, # |   -57 worst contest with no creativity
 » 3 months ago, # |   +3 Was E square root decomposition?
•  » » 3 months ago, # ^ |   0 I tried a sqrt approach, it was TLE 13. I was using unordered_maps, so I tried to implement hashes, but didn't finished in time. I think there is a log solution
•  » » » 3 months ago, # ^ | ← Rev. 2 →   +3 It's too slow solution, the same our solution worked >10 sec
•  » » » 3 months ago, # ^ |   -8 Usually if you think it is solvable with sqrt-decomposition, dump the idea and look for a better solution. In most the cases you would be right.
•  » » 3 months ago, # ^ |   +51 Of course, No :)Idea is simple, there are not many positions that greater than sum of previous.
•  » » » 3 months ago, # ^ |   0 can you explain more ?
•  » » » » 3 months ago, # ^ |   +11 It likes fibonacci sequence, there are little terms  ≤ 109. So what you need to do is just pick the maximum until it less than or equals 0.
•  » » » » » 3 months ago, # ^ |   0 The way I thought about the problem was to always start searching at the first index i = 0, and if that index wasn't the shaman-king then go to the smallest index j such that j > i and aj  ≥  sum(A[: i + 1]). Continue doing this until there is no such index j. All of this can be done quickly using segment trees. Worst case aj should double in size (not Fibonacci) for each iteration, and all of the segment tree operations will run in time so my solution should run in . 39387502.
•  » » » » » 3 months ago, # ^ | ← Rev. 3 →   0 chemthan Could you please explain this in brief?
•  » » » » » » 3 months ago, # ^ |   +1 Assuming i1 < i2 < ... < ik are all positions d such that ad > a1 + a2 + ... + ad - 1. Then obviously aic ≥ ai1 + ai2 + ... + aic - 1 + 1. We have: ai1 ≥ 0, ai2 ≥ 1, ai3 ≥ 2, ai4 ≥ 4, .... Because ai ≤ 109 so the number of terms k is not big.Then let fd = ad - ad - 1 - ad - 2... - a1, using a segment tree to get all d s.t. fd ≥ 0. The number of d s.t. fd > 0 is less than log2(109) so each query we get out at most that number until fd ≤ 0.
•  » » 3 months ago, # ^ |   +8 Hey My square root decomposition solution 39389380 passed after contest. (missed submitting during contest by 1 minute). Have a look.
•  » » » 3 months ago, # ^ |   0 Super tight time limit :D
•  » » » » 3 months ago, # ^ |   +1 I regret wasting time on D now :(
 » 3 months ago, # | ← Rev. 3 →   0 PS: Found mistake . It doesnt work, Sorry
 » 3 months ago, # |   +29 It was very nice contest:::::: thanks
 » 3 months ago, # | ← Rev. 3 →   +3 pretest #12 of C? any hints please verdict- WAEdit this is the code please tell me whats wrong-http://p.ip.fi/_4l8Update- I got it thanks for looking over my code everyone. In python n//2 and int(n/2) are not the same it looks like.
•  » » 3 months ago, # ^ |   +8 take modulus of x by 1e9+7 after scanning input.
•  » » 3 months ago, # ^ |   0 Overflow most probably.
•  » » » 3 months ago, # ^ |   +1 Overflow in Python?
•  » » » » 3 months ago, # ^ |   +1 Max range of integer in python is around 10^(7000).
•  » » » » » 3 months ago, # ^ |   0
•  » » 3 months ago, # ^ |   0 Maybe your program prints negative number?
•  » » » 3 months ago, # ^ |   0 Modulus gives a positive number in python as far as I know.
•  » » » » 3 months ago, # ^ |   0 Got it. Hmm, everything seems OK.
•  » » 3 months ago, # ^ |   0 if x==0 or x%1000000007==0:This is wrong. Only if x==0 is required.
•  » » » 3 months ago, # ^ |   0 Yes you are right. But I removed that and still WA.
•  » » 3 months ago, # ^ |   0 Screwed with 12th test case 3 times. I just simplified my expression (may be overflow) and got AC in last 7 minutes.
 » 3 months ago, # |   0 when will the rating changes happen ? (sorry for bad english)
•  » » 3 months ago, # ^ |   0 There is a chrome extension called CF-Predictor
•  » » » 3 months ago, # ^ |   0 i know about it , and i have it ,but that does not mean all of my problems(a,b) will be accepted.
 » 3 months ago, # | ← Rev. 2 →   -14 I don't like math problems.
 » 3 months ago, # |   0 I read only A, B and C, but looked more a math contest than a programming contest to me! Thanks to the author, anyways.
•  » » 3 months ago, # ^ |   +26 Programming contest are half logics and half maths.
 » 3 months ago, # |   0 Managed to solve A,B,C. How to solve D?
•  » » 3 months ago, # ^ |   +9 I think the main idea is that the maximum possible product is TOTALSUM*k, so there can be at most log_2(TOTALSUM*k) elements larger than 1 in a valid array.Hence we can bruteforce over all possible (i,j) where i is the position of the first element larger than 1 in the array and j is the last position.Once you have that you just need to look at how many extra ones you can add to the left of i and to the right of j.I did this but I made a mistake I guess.
 » 3 months ago, # |   0 What was Test case 4 for C?
•  » » 3 months ago, # ^ | ← Rev. 2 →   0 k = 0, I think.
•  » » 3 months ago, # ^ |   0 i guess its y := 0ans should be (x<<1)%M
•  » » 3 months ago, # ^ |   0 Likely your program didn't pass that test case due to overflow. (That's what happened to me in the first attempt)
•  » » 3 months ago, # ^ |   0 Darn. I missed ONE mod sign :(
•  » » » 3 months ago, # ^ |   0 I did everything right , just took 64 as 2^8 and used 2^k instead of 2k somewhere and messed up the whole thing.
•  » » 3 months ago, # ^ |   0 it was x=0 i think;(
•  » » » 3 months ago, # ^ |   +1 That was test case = 9
 » 3 months ago, # |   0 How was in Problem C 'n==1' solved??
•  » » 3 months ago, # ^ |   0 Just as n==2,n==3,n==4 and so on.
•  » » 3 months ago, # ^ |   0 because at the end there will be twice the dresses, but there can be one less dress with 50% probability, so at the end there will be 2 * x and 2x + 1 dresses each with 50% prob. Rest is simple. This gives f0 = xanswer is twice of fn
 » 3 months ago, # |   0 I have a doubt. Suppose I submit a solution which passes all pretest. Then I submit a solution which fails on pretest. Will then only my 1st solution be considered ? Or i will have some penalties?
•  » » 3 months ago, # ^ |   +3 Just the 1st one
 » 3 months ago, # |   0 My idea for D:at most I will multiply with 62 numbers greater than 1, so for every number I store the next number greater than 1, and I should take care of the ones between, am I missing something???
•  » » 3 months ago, # ^ |   +3 No, that it.
•  » » 3 months ago, # ^ |   +3 I did the same thing.
•  » » » 3 months ago, # ^ |   +6 I did the same but i messed up somewhere.
•  » » » » 3 months ago, # ^ |   0 It seems like I also had some bugs :(
 » 3 months ago, # |   +16 RIP ratings.
 » 3 months ago, # |   +3 This round makes me realize how poor my math is.TAT.
 » 3 months ago, # |   0 In problem A i was having time limit exceeded on pretest 6 as the judgement. Did any one face the same problem and knows how to fix that?
•  » » 3 months ago, # ^ |   0 your code link ??
•  » » » 3 months ago, # ^ | ← Rev. 2 →   0
•  » » » » 3 months ago, # ^ |   0 It's kinda obvious your solution works in O(n^2) for n = 1e5. No surprise you got TL.
•  » » » » » 3 months ago, # ^ |   0 can you explain more why that obvious?
•  » » » » » » 3 months ago, # ^ | ← Rev. 2 →   -18 _
•  » » » » » » » 3 months ago, # ^ |   0 1) He said he got TL6, not WA1. He just post the wrong link. 2) It's obvious that is was some debug output and he undestands he shouldn't use printf instead of scanf. 3) Now he posted correct link.
•  » » » » » » 3 months ago, # ^ |   0 Suppose there is no a[i] = 0; Then your code is simmilar to: for (int i = 0; i < n-1; i++) for (int j = i + 1; j < n; j++) { do_something(); } Still not obvious?
•  » » » » » » » 3 months ago, # ^ |   0 thanks! :) am a newbie dont know much so wasnt aware that nested loops of this sort are never fast enough
•  » » » » » » 3 months ago, # ^ | ← Rev. 3 →   +1 There is a nested loop in your code: for(int i=0;i
•  » » » » » » » 3 months ago, # ^ |   0 thanks!
•  » » » » » » 3 months ago, # ^ |   0 Your code complexity if N*N (as your code runs n times for every outer loop.) So n*n statements minimum. Generally 1 sec = 10^8 operations. and here n=10^5 so n*n = 10^10 so it will take 100 secs. That's why you are getting TLE. Hope it helps.
•  » » » » » » » 3 months ago, # ^ |   0 really helped! thanks :)
•  » » » » 3 months ago, # ^ |   -6 bro you have used printf instead of scanf.....that's why tle and runtime type errors are coming.
 » 3 months ago, # |   +13 div2B was not made for div2B.
 » 3 months ago, # |   +9 Problem E was really nice.
•  » » 3 months ago, # ^ |   0 Because you solved it :D
•  » » » 3 months ago, # ^ |   0 I solved D too that wasn't nice at all!
•  » » » » 3 months ago, # ^ | ← Rev. 2 →   0 Well, you don't solve E in every contest ;p
 » 3 months ago, # |   +3 How to solve DIV2 C?
•  » » 3 months ago, # ^ |   +15 Observe that after k months, there can be 2k * x, 2k * x - 1, ... , 2k * x - (2k - 1) clothes in the wardrobe, with equal probability .By using definition of expected value, we find that the expected number of clothes after k months is . The answer to this problem is twice of this number, i.e. 2k(2x - 1) + 1.Note the special case: if x = 0, the answer is 0 no matter what k is.
•  » » » 3 months ago, # ^ |   0 I used the same logic still kept getting error on pretest 5. http://codeforces.com/contest/992/submission/39380228
•  » » » » 3 months ago, # ^ |   0 Most likely overflow.You should append LL to numbers you intend to be used as long long, e.g. "2LL"
•  » » » » » 3 months ago, # ^ |   0 Thanks :)
•  » » » » 3 months ago, # ^ |   0 Me too bro :(
•  » » » » 3 months ago, # ^ |   0 You have taken a negative without adding a MOD. cout<<((x*poww(2,k+1))%mod-poww(2,k)+1)%mod; For solving it use cout<<((x*poww(2,k+1))%mod-poww(2,k)+1 + mod)%mod; Still try to use mod after avery arithmetic operation
•  » » » » » 3 months ago, # ^ | ← Rev. 2 →   0 oh gosh!! Thank you so much for pointing it out. I had totally missed it.
•  » » » 3 months ago, # ^ |   +2 F**K only because of x=0 special case I was getting WA.
•  » » 3 months ago, # ^ | ← Rev. 2 →   0 Let f(x, k) be the answer for input x and k.Then we have the recurrence,For k ≥ 1,and f(x, 0) = 2x.By induction, you get f(x, k) = 2k + 1x - 2k + 1.Use repeated squaring to evaluate the powers with the right modulus.
 » 3 months ago, # |   0 i find the penalty on re-submission kinda weird :(
 » 3 months ago, # |   +1 Can D be solved using two pointer both starting from beginning ?
•  » » 3 months ago, # ^ |   0 nope. The solution comes from fact "ones are useless"
 » 3 months ago, # |   0 Forgot to take mod in C fml. Also can someone tell whats wrong with my code for D — http://codeforces.com/contest/992/submission/39387013 ?
•  » » 3 months ago, # ^ | ← Rev. 3 →   0 5 21 1 2 1 1Your solution fails on this case, ans should be 3
 » 3 months ago, # |   +62 B is a bit too hard, and the problem involved a lot of maths, but the problemset is nice overall. I liked B and D the most.Also, I appreciate the fact that pretests is strong and included corner cases (n = 0 in C).
•  » » 3 months ago, # ^ |   0 Problem E smells like an interesting problem as well. It's the kind of problem you think you'd go like 'aaa, hmm, mkay, that's pretty cool' haha
•  » » » 3 months ago, # ^ |   0 I didn't come up with that observation (I thought the upper bound is at first, so RIP). But now knowing that, I think E is also a cool problem.
 » 3 months ago, # | ← Rev. 2 →   -15 A lot of Maths!
 » 3 months ago, # |   -8 For problem E, can we solve sqrt(q) queries at a time by pre processing for each sqrt block. My idea is to find all the indices that are updated in that block and then we make a new array having all the subsequent indices that are not updated together as a same element. We can maintain the sum of that element and also create a map to check the sum requirement of all the indices in that element, while for indices that are updated, we can check if the prefix sum till that element is equal to that element. Time Complexity will be O(n * root(q) + q * root(n)).
 » 3 months ago, # |   0 What was test case 5 for c?
•  » » 3 months ago, # ^ |   0 x==0
•  » » » 3 months ago, # ^ |   0 It should not be x == 0 as I had considered it a special case and printed 0(verifying)
•  » » » » 3 months ago, # ^ |   0 Yes I'm sorry that was pretest 9. Messed up a lot today :/
 » 3 months ago, # |   +10 Solution of problem B already exists on the internet. link : Click . Found it after the contest!
•  » » 3 months ago, # ^ |   0 How to modify it to include the range specification?
•  » » » 3 months ago, # ^ | ← Rev. 2 →   0 Edit:Nevermind, like a tilted fool I read the wrong block of code and didn't realize it wouldn't run in time, give me a minute
•  » » » » 3 months ago, # ^ |   +3 That solution would give TLE because it iterates all the numbers until 1e9
•  » » » 3 months ago, # ^ |   0 You can iterate over all the 2^k subsets and check range of product of each subset. You can do that because k will be less than 11 as the product grows rapidly. See primorials
•  » » » 3 months ago, # ^ |   0 If you read the efficient solution which was given in the link above, you can see that the answer is 2^number_of_distinct_prime_factors(lcm/gcd). You can do this: bruteforce through all pairs of numbers that can be formed using distinct prime factors of lcm/gcd such that their multiplication is equal to lcm/gcd, and add to answer if both of them are in range [l,r]. That was my solution (not the best one i think, but it passed).
•  » » 3 months ago, # ^ | ← Rev. 2 →   0 Its not same at all. You also have to check if a and b are between l and r, which requires a lot more work.
•  » » » 3 months ago, # ^ |   0 No .. it does'nt ... once you get the logic ... checking for a pair elements to lie in a particular range is not a big deal.
 » 3 months ago, # |   +3 What is pretest 9 in D and why did it bend me over?
•  » » 3 months ago, # ^ |   0 probably x = 0, I completely forgot about it
•  » » » 3 months ago, # ^ |   0 i think thats problem c
•  » » » » 3 months ago, # ^ |   0 sorry, i misread your comment
•  » » » » » 3 months ago, # ^ |   0 Found it ! For the case of segments in which the product is 1 I made a mistake and took the cases in which sum = k and product = 1. Changing that fixes everything ! :(
 » 3 months ago, # |   +2 Thanks for strong pretest of Problem C. To me it was easier than Problem B.
•  » » 3 months ago, # ^ |   +2 Same, I had problems with B corner cases and I didn't bother reading C because there was little time left. After the end of the contest I coded C in literally 5 minutes.
•  » » » 3 months ago, # ^ |   +1 Same situation :(
 » 3 months ago, # |   +1 Why is the system testing happening so slow?
•  » » 3 months ago, # ^ |   +3 I think is due to the many submissions for problem A.
 » 3 months ago, # |   0 pretest 5 in B? Coldnt pass it
•  » » 3 months ago, # ^ |   +4 Case when y is not divisible by x.
 » 3 months ago, # |   +44 Am I the only one who really loves math problems?) Thanks to authors, problems were really nice, though harder than ussual.
 » 3 months ago, # |   +28 The math skills...
 » 3 months ago, # |   +5 The amount of number theory and partial sums is strong with this one.
 » 3 months ago, # |   +16 What could the test case 63 be for Div2 C?...I see many WA's on that test (including mine).
•  » » 3 months ago, # ^ |   +16 x is multiple of 1000000007
•  » » » 3 months ago, # ^ |   -26 Such a cancer test case honestly.Bad luck keeps hitting me at contest.
•  » » » » 3 months ago, # ^ |   +50 Such a cancer comment, honestly.
•  » » » » » 3 months ago, # ^ |   +38 Sorry the community if i'm being too negative or toxic,but honestly when i failed that test i can't hold the feeling,i feel like such a loser.Again,sorry for writing a stupid comment.
•  » » » 3 months ago, # ^ |   +10
 » 3 months ago, # |   0 the writer of problem B is germa 66 fan
•  » » 3 months ago, # ^ |   0 How is problem B related to Germa 66? There's barely any backstory to the problem.
•  » » » 3 months ago, # ^ |   +3 most WA are on 66 testcase
 » 3 months ago, # |   0 Is a lot of test case the reason of this very slow system testing ?
 » 3 months ago, # |   0 In problem D, what is the maximum p, such what p/s=k exists?
•  » » 3 months ago, # ^ |   0 well i know that you could just simulate the entire problem, like iterate for i, then for j with j > i and with some optimizations like, jump over sequences of 1 and when current p is much bigger than s + (n — j) because p rises much faster than s the situation is unrecoverable so you stop the second iteration because you are sure to have no solution with current i ans j' >= current j, Getting a nlogn complexity. Now for your question the answer is s * k
•  » » » 3 months ago, # ^ |   0 1) s is not fixed. 2) If we say that s = n*max(a) and k=1e5, when p=2e18 can't exist, because all of the numbers would be 1e8, and that means 1e8^n=2e18, which is false.
•  » » 3 months ago, # ^ |   +6 You can take 108,  100300,  199700 × 1to get p = 1003·1010, s = 1003·105, k = 105.Not sure if that's the worst case, however.
•  » » 3 months ago, # ^ | ← Rev. 3 →   0 Intuition: k should be max (10^5). We would like to use a small number of numbers because otherwise, p is going to be extremely large. So we would use 2 numbers. We would like one number to have the maximum value. So the equation is (10^8*x)/(10^8+x)=k. X is slightly more than 10^5 -> maximum p is slightly more than 10^13.I didn't prove it but I think it's right and should be easy to actually prove.It could overflow even unsigned long long. I have checked that a*b < 10^y with log10(a) + log10(b) < y.Also, I've accidentally set the limit to 10^13 in my solution and it passed.UPD: yes, maybe such test is impossible to create so that's just an upper bound.
•  » » » 3 months ago, # ^ |   0 I know that's no argument, but my solution passed with 10^11 as a limit :D
•  » » » 3 months ago, # ^ |   0 I was for a minute scared, what product can be 2e18, because i used >= and not > :D
•  » » » 3 months ago, # ^ |   0 Hello Qumeric In problem C : in this solution link i have used modInverse but in this solution link i haven't because i just had to divide the variable by 2 and my numerator is already %M.... Can you please tell me why my answer was accepted in the first case and not in the second? ( M = 1000000007)
•  » » » » 3 months ago, # ^ |   0 Lets think answer is 500000004. Then before divide you should have 1000000008. But you use modulo calculations and you have 1 instead of 1000000008. If you use modulo inverse you get correct answer. But if you divide by 2 you get 0 (1/2 = 0).
•  » » » » » 3 months ago, # ^ |   0 Thank you Darui99
 » 3 months ago, # | ← Rev. 2 →   +77 Dear author(s),Thanks for including n = 0 in pretests (Problem C). Thanks for not making it hackforces and saving my rating...
 » 3 months ago, # |   0 for C, the correct formula is 2^(k+1)*x — (2^k — 1) ? [after applying proper modulo] If yes, then why is my submission giving wrong answer? 39389996
•  » » 3 months ago, # ^ |   0 Should be overflow somethere.
•  » » 3 months ago, # ^ |   +1 Take modulo of X before multiplying with 2^(k+1)
•  » » » 3 months ago, # ^ |   0 Accepted, Thanks !
•  » » » 3 months ago, # ^ |   0 Hello darkhorse7 In problem C : in this solution link i have used modInverse but in this solution link i haven't because i just had to divide the variable by 2 and my numerator is already %M.... Can you please tell me why my answer was accepted in the first case and not in the second? ( M = 1000000007)
•  » » » » 3 months ago, # ^ |   0 please attach the solution link
•  » » » » » 3 months ago, # ^ |   0 oh sorry! in this solution link i have used modInverse but in this solution link i haven't because i just had to divide the variable by 2 and my numerator is already %M.... Can you please tell me why my answer was accepted in the first case and not in the second? ( M = 1000000007)
•  » » » » » » 3 months ago, # ^ |   0 you have to print ans modulo 1000000007. so you can't simply divide by 2. read this Link
•  » » » » » » » 3 months ago, # ^ |   0 But my numerator is already % M and dividing by 2 would further reduce it then why do i again need to do %M?Please tell....
•  » » » » » » » » 3 months ago, # ^ |   0 you have to print (a/b) % m, what you are printing is (a % m) / b
•  » » » » » » » » » 3 months ago, # ^ |   0 ok Thank you
•  » » 3 months ago, # ^ |   -11 if(b == 0) return 1;if(b == 1) return a%mod; // ( not a )
 » 3 months ago, # |   +28 Yeah, now that I'm yellow I want to say that my D is wrong ):It fails for this testcase: 10 2 1 1 1 1 10 3 1 1 1 1 I think the answer is 3, but my code prints 2... I don't know how did it pass system test while failing on that simple case.I don't deserve this :'(Anyways, it gave AC 20 seconds before the end of the competition, so that was pretty cool (?
•  » » 3 months ago, # ^ |   +10 Your ac code is indeed printing 3. https://ideone.com/CHh3Yb
•  » » » 3 months ago, # ^ |   0 Well that's rare... I ran it on custom invocation and locally, and it printed 2.
•  » » 3 months ago, # ^ |   +3 Isn't 2 correct? (1, 1, 10, 3) and (10, 3, 1, 1), or am I missing something?
•  » » » 3 months ago, # ^ |   +14 Why leave (1, 10, 3, 1)?
•  » » » » 3 months ago, # ^ |   +10 Oh yes I missed that, thanks
 » 3 months ago, # |   0 How calculate lcm in Div2 B?
•  » » 3 months ago, # ^ |   +4 lcm(a, b) = a * b / gcd(a, b)
•  » » » 3 months ago, # ^ |   0 Yes it is, but it overflow in test (10^18 * 10^18 / (gcd(10^18 * 10^18)), may be another way?
•  » » » » 3 months ago, # ^ |   +5 Yes :) lcm(a, b) = a / gcd(a, b) * b
•  » » » » » 3 months ago, # ^ |   +1 OH, my math is very baad, thanks!
•  » » » » » 3 months ago, # ^ |   0 For the input 1 12 1 12Why (2,6) isn't a good solution ?
•  » » » » » » 3 months ago, # ^ |   +1 because gcd(2, 6) = 2
•  » » » » 3 months ago, # ^ |   0 The limit is 10^9. 10^9*10^9=10^18. Overflow is not a problem
•  » » » » » 3 months ago, # ^ |   0 Oh, you are right, mistake in another.
•  » » » » 3 months ago, # ^ |   0 or you can do this (a/gcd(a,b))*b
 » 3 months ago, # |   0 can anyone explain D ??
•  » » 3 months ago, # ^ |   0 p/s=k; p/s<=k; p<=s*k<=2e18, so there will be at most log_2(2e18) elements in subsegments not equal to 1.
 » 3 months ago, # | ← Rev. 3 →   +3 I fst in D in the 132nd test. However,I run this test on my own computer,it gives the right answer immediately. It makes me fuzzy. Here is my code:code link Can anyone give me a explanation?UPD： I resubmitted the same code in C++17 and C++11, both get AC. Only in C++14, I got TLE again.:(UPD2: It is due to compiler's(C++14) optimization(level 2 and above). (My undefined behaviour first, it's my fault.)
•  » » 3 months ago, # ^ |   +20 First of all, how can you run the test if the test is not fully available? :DMore to the point, LL PP = tempPro*a[j]; if(PP<0||PP%a[j]!=0||PP/a[j]!=tempPro)break; This is NOT the right way of testing for overflow. In the C++ standard, you can read that signed integer multiplication overflow causes undefined behavior, which means that you have no guarantee of what happens. It also means it might run well on your machine, but not run the same way on the judge.The proper way to test for overflow is something like this: //checks if a * b overflows long long inline bool overflows(LL a, LL b) { return a > (LLONG_MAX / b); } This avoids undefined behavior. Have a look at this submission 39391459. It's your code, but with proper overflow checking. It gets AC.P.S. I learned this the hard way. To understand how wild undefined behavior can be, I've had this assert (multiply two non-zero numbers and get a zero result) pass on some online judge: void f(long long b, long long c) { long long a = b * c; if(b && a / b != c) return; assert(b != 0 && c != 0 && a == 0); } 
•  » » » 3 months ago, # ^ |   +17 Thanks a lot.Though my rating is declined, I'm pretty happy to learn something new.
 » 3 months ago, # | ← Rev. 2 →   +2 Suppose mod is prime.We know that (1/a) % mod is equivalent to (1 * a ^ (mod — 2)).So what is (1 / (a ^ m)) % mod ? 1 * (((a ^ (mod — 2)) ^ m) find z = (a ^ m) % mod. then answer is = 1 * (z ^ (mod — 2)). Both approaches in Problem C resulted in AC. I just want to make sure if those are actually correct and if you want, you can also include the proofs.Not good at math. Only surviving by using theories and luck at appropriate places. :|
•  » » 3 months ago, # ^ | ← Rev. 2 →   +3 From the exponentialtion laws we know: (ab)c = ab·c = ac·b = (ac)b Therefore: So both approaches are fine.
 » 3 months ago, # |   0 Got an idea for E 1:58 into the competition... Damn :D I understand the normal solution, but can someone who solved this with the sqrt decomposition elaborate? I didn't understand the comment that was posted here about it :)
•  » » 3 months ago, # ^ |   +8 Most sqrt-decomposition solutions gets tle :D Idea is to make sqrt(n) blocks of size sqrt(n). If you store b[i] = prefix[i-1]-a[i] then you update, you need to decrease b[pos] and increase b[pos+1, n]. So for every block store this: all possible values of b, lazy value what is needed to be added, and some king shaman. So you need to fix the block with index i/block_size. And then for every following blocks add value to lazy, and find some shaman using lazy value and some map for all values of b.
•  » » » 3 months ago, # ^ |   0 Thought about the prefix minus value and look for zero, but got stuck on n*n solutions. Really cool! Thanks :D
•  » » 3 months ago, # ^ | ← Rev. 2 →   +8 other sqrt decomp solution: http://codeforces.com/contest/992/submission/39380451Main idea:in some block , we will keep values of form val[pos] — block_sum[pos — 1] and we sort them1) to update val[pos] = x, we update block of x only (just recalc the values)2) for query, we go through all blocks b1, b2.... bk (which takes O(k = number of blocks))Say you have sum of first p blocks. Binary search for that sum in block bp+1. If it exists in block bp+1, we have a king shaman
•  » » » 3 months ago, # ^ |   0 Wow man! This is quite amazing that this is working! Tried compiling it with std::map and got a tle. but using vector of sized 64 apparently is a gamechanger — worked with a time of 1300ms...! sorting once and doing a binary search using bit is a-bit wow haha but kudos it's amazing you got this to work.I got quite intriguied by the idea and played with it a lot ( you can see the last 50+- submissions of mine haha...), This is the best working version I got:64-decomposition + your efficient binary search + memory reuse + arrays instead of vectors. http://codeforces.com/contest/992/submission/39407122 1263 msDoes anyone have an idea why the 64 "magic" works? trying to use 256 or 512 which are closer to the sqrt(2e5) is way better complexity wise, but works like hell. Cache misses?
 » 3 months ago, # | ← Rev. 5 →   -8 Thanks for the delightful problems.
 » 3 months ago, # |   0 Did anyone else here get tle on test 132 in problem D? Here is what I did: Since the product increases very fast, for every end index I found the starting index such that p > 2e18 in by iterating over every element. Meanwhile, I updated the count of required segments. It takes at most log(2e18) time. For cases when the elements are 1, I checked in O(1). my code What can be the possible mistake?
•  » » 3 months ago, # ^ |   +6 This comment will help you.
 » 3 months ago, # |   0 Your crafting.oj.uz ratings are updated!
 » 3 months ago, # |   +3 It was one of the most interesting contests that I had participate before thanks for this great contest ^_^
 » 3 months ago, # |   +3 i was iterating over accepted submissions on the problem E and I've seen that one that i can't understand why it's not getting tle... if we have an array of zeroes and in each query we change the last element to something ...the segment tree is obviously okay but the "beriz" function seems not okay to me at least ... because its iterating over all segments that they're min is not positive and go down until the length of the segment is 1 and in my array his function i think will iterate over all elements of the array so that the order seems to be o(n*n) someone plz help me with my problem ... these code got ac so it's correct but i don't know why ... i know the solution of the problem since I've got ac !
•  » » 3 months ago, # ^ | ← Rev. 7 →   +16 His solution is O(n^2) and TL (works more than 5 minutes) on test like this:n = 1e5, q = 1e5a_i = 0p_i = 1, x_i = 0. If I'm not wrong, I guess, authors tests aren't strong enough.
•  » » 3 months ago, # ^ |   0 Shot dead!123a6bcw nice catch (your test is now #95).
 » 3 months ago, # |   0 Can someone explain algo to use in div.2 D? Seems like editorial is taking time :).
•  » » 3 months ago, # ^ |   0 An easier version that helps inspire a solution for the original problem: What if the smallest number in a[] becomes 2? That brute force tag seems fishy.
 » 3 months ago, # | ← Rev. 2 →   +11 E solution w/ parallel binary search + segment tree since only sqrt-decomp solution is revealed here:First step: Reduce the constraint a little bit — Let's say the shamans are claimed as "god-kings" if they have powers at least as much as their predecessors (instead of being exact). Note that the god-king set is a superset of the original king set, so we can check all elements of god-kings to see whether they are exactly kings.How large is the god-king set? O(lg 1e9). Why? Consider all god-kings (i) in the set, observe that power[i] > sum(power[0:i]), so the power of the next god-king must be at least sum(power[0:i]) + power[i] >= 2*power[i-1], i.e. roughly twice as powerful as the previous one (except in constant corner cases, eg: sample 2, power[0] = power[1] = 2 results in both shamans being god-kings but no.2 is not twice as powerful as the previous god-king), thus the log factor in the complexity.Now you'd just apply segment tree / BIT to support sum(power[0:i]) queries, and find the first element which is larger than sum(power[0:i]) with parallel binary search.39403776
•  » » 3 months ago, # ^ |   0 I think my solution is similar to yours . Why it gets TL at test 8 ? Thx.
•  » » » 3 months ago, # ^ | ← Rev. 3 →   +5 The segment tree query function for sum query is a bit off, it misses a line which returns the sum directly if the current segment completely lies within the current range. if(l <= Node[u].l && Node[u].r <= r) return Node[u].sum;`39407362Something it's still wrong though.Edit -- And long long. 39407764
•  » » » » 3 months ago, # ^ |   0 Oh..Thanks.I typed the wrong segment tree and i haven't noticed that . I deleted some useless optimization and gets ac. Thanks again
 » 3 months ago, # | ← Rev. 2 →   +5 i got A in 2 mins i got B in 99 mins i got C in 93 mins but wrong (sad face) i am in 6th grade
 » 3 months ago, # |   0 can anyone debug why I am getting wa in test case 133 problem DI assumed all numbers to be 1 of the array and tested in my local machine it gave me 0 only which is same as jury s answer.pls helpmy solutionhttp://codeforces.com/contest/992/submission/39416834