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!

I'm looking forward your participation.

**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**

Is it rated? don't downvote plz, tomorrow is my birthday

Happy BirthdayNumb in advance.Not rated for division 1.

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

Finally someone remembered to thank both KAN and MikeMirzayanov.Hoping it would be a good round after the last one.Good Luck everyone.

is that true ??

any one mention KAN and MikeMirzayanov will have upVotes ?

KAN & MikeMirzayanov

You got it wrong it's not the

namebut thethanks partfor thework they do for usin preparing contests and updating codeforces on a regular basis.score distribution ?

It will probably be announced before the contest

just saw your graph! You have my respect, mate!

we are gladiators ( like viking , icleland football team + mexicans )

well said!

Of course, it will be announced before the contest. I'm sorry, I forgot to write it in the English announcement.

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.

SpoilerUnUsual Usual contest time !

Do you ever get upvotes ? xD

I was hoping to see one thematic contest of the world cup

creates confusion for non followers and boring too

hoping to see more of mathematics ,all time favorite GreenGrape

Your wish came true :)

true...:D

Getting 502 Gateway error, hope that will be fine at contest time :)

I think they were doing some server maintenance.

Expecting a good contest....

Score distribution?

Updated. Check now.

Yeah, got it. Thanks

10 sec to go

In problem B the 2nd test case also includes the pair (2,6) and (6,2) Sorry i realize now that was my mistake

Too keked

In the problem C : Also, you should find the answer modulo 10^9+7 Can someone explain what this means,please?

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 ofAon 10^{9}+ 7.Understood,thank you!

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.

Wtf, math contest.

:D :D

It's not funny

I'm sorry. I'm quite surprised as well. I'm screwed up too.

Mathforces Round #489 (Div. 2)What is unexpected verdict when trying to hack problem C?

Drunken and sleepy ㅜ_ㅜ

Oh those wardrobes

How to solve div-2 B?

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.

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

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.

Thanks go it , i assumed lcm to be divisble by x, which was a stupidity.

`in form a*x and second is in b*y`

wont be second number also in form

`b*x`

Yeah typo error Lemme edit it.

Second is b*x. Right? Not b*y.

Yes it was a typo error. Edited !

How to solve Div 2 B ?

If

yis not divisible byx, 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 thatGCD(a',b') = 1 andLCM(a',b') =y'.This can be done by iterate over all divisor

dofy' and check if pair satisfy all the condition above.My implementation

I think its can be done just by iterate over all divisor d of y

its can be done in

`O(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 :(

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.

why min(a*x, b*x) >= l and not a*x >= l && b*x >= l ??

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.

Yeah. Sorry that was a stupid question! By the way, can you explain the case for 0. why would it be 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.

Got it Bro, Thanks :) That's what is missing in my solution, The TC 5.

thats exactly wha i did and i get wa on test 9..... https://pastebin.com/bCfGhsx6

You can refer to my solution 39374707

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.

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

How to solve D?

I thought of Divide & Conquer based solution but couldn't merge efficiently.

If somebody solved like this, then please help how!

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·10

^{18}). 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..Really nice and simple. Thank you!

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.

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.

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 result

what is wrong with the solution?

You should check the case 1 1 1 1

It 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.

my code output for case 1 1 1 1 is 1

what it should be?

Oh wait... have you checked both numbers in each pair >=l and <=r as well?

yes, i also checked that

You wrote in the program:

If a and b are too big, it can be overflow (10

^{9}·10^{9}= 10^{18}> maximum value of int).For example:

test case:

`1000000000 1000000000 1000000000 1000000000`

correct answer:

`1`

your output:

`0`

oh thanks! got accepted on practice submit because of that

that was some noob mistake :( i should check any overflow case later

Pro tip: write

`#define int long long`

at the beginning of every solution and use`signed main()`

.What's the difference between

`int main()`

and`signed main()`

?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

Exact.

worst contest with no creativity

Was E square root decomposition?

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

It's too slow solution, the same our solution worked >10 sec

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.

Of course, No :)

Idea is simple, there are not many positions that greater than sum of previous.

can you explain more ?

It likes fibonacci sequence, there are little terms ≤ 10

^{9}. So what you need to do is just pick the maximum until it less than or equals 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 indexjsuch thatj>ianda_{j}≥sum(A[:i+ 1]). Continue doing this until there is no such indexj. All of this can be done quickly using segment trees. Worst casea_{j}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.chemthan Could you please explain this in brief?

Assuming

i_{1}<i_{2}< ... <i_{k}are all positionsdsuch thata_{d}>a_{1}+a_{2}+ ... +a_{d - 1}. Then obviouslya_{ic}≥a_{i1}+a_{i2}+ ... +a_{ic - 1}+ 1. We have:a_{i1}≥ 0,a_{i2}≥ 1,a_{i3}≥ 2,a_{i4}≥ 4, .... Becausea_{i}≤ 10^{9}so the number of termskis not big.Then let

