Codeforces Round #489 (Div.2)

7 years ago, # ^ |

-41

is that true ??

any one mention KAN and MikeMirzayanov will have upVotes ?

KAN & MikeMirzayanov

→ Reply

fastboot

7 years ago, # ^ |

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.

→ Reply

7 years ago, # |

-27

score distribution ?

→ Reply

stefdasca

7 years ago, # ^ |

It will probably be announced before the contest

→ Reply

devarshi09

7 years ago, # ^ |

+21

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

→ Reply

7 years ago, # ^ |

-12

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

→ Reply

devarshi09

7 years ago, # ^ |

-7

well said!

→ Reply

gop2024

7 years ago, # ^ |

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

→ Reply

AD_GOD

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

→ Reply

7 years ago, # |

-26

Spoiler

→ Reply

antipr000

7 years ago, # ^ |

Do you ever get upvotes ? xD

→ Reply

JoaoMauricio

7 years ago, # |

+18

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

→ Reply

des1997

7 years ago, # ^ |

creates confusion for non followers and boring too

→ Reply

MonsterInMe

7 years ago, # |

hoping to see more of mathematics ,all time favorite GreenGrape

→ Reply

raja1999

7 years ago, # ^ |

Your wish came true :)

→ Reply

MonsterInMe

7 years ago, # ^ |

true...:D

→ Reply

mahade31

7 years ago, # |

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

→ Reply

Bisnu

7 years ago, # |

Expecting a good contest....

→ Reply

aman28rwt

7 years ago, # |

Score distribution?

→ Reply

just9n

7 years ago, # ^ |

Updated. Check now.

→ Reply

aman28rwt

7 years ago, # ^ |

Yeah, got it. Thanks

→ Reply

I_Love_Diashka

7 years ago, # |

Too keked

→ Reply

GugaKatamadzeALT

7 years ago, # |

-10

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

→ Reply

KAN

7 years 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 10⁹ + 7.

→ Reply

GugaKatamadzeALT

7 years ago, # ^ |

Understood,thank you!

→ Reply

mat_v

7 years ago, # |

← Rev. 3 →

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.

→ Reply

Sharon

7 years ago, # |

+31

Wtf, math contest.

→ Reply

kak4rot7

7 years ago, # ^ |

:D :D

→ Reply

Naumtsev

7 years ago, # ^ |

It's not funny

→ Reply

AFN

7 years ago, # |

+84

Mathforces Round #489 (Div. 2)

→ Reply

BohdanPastuschak

7 years ago, # |

What is unexpected verdict when trying to hack problem C?

→ Reply

DruuuuuuuuuuuuuuunkenDog

7 years ago, # |

Drunken and sleepy ㅜ_ㅜ

→ Reply

nika-skybytska

7 years ago, # |

← Rev. 2 →

+121

Oh those wardrobes

→ Reply

92anurag

7 years ago, # |

How to solve div-2 B?

→ Reply

7 years ago, # ^ |

← Rev. 2 →

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.

→ Reply

92anurag

7 years ago, # ^ |

I kind of used the same logic, if possible can you please tell why is this solution failing. http://codeforces.net/contest/992/submission/39386988

→ Reply

7 years ago, # ^ |

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.

→ Reply

92anurag

7 years ago, # ^ |

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

→ Reply

sonu628

7 years ago, # ^ |

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

wont be second number also in form b*x

→ Reply

7 years ago, # ^ |

Yeah typo error Lemme edit it.

→ Reply

tdk93

7 years ago, # ^ |

← Rev. 2 →

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

→ Reply

7 years ago, # ^ |

Yes it was a typo error. Edited !

→ Reply

illmondo

7 years ago, # |

How to solve Div 2 B ?

→ Reply

xuanquang1999

7 years ago, # ^ |

← Rev. 2 →

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 $\text{[math]}$ , $\text{[math]}$ , $\text{[math]}$ . 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 $\text{[math]}$ satisfy all the condition above.

My implementation

→ Reply

Mouaz_Alkhodari

7 years ago, # ^ |

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 implementation

→ Reply

7 years ago, # ^ |

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.

→ Reply

imalgoholic

7 years ago, # ^ |

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

→ Reply

7 years ago, # ^ |

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.

→ Reply

imalgoholic

7 years ago, # ^ |

Yeah. Sorry that was a stupid question! By the way, can you explain the case for 0. why would it be 0?

→ Reply

7 years ago, # ^ |

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.

→ Reply

imalgoholic

7 years ago, # ^ |

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

→ Reply

7 years ago, # ^ |

← Rev. 3 →

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

→ Reply

illmondo

7 years ago, # ^ |

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

→ Reply

7 years ago, # ^ |

You can refer to my solution 39374707

→ Reply

7 years ago, # ^ |

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.

→ Reply

joney000

7 years ago, # ^ |

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

→ Reply

Natori

7 years ago, # |

+15

How to solve D?

→ Reply

madhur4127

7 years ago, # ^ |

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

If somebody solved like this, then please help how!

→ Reply

Jakube

7 years 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·10¹⁸). This will have runtime $\text{[math]}$ .

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

→ Reply

Natori

7 years ago, # ^ |

Really nice and simple. Thank you!

→ Reply

TheOneYouWant

7 years ago, # ^ |

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.

→ Reply

vbobrov

7 years ago, # ^ |

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.

→ Reply

sph_mp

7 years ago, # |

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?

→ Reply

TheOneYouWant

7 years ago, # ^ |

← Rev. 2 →

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.

→ Reply

sph_mp

7 years ago, # ^ |

my code output for case 1 1 1 1 is 1

what it should be?

→ Reply

TheOneYouWant

7 years ago, # ^ |

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

→ Reply

VladProg

7 years ago, # ^ |

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 (10⁹·10⁹ = 10¹⁸ > maximum value of int).

For example:

test case: 1000000000 1000000000 1000000000 1000000000
correct answer: 1
your output: 0

→ Reply

sph_mp

7 years ago, # ^ |

← Rev. 2 →

oh thanks! got accepted on practice submit because of that

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

→ Reply

BrunoPloumhans

7 years ago, # ^ |

← Rev. 2 →

Pro tip: write #define int long long at the beginning of every solution and use signed main().

→ Reply

dhruvsomani

7 years ago, # ^ |

What's the difference between int main() and signed main()?

→ Reply

georgerapeanu

7 years ago, # ^ |

← Rev. 2 →

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

→ Reply

BrunoPloumhans

7 years ago, # ^ |

← Rev. 2 →

Exact.

→ Reply

ArianB

7 years ago, # |

-57

worst contest with no creativity

→ Reply

7 years ago, # |

Was E square root decomposition?

→ Reply

Juve45

7 years ago, # ^ |

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

→ Reply

gop2024

7 years ago, # ^ |

← Rev. 2 →

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

→ Reply

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

→ Reply

chemthan

7 years ago, # ^ |

+51

Of course, No :)

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

→ Reply

nima10khodaveisi

7 years ago, # ^ |

can you explain more ?

→ Reply

chemthan

7 years ago, # ^ |

+11

It likes fibonacci sequence, there are little terms ≤ 10⁹. So what you need to do is just pick the maximum until it less than or equals 0.

→ Reply

pajenegod

7 years ago, # ^ |

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 a_j ≥ 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 a_j should double in size (not Fibonacci) for each iteration, and all of the segment tree operations will run in $\text{[math]}$ time so my solution should run in $\text{[math]}$ . 39387502.

→ Reply

fsociety00

7 years ago, # ^ |

← Rev. 3 →

chemthan Could you please explain this in brief?

→ Reply

chemthan

7 years ago, # ^ |

Assuming i₁ < i₂ < ... < i_k are all positions d such that a_d > a₁ + a₂ + ... + a_d - 1. Then obviously a_{i_c} ≥ a_i₁ + a_i₂ + ... + a_{i_c - 1} + 1. We have: a_i₁ ≥ 0, a_i₂ ≥ 1, a_i₃ ≥ 2, a_i₄ ≥ 4, .... Because a_i ≤ 10⁹ so the number of terms k is not big.

Then let f_d = a_d - a_d - 1 - a_d - 2... - a₁, using a segment tree to get all d s.t. f_d ≥ 0. The number of d s.t. f_d > 0 is less than log₂(10⁹) so each query we get out at most that number until f_d ≤ 0.

→ Reply

taran_1407

7 years ago, # ^ |

Hey My square root decomposition solution 39389380 passed after contest. (missed submitting during contest by 1 minute). Have a look.

→ Reply

7 years ago, # ^ |

Super tight time limit :D

→ Reply

taran_1407

7 years ago, # ^ |