f_{d}=a_{d}-a_{d - 1}-a_{d - 2}... -a_{1}, using a segment tree to get allds.t.f_{d}≥ 0. The number ofds.t.f_{d}> 0 is less thanlog_{2}(10^{9}) so each query we get out at most that number untilf_{d}≤ 0.Hey My square root decomposition solution 39389380 passed after contest. (missed submitting during contest by 1 minute). Have a look.

Super tight time limit :D

I regret wasting time on D now :(

PS: Found mistake . It doesnt work, Sorry

It was very nice contest:::::: thanks

pretest #12 of C? any hints please verdict- WA

Edit this is the code please tell me whats wrong-http://p.ip.fi/_4l8

Update- 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.

take modulus of x by 1e9+7 after scanning input.

Overflow most probably.

Overflow in Python?

Max range of integer in python is around 10^(7000).

Huh?

Maybe your program prints negative number?

Modulus gives a positive number in python as far as I know.

Got it. Hmm, everything seems OK.

`if x==0 or x%1000000007==0:`

This is wrong. Only

`if x==0`

is required.Yes you are right. But I removed that and still WA.

Screwed with 12th test case 3 times. I just simplified my expression (may be overflow) and got AC in last 7 minutes.

when will the rating changes happen ? (sorry for bad english)

There is a chrome extension called CF-Predictor

i know about it , and i have it ,but that does not mean all of my problems(a,b) will be accepted.

I don't like math problems.

I read only A, B and C, but looked more a math contest than a programming contest to me! Thanks to the author, anyways.

Programming contest are half logics and half maths.

Managed to solve A,B,C. How to solve D?

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.

What was Test case 4 for C?

k = 0, I think.

i guess its y := 0

ans should be (x<<1)%M

Likely your program didn't pass that test case due to overflow. (That's what happened to me in the first attempt)

Darn. I missed ONE mod sign :(

I did everything right , just took 64 as 2^8 and used 2^k instead of 2k somewhere and messed up the whole thing.

it was x=0 i think;(

That was test case = 9

How was in Problem C 'n==1' solved??

Just as n==2,n==3,n==4 and so on.

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 *

xand 2x+ 1 dresses each with 50% prob. Rest is simple.This gives

f_{0}=xanswer is twice of

f_{n}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?

Just the 1st one

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???

No, that it.

I did the same thing.

I did the same but i messed up somewhere.

It seems like I also had some bugs :(

RIP ratings.

This round makes me realize how poor my math is.TAT.

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?

your code link ??

http://codeforces.com/contest/992/submission/39384811

It's kinda obvious your solution works in O(n^2) for n = 1e5. No surprise you got TL.

can you explain more why that obvious?

_

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.

Suppose there is no a[i] = 0; Then your code is simmilar to:

Still not obvious?

thanks! :) am a newbie dont know much so wasnt aware that nested loops of this sort are never fast enough

There is a nested loop in your code:

This nested loop takes

O(n^{2}) time.Note: For this problem, I recommend you to use set data structure.

thanks!

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.

really helped! thanks :)

bro you have used printf instead of scanf.....that's why tle and runtime type errors are coming.

div2B was not made for div2B.

Problem E was really nice.

Because you solved it :D

I solved D too that wasn't nice at all!

Well, you don't solve E in every contest ;p

How to solve DIV2 C?

Observe that after k months, there can be 2

^{k}*x, 2^{k}*x- 1, ... , 2^{k}*x- (2^{k}- 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. 2

^{k}(2x- 1) + 1.Note the special case: if x = 0, the answer is 0 no matter what k is.

I used the same logic still kept getting error on pretest 5. http://codeforces.com/contest/992/submission/39380228

Most likely overflow.

You should append LL to numbers you intend to be used as long long, e.g. "2LL"

Thanks :)

Me too bro :(

You have taken a negative without adding a MOD.

For solving it use

Still try to use mod after avery arithmetic operation

oh gosh!! Thank you so much for pointing it out. I had totally missed it.

F**K only because of x=0 special case I was getting WA.

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) = 2^{k + 1}x- 2^{k}+ 1.Use repeated squaring to evaluate the powers with the right modulus.

i find the penalty on re-submission kinda weird :(

Can D be solved using two pointer both starting from beginning ?

nope. The solution comes from fact "ones are useless"

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 ?

5 2

1 1 2 1 1

Your solution fails on this case, ans should be 3

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).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

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.

A lot of Maths!

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)).

What was test case 5 for c?

x==0

It should not be x == 0 as I had considered it a special case and printed 0(verifying)

Yes I'm sorry that was pretest 9. Messed up a lot today :/

Solution of problem B already exists on the internet. link : Click . Found it after the contest!

How to modify it to include the range specification?

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

That solution would give TLE because it iterates all the numbers until 1e9

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

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).

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.

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.

What is pretest 9 in D and why did it bend me over?

probably x = 0, I completely forgot about it

i think thats problem c