I regret wasting time on D now :(

→ Reply

teja349

7 years ago, # |

← Rev. 3 →

PS: Found mistake . It doesnt work, Sorry

→ Reply

Tremor

7 years ago, # |

+29

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

→ Reply

7 years ago, # |

← Rev. 3 →

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.

→ Reply

deepak1527

7 years ago, # ^ |

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

→ Reply

parth

7 years ago, # ^ |

Overflow most probably.

→ Reply

AdrienVannson

7 years ago, # ^ |

Overflow in Python?

→ Reply

des1997

7 years ago, # ^ |

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

→ Reply

Kelang

7 years ago, # ^ |

Huh?

→ Reply

neckbotov

7 years ago, # ^ |

Maybe your program prints negative number?

→ Reply

7 years ago, # ^ |

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

→ Reply

neckbotov

7 years ago, # ^ |

Got it. Hmm, everything seems OK.

→ Reply

dush1729

7 years ago, # ^ |

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

This is wrong. Only if x==0 is required.

→ Reply

7 years ago, # ^ |

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

→ Reply

AliZainAldeen

7 years ago, # |

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

→ Reply

JoaoMauricio

7 years ago, # ^ |

There is a chrome extension called CF-Predictor

→ Reply

AliZainAldeen

7 years ago, # ^ |

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

→ Reply

Anguei

7 years ago, # |

← Rev. 2 →

-14

I don't like math problems.

→ Reply

salvois

7 years ago, # |

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

→ Reply

7 years ago, # ^ |

+26

Programming contest are half logics and half maths.

→ Reply

7 years ago, # |

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

→ Reply

7 years ago, # ^ |

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.

→ Reply

Doritos4

7 years ago, # |

What was Test case 4 for C?

→ Reply

dhruvsomani

7 years ago, # ^ |

← Rev. 2 →

k = 0, I think.

→ Reply

send_n0des

7 years ago, # ^ |

i guess its y := 0

ans should be (x<<1)%M

→ Reply

7 years ago, # ^ |

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

→ Reply

Doritos4

7 years ago, # ^ |

Darn. I missed ONE mod sign :(

→ Reply

prathmesh_01

7 years ago, # ^ |

it was x=0 i think;(

→ Reply

Jynx

7 years ago, # ^ |

That was test case = 9

→ Reply

fallacy

7 years ago, # |

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

→ Reply

cannabutter

7 years ago, # ^ |

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

→ Reply

madhur4127

7 years ago, # ^ |

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 f₀ = x

$\text{[math]}$

answer is twice of f_n

→ Reply

hackerwizard

7 years ago, # |

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?

→ Reply

EliasMera

7 years ago, # ^ |

Just the 1st one

→ Reply

C137

7 years ago, # |

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

→ Reply

Jakube

7 years ago, # ^ |

No, that it.

→ Reply

hackerwizard

7 years ago, # ^ |

I did the same thing.

→ Reply

7 years ago, # ^ |

I did the same but i messed up somewhere.

→ Reply

C137

7 years ago, # ^ |

It seems like I also had some bugs :(

→ Reply

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

7 years ago, # |

+16

RIP ratings.

→ Reply

GNAQ

7 years ago, # |

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

→ Reply

anjali1233

7 years ago, # |

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?

→ Reply

ninetailfox

7 years ago, # ^ |

your code link ??

→ Reply

anjali1233

7 years ago, # ^ |

← Rev. 2 →

→ Reply

7 years ago, # ^ |

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

→ Reply

anjali1233

7 years ago, # ^ |

can you explain more why that obvious?

→ Reply

7 years ago, # ^ |

← Rev. 2 →

-18

→ Reply

7 years ago, # ^ |

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.

→ Reply

7 years ago, # ^ |

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?

→ Reply

7 years ago, # ^ |

← Rev. 3 →

There is a nested loop in your code:

for(int i=0;i<n;i++){
  ...;
  for(int j=i+1;j<n;j++){
    ...;
  }
}

This nested loop takes O(n²) time.

Note: For this problem, I recommend you to use set data structure.

→ Reply

7 years ago, # ^ |

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.

→ Reply

_tintin_

7 years ago, # |

+13

div2B was not made for div2B.

→ Reply

HanaElhami

7 years ago, # |

Problem E was really nice.

→ Reply

Workforces

7 years ago, # ^ |

Because you solved it :D

→ Reply

HanaElhami

7 years ago, # ^ |

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

→ Reply

....

7 years ago, # ^ |

← Rev. 2 →

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

→ Reply

7 years ago, # |

How to solve DIV2 C?

→ Reply

7 years ago, # ^ |

+15

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 $\text{[math]}$ .

By using definition of expected value, we find that the expected number of clothes after k months is $\text{[math]}$ . 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.

→ Reply

7 years ago, # ^ |

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

→ Reply

7 years ago, # ^ |

Most likely overflow.

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

→ Reply

7 years ago, # ^ |

Thanks :)

→ Reply

7 years ago, # ^ |

Me too bro :(

→ Reply

-_-_-

7 years ago, # ^ |

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

→ Reply

7 years ago, # ^ |

← Rev. 2 →

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

→ Reply

Gannu_raj

7 years ago, # ^ |

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

→ Reply

ameya

7 years ago, # ^ |

← Rev. 2 →

Let f(x, k) be the answer for input x and k.
Then we have the recurrence,
For k ≥ 1,
$\text{[math]}$
and f(x, 0) = 2x.

By induction, you get f(x, k) = 2^k + 1x - 2^k + 1.
Use repeated squaring to evaluate the powers with the right modulus.

→ Reply

-_-_-

7 years ago, # |

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

→ Reply

johnhoth

7 years ago, # ^ |

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

→ Reply

T1duS

7 years ago, # |

Forgot to take mod in C fml. Also can someone tell whats wrong with my code for D — http://codeforces.net/contest/992/submission/39387013 ?

→ Reply

kr_abhinav

7 years ago, # ^ |

← Rev. 3 →

5 2

1 1 2 1 1

Your solution fails on this case, ans should be 3

→ Reply

xuanquang1999

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

→ Reply

7 years ago, # ^ |

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

→ Reply

xuanquang1999

7 years ago, # ^ |

I didn't come up with that observation (I thought the upper bound is $\text{[math]}$ at first, so RIP). But now knowing that, I think E is also a cool problem.

→ Reply

Jeel_Vaishnav

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

→ Reply

VijiZa

7 years ago, # |

What was test case 5 for c?

→ Reply

7 years ago, # ^ |

x==0

→ Reply

7 years ago, # ^ |

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

→ Reply

7 years ago, # ^ |

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

→ Reply

amulyagaur_111

7 years ago, # |

+10

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

→ Reply

7 years ago, # ^ |

How to modify it to include the range specification?

→ Reply

Sharon

7 years ago, # ^ |

← Rev. 2 →

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

→ Reply

alwerty

7 years ago, # ^ |

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

→ Reply

bira37

7 years ago, # ^ |

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

→ Reply

7 years ago, # ^ |

← Rev. 2 →

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.

→ Reply

7 years ago, # |

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

→ Reply

dzyura_christopher

7 years ago, # ^ |

probably x = 0, I completely forgot about it

→ Reply

7 years ago, # ^ |

i think thats problem c

→ Reply

dzyura_christopher

7 years ago, # ^ |

sorry, i misread your comment

→ Reply

7 years ago, # ^ |

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

→ Reply

DonMichaelCorleone

7 years ago, # |

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

→ Reply

alwerty

7 years ago, # ^ |

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.

→ Reply

Single_Ready_To_Mingle

7 years ago, # ^ |

Same situation :(

→ Reply

7 years ago, # |

Why is the system testing happening so slow?

→ Reply

EliasMera

7 years ago, # ^ |

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

→ Reply

OptxPrime

7 years ago, # |

pretest 5 in B? Coldnt pass it

→ Reply

7 years ago, # ^ |

Case when y is not divisible by x.

→ Reply

7 years ago, # |

+44

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

→ Reply

CarlosGoogles

7 years ago, # |

+28

The math skills...

→ Reply

7 years ago, # |

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

→ Reply

raja1999

7 years ago, # |

+16

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

→ Reply

7 years ago, # ^ |

+16

x is multiple of 1000000007

→ Reply

LuckStillWins

7 years ago, # ^ |

-26

Such a cancer test case honestly.

Bad luck keeps hitting me at contest.

→ Reply

7 years ago, # ^ |

+50

Such a cancer comment, honestly.

→ Reply

LuckStillWins

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

→ Reply

just9n

7 years ago, # ^ |

+10

spj_29

→ Reply

Jhin

7 years ago, # |

the writer of problem B is germa 66 fan

→ Reply

Ahmad

7 years ago, # ^ |

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

→ Reply

Jhin

7 years ago, # ^ |

most WA are on 66 testcase

→ Reply

Kasapoglu

7 years ago, # |

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

→ Reply

7 years ago, # |

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

→ Reply

AlexArdelean

7 years ago, # ^ |

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

→ Reply

7 years ago, # ^ |

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.

→ Reply

Benq

7 years ago, # ^ |

You can take

10⁸, 100300, 199700 × 1

to get

p = 1003·10¹⁰, s = 1003·10⁵, k = 10⁵.

Not sure if that's the worst case, however.

→ Reply

Qumeric

7 years ago, # ^ |

← Rev. 3 →

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.

→ Reply

Mucosolvan

7 years ago, # ^ |

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

→ Reply

7 years ago, # ^ |

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

→ Reply

7 years ago, # ^ |

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)

→ Reply

Darui99

7 years ago, # ^ |

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

→ Reply

_Dark_Shadow_

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

→ Reply

TMHMR

7 years ago, # |

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

→ Reply

7 years ago, # ^ |

Should be overflow somethere.

→ Reply

7 years ago, # ^ |

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

→ Reply

7 years ago, # ^ |

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)

→ Reply

7 years ago, # ^ |

please attach the solution link

→ Reply

7 years ago, # ^ |

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)

→ Reply

7 years ago, # ^ |

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

→ Reply

7 years ago, # ^ |

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

→ Reply

7 years ago, # ^ |

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

→ Reply

Daniar

7 years ago, # ^ |

-11

if(b == 0) return 1;

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

→ Reply

mredigonda

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

→ Reply

amnesiac_dusk

7 years ago, # ^ |

+10

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

→ Reply

mredigonda

7 years ago, # ^ |

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

→ Reply

Nanami_chan

7 years ago, # ^ |

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

→ Reply

Ashishgup

7 years ago, # ^ |

+14

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

→ Reply

Nanami_chan

7 years ago, # ^ |

+10

Oh yes I missed that, thanks

→ Reply

7 years ago, # |

How calculate lcm in Div2 B?

→ Reply

312352145215

7 years ago, # ^ |

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

→ Reply

7 years ago, # ^ |

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

→ Reply

312352145215

7 years ago, # ^ |

Yes :)

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

→ Reply

7 years ago, # ^ |

OH, my math is very baad, thanks!

→ Reply

Kyochi

7 years ago, # ^ |

For the input 1 12 1 12

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

→ Reply

312352145215

7 years ago, # ^ |

because gcd(2, 6) = 2

→ Reply

Diegogrc

7 years ago, # ^ |

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

→ Reply

7 years ago, # ^ |

Oh, you are right, mistake in another.

→ Reply

travelers

7 years ago, # ^ |

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

→ Reply

acIN1go

7 years ago, # |

can anyone explain D ??

→ Reply

7 years ago, # ^ |

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.

→ Reply

calabash_boy

7 years ago, # |

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

→ Reply

mouse_wireless

7 years ago, # ^ |

+20

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

More 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);
}

→ Reply

calabash_boy

7 years ago, # ^ |

+17

Thanks a lot.

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

→ Reply

_Dark_Shadow_

7 years ago, # |

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

→ Reply

Jakube

7 years ago, # ^ |

← Rev. 2 →

From the exponentialtion laws we know: (a^b)^c = a^b·c = a^c·b = (a^c)^b Therefore:

$\text{[math]}$ $\text{[math]}$

So both approaches are fine.

→ Reply

kessido

7 years ago, # |

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

→ Reply

7 years ago, # ^ |

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.

→ Reply

kessido

7 years ago, # ^ |

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

→ Reply

Laiu

7 years ago, # ^ |

← Rev. 2 →

other sqrt decomp solution: http://codeforces.net/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

→ Reply

kessido

7 years ago, # ^ |

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.net/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?

→ Reply

CodingKnight

7 years ago, # |

← Rev. 5 →

-8

Thanks for the delightful problems.

→ Reply

ak532

7 years ago, # |

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?

→ Reply

Workforces

7 years ago, # ^ |

This comment will help you.

→ Reply

Uzumaki_Narutoo

7 years ago, # |

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

→ Reply

Zeus726

7 years ago, # |

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 !

→ Reply