sorry, i misread your comment

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 ! :(

Thanks for strong pretest of Problem C. To me it was easier than Problem B.

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.

Same situation :(

Why is the system testing happening so slow?

I think is due to the many submissions for problem A.

pretest 5 in B? Coldnt pass it

Case when y is not divisible by x.

Am I the only one who really loves math problems?) Thanks to authors, problems were really nice, though harder than ussual.

The math skills...

The amount of number theory and partial sums is strong with this one.

What could the test case 63 be for Div2 C?...I see many WA's on that test (including mine).

x is multiple of 1000000007

Such a cancer test case honestly.

Bad luck keeps hitting me at contest.

Such a cancer comment, honestly.

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.

spj_29

the writer of problem B is germa 66 fan

How is problem B related to Germa 66? There's barely any backstory to the problem.

most WA are on 66 testcase

Is a lot of test case the reason of this very slow system testing ?

In problem D, what is the maximum p, such what p/s=k exists?

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

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.

You can take

^{8},to get

p= 1003·10^{10},s= 1003·10^{5},k= 10^{5}.Not sure if that's the worst case, however.

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.

I know that's no argument, but my solution passed with 10^11 as a limit :D

I was for a minute scared, what product can be 2e18, because i used >= and not > :D

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)

Let`s 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).

Thank you Darui99

Dear author(s),

Thanks for including n = 0 in pretests (Problem C). Thanks for not making it hackforces and saving my rating...

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

Should be overflow somethere.

Take modulo of X before multiplying with 2^(k+1)

Accepted, Thanks !

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)

please attach the solution link

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)

you have to print ans modulo 1000000007. so you can't simply divide by 2. read this Link

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

you have to print (a/b) % m, what you are printing is (a % m) / b

ok Thank you

if(b == 0) return 1;

if(b == 1) return a%mod; // ( not a )

Yeah, now that I'm yellow I want to say that my D is wrong ):

It fails for this testcase:

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 (?

Your ac code is indeed printing 3. https://ideone.com/CHh3Yb

Well that's rare... I ran it on custom invocation and locally, and it printed 2.

Isn't 2 correct? (1, 1, 10, 3) and (10, 3, 1, 1), or am I missing something?

Why leave (1, 10, 3, 1)?

Oh yes I missed that, thanks

How calculate lcm in Div2 B?

`lcm(a, b) = a * b / gcd(a, b)`

Yes it is, but it overflow in test (10^18 * 10^18 / (gcd(10^18 * 10^18)), may be another way?

Yes :)

`lcm(a, b) = a / gcd(a, b) * b`

OH, my math is very baad, thanks!

For the input 1 12 1 12

Why (2,6) isn't a good solution ?

because gcd(2, 6) = 2

The limit is 10^9. 10^9*10^9=10^18. Overflow is not a problem

Oh, you are right, mistake in another.

or you can do this (a/gcd(a,b))*b

can anyone explain D ??

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.

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.)

First of all, how can you run the test if the test is not fully available? :D

More to the point,

This is

NOTthe right way of testing for overflow. In the C++ standard, you can read that signed integer multiplication overflow causesundefined 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:

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:

Thanks a lot.

Though my rating is declined, I'm pretty happy to learn something new.

Suppose mod is prime.

We know that (1/a) % mod is equivalent to (1 * a ^ (mod — 2)).

So what is (1 / (a ^ m)) % mod ?

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. :|

From the exponentialtion laws we know: (

a^{b})^{c}=a^{b·c}=a^{c·b}= (a^{c})^{b}Therefore:So both approaches are fine.

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 :)

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.

Thought about the prefix minus value and look for zero, but got stuck on n*n solutions. Really cool! Thanks :D

other sqrt decomp solution: http://codeforces.com/contest/992/submission/39380451

Main idea:

in some block , we will keep values of form val[pos] — block_sum[pos — 1] and we sort them

1) 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

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 ms

Does 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?

Thanks for the delightful problems.

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?

This comment will help you.

Your crafting.oj.uz ratings are updated!

It was one of the most interesting contests that I had participate before thanks for this great contest ^_^

39389999

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 !

His solution is O(n^2) and TL (works more than 5 minutes) on test like this:

n = 1e5, q = 1e5

a_i = 0

p_i = 1, x_i = 0.

If I'm not wrong, I guess, authors tests aren't strong enough.

Shot dead!

123a6bcw nice catch (your test is now #95).

Can someone explain algo to use in div.2 D? Seems like editorial is taking time :).

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.

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

I think my solution is similar to yours . Why it gets TL at test 8 ? Thx.

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.

39407362

Something it's still wrong though.

Edit -- And long long. 39407764

Oh..Thanks.I typed the wrong segment tree and i haven't noticed that . I deleted some useless optimization and gets ac. Thanks again

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

can anyone debug why I am getting wa in test case 133 problem D

I 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 help

my solution

http://codeforces.com/contest/992/submission/39416834