Codeforces Round #489 (Div.2)

6 лет назад, # ^ |

-41

is that true ??

any one mention KAN and MikeMirzayanov will have upVotes ?

KAN & MikeMirzayanov

→ Ответить

fastboot

6 лет назад, # ^ |

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.

→ Ответить

6 лет назад, # |

-27

score distribution ?

→ Ответить

stefdasca

6 лет назад, # ^ |

It will probably be announced before the contest

→ Ответить

devarshi09

6 лет назад, # ^ |

+21

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

→ Ответить

6 лет назад, # ^ |

-12

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

→ Ответить

devarshi09

6 лет назад, # ^ |

-7

well said!

→ Ответить

gop2024

6 лет назад, # ^ |

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

→ Ответить

nskybytskyi

6 лет назад, # |

+12

Хммм, у моей знакомой Насти сегодня день рождения, пойду спрошу, что ей подарили ;-)

→ Ответить

AD_GOD

6 лет назад, # |

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

→ Ответить

6 лет назад, # |

-26

Spoiler

→ Ответить

antipr000

6 лет назад, # ^ |

Do you ever get upvotes ? xD

→ Ответить

JoaoMauricio

6 лет назад, # |

+18

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

→ Ответить

des1997

6 лет назад, # ^ |

creates confusion for non followers and boring too

→ Ответить

dened

6 лет назад, # |

Раунд будет рейтинговым для всех участников из второго дивизиона. Как обычно, мы будем очень рады видеть всех участников из первого дивизиона на нашем контесте вне конкурса!

Теперь ведь раунды второго дивизиона являются рейтинговыми и для участников первого дивизиона с рейтингом до 2100 – http://codeforces.net/blog/entry/59228. Нужно поправить текст.

→ Ответить

DP_I_J

6 лет назад, # ^ |

+13

Просто теперь все считают что первый див начинается с рейтинга 2100))

→ Ответить

dened

6 лет назад, # ^ |

Я так не считаю :) – в Div1 + Div2 раунде дивизионы делятся по рейтингу 1900.

→ Ответить

MonsterInMe

6 лет назад, # |

hoping to see more of mathematics ,all time favorite GreenGrape

→ Ответить

raja1999

6 лет назад, # ^ |

Your wish came true :)

→ Ответить

MonsterInMe

6 лет назад, # ^ |

true...:D

→ Ответить

mahade31

6 лет назад, # |

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

→ Ответить

Bisnu

6 лет назад, # |

Expecting a good contest....

→ Ответить

aman28rwt

6 лет назад, # |

Score distribution?

→ Ответить

just9n

6 лет назад, # ^ |

Updated. Check now.

→ Ответить

aman28rwt

6 лет назад, # ^ |

Yeah, got it. Thanks

→ Ответить

I_Love_Diashka

6 лет назад, # |

Too keked

→ Ответить

GugaKatamadzeALT

6 лет назад, # |

-10

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

→ Ответить

KAN

6 лет назад, # ^ |

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

→ Ответить

GugaKatamadzeALT

6 лет назад, # ^ |

Understood,thank you!

→ Ответить

mat_v

6 лет назад, # |

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

→ Ответить

Sharon

6 лет назад, # |

+31

Wtf, math contest.

→ Ответить

kak4rot7

6 лет назад, # ^ |

:D :D

→ Ответить

Naumtsev

6 лет назад, # ^ |

It's not funny

→ Ответить

AFN

6 лет назад, # |

+84

Mathforces Round #489 (Div. 2)

→ Ответить

BohdanPastuschak

6 лет назад, # |

What is unexpected verdict when trying to hack problem C?

→ Ответить

DruuuuuuuuuuuuuuunkenDog

6 лет назад, # |

Drunken and sleepy ㅜ_ㅜ

→ Ответить

nskybytskyi

6 лет назад, # |

← Rev. 2 →

+121

Oh those wardrobes

→ Ответить

92anurag

6 лет назад, # |

How to solve div-2 B?

→ Ответить

6 лет назад, # ^ |

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

→ Ответить

92anurag

6 лет назад, # ^ |

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

→ Ответить

6 лет назад, # ^ |

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.

→ Ответить

92anurag

6 лет назад, # ^ |

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

→ Ответить

sonu628

6 лет назад, # ^ |

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

wont be second number also in form b*x

→ Ответить

6 лет назад, # ^ |

Yeah typo error Lemme edit it.

→ Ответить

tdk93

6 лет назад, # ^ |

← Rev. 2 →

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

→ Ответить

6 лет назад, # ^ |

Yes it was a typo error. Edited !

→ Ответить

illmondo

6 лет назад, # |

How to solve Div 2 B ?

→ Ответить

xuanquang1999

6 лет назад, # ^ |

← 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

→ Ответить

Mouaz_Alkhodari

6 лет назад, # ^ |

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

→ Ответить

6 лет назад, # ^ |

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.

→ Ответить

imalgoholic

6 лет назад, # ^ |

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

→ Ответить

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.

→ Ответить

imalgoholic

6 лет назад, # ^ |

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

→ Ответить

6 лет назад, # ^ |

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.

→ Ответить

imalgoholic

6 лет назад, # ^ |

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

→ Ответить

6 лет назад, # ^ |

← 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

→ Ответить

illmondo

6 лет назад, # ^ |

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

→ Ответить

6 лет назад, # ^ |

You can refer to my solution 39374707

→ Ответить

6 лет назад, # ^ |

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.

→ Ответить

joney000

6 лет назад, # ^ |

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

→ Ответить

Natori

6 лет назад, # |

+15

How to solve D?

→ Ответить

madhur4127

6 лет назад, # ^ |

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

If somebody solved like this, then please help how!

→ Ответить

Jakube

6 лет назад, # ^ |

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

→ Ответить

Natori

6 лет назад, # ^ |

Really nice and simple. Thank you!

→ Ответить

TheOneYouWant

6 лет назад, # ^ |

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.

→ Ответить

vbobrov

6 лет назад, # ^ |

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.

→ Ответить

sph_mp

6 лет назад, # |

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?

→ Ответить

TheOneYouWant

6 лет назад, # ^ |

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

→ Ответить

sph_mp

6 лет назад, # ^ |

my code output for case 1 1 1 1 is 1

what it should be?

→ Ответить

TheOneYouWant

6 лет назад, # ^ |

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

→ Ответить

VladProg

6 лет назад, # ^ |

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

→ Ответить

sph_mp

6 лет назад, # ^ |

← Rev. 2 →

oh thanks! got accepted on practice submit because of that

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

→ Ответить

BrunoPloumhans

6 лет назад, # ^ |

← Rev. 2 →

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

→ Ответить

dhruvsomani

6 лет назад, # ^ |

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

→ Ответить

georgerapeanu

6 лет назад, # ^ |

← 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

→ Ответить

BrunoPloumhans

6 лет назад, # ^ |

← Rev. 2 →

Exact.

→ Ответить

ArianB

6 лет назад, # |

-57

worst contest with no creativity

→ Ответить

6 лет назад, # |

Was E square root decomposition?

→ Ответить

Juve45

6 лет назад, # ^ |

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

→ Ответить

gop2024

6 лет назад, # ^ |

← Rev. 2 →

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

→ Ответить

6 лет назад, # ^ |

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

→ Ответить

chemthan

6 лет назад, # ^ |

+51

Of course, No :)

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

→ Ответить

nima10khodaveisi

6 лет назад, # ^ |

can you explain more ?

→ Ответить

chemthan

6 лет назад, # ^ |

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

→ Ответить

pajenegod

6 лет назад, # ^ |

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.

→ Ответить

fsociety00

6 лет назад, # ^ |

← Rev. 3 →

chemthan Could you please explain this in brief?

→ Ответить

chemthan

6 лет назад, # ^ |

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.

→ Ответить

taran_1407

6 лет назад, # ^ |

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

→ Ответить

6 лет назад, # ^ |

Super tight time limit :D

→ Ответить

taran_1407

6 лет назад, # ^ |

I regret wasting time on D now :(

→ Ответить

NIKABB_IS_N00B_LIKE_ME

6 лет назад, # |

Guys look at last two places :o

→ Ответить

Vsevolod_Kaplin

6 лет назад, # ^ |

You were trying to reach new record on Codeforses or you just like the number 228? (Or it's the result of competition between two brothers?).

→ Ответить

6 лет назад, # |

pretest #12 of C? any idea?

→ Ответить

Natori

6 лет назад, # ^ |

Overflow

→ Ответить

teja349

6 лет назад, # |

← Rev. 3 →

PS: Found mistake . It doesnt work, Sorry

→ Ответить

Tremor

6 лет назад, # |

+29

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

→ Ответить

6 лет назад, # |

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

→ Ответить

deepak1527

6 лет назад, # ^ |

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

→ Ответить

parth

6 лет назад, # ^ |

Overflow most probably.

→ Ответить

AdrienVannson

6 лет назад, # ^ |

Overflow in Python?

→ Ответить

des1997

6 лет назад, # ^ |

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

→ Ответить

Kelang

6 лет назад, # ^ |

Huh?

→ Ответить

neckbotov

6 лет назад, # ^ |

Maybe your program prints negative number?

→ Ответить

6 лет назад, # ^ |

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

→ Ответить

neckbotov

6 лет назад, # ^ |

Got it. Hmm, everything seems OK.

→ Ответить

dush1729

6 лет назад, # ^ |

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

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

→ Ответить

6 лет назад, # ^ |

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

→ Ответить

AliZainAldeen

6 лет назад, # |

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

→ Ответить

JoaoMauricio

6 лет назад, # ^ |

There is a chrome extension called CF-Predictor

→ Ответить

AliZainAldeen

6 лет назад, # ^ |

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

→ Ответить

Anguei

6 лет назад, # |

← Rev. 2 →

-14

I don't like math problems.

→ Ответить

salvois

6 лет назад, # |

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

→ Ответить

6 лет назад, # ^ |

+26

Programming contest are half logics and half maths.

→ Ответить

6 лет назад, # |

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

→ Ответить

6 лет назад, # ^ |

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.

→ Ответить

Doritos4

6 лет назад, # |

What was Test case 4 for C?

→ Ответить

dhruvsomani

6 лет назад, # ^ |

← Rev. 2 →

k = 0, I think.

→ Ответить

send_n0des

6 лет назад, # ^ |

i guess its y := 0

ans should be (x<<1)%M

→ Ответить

6 лет назад, # ^ |

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

→ Ответить

Doritos4

6 лет назад, # ^ |

Darn. I missed ONE mod sign :(

→ Ответить

prathmesh_01

6 лет назад, # ^ |

it was x=0 i think;(

→ Ответить

Jynx

6 лет назад, # ^ |

That was test case = 9

→ Ответить

fallacy

6 лет назад, # |

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

→ Ответить

cannabutter

6 лет назад, # ^ |

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

→ Ответить

madhur4127

6 лет назад, # ^ |

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

→ Ответить

....

6 лет назад, # |

It sucks when you spend all your time thinking about the solution, and then find out later that the solution(s) are googlable :/

→ Ответить

hackerwizard

6 лет назад, # |

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?

→ Ответить

EliasMera

6 лет назад, # ^ |

Just the 1st one

→ Ответить

C137

6 лет назад, # |

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

→ Ответить

Jakube

6 лет назад, # ^ |

No, that it.

→ Ответить

hackerwizard

6 лет назад, # ^ |

I did the same thing.

→ Ответить

6 лет назад, # ^ |

I did the same but i messed up somewhere.

→ Ответить

C137

6 лет назад, # ^ |

It seems like I also had some bugs :(

→ Ответить

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

6 лет назад, # |

+16

RIP ratings.

→ Ответить

GNAQ

6 лет назад, # |

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

→ Ответить

GNAQ

6 лет назад, # |

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

→ Ответить

anjali1233

6 лет назад, # |

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?

→ Ответить

ninetailfox

6 лет назад, # ^ |

your code link ??

→ Ответить

anjali1233

6 лет назад, # ^ |

← Rev. 2 →

→ Ответить

6 лет назад, # ^ |

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

→ Ответить

anjali1233

6 лет назад, # ^ |

can you explain more why that obvious?

→ Ответить

6 лет назад, # ^ |

← Rev. 2 →

-18

→ Ответить

6 лет назад, # ^ |

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.

→ Ответить

6 лет назад, # ^ |

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?

→ Ответить

6 лет назад, # ^ |

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

→ Ответить

6 лет назад, # ^ |

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.

→ Ответить

johnhoth

6 лет назад, # |

+23

Спасибо Димону за раунд. Задачи очень жосские. Возьмите мое пятое питание, только бы он делал еще раунды.

→ Ответить

_tintin_

6 лет назад, # |

+13

div2B was not made for div2B.

→ Ответить

HanaElhami

6 лет назад, # |

Problem E was really nice.

→ Ответить

Workforces

6 лет назад, # ^ |

Because you solved it :D

→ Ответить

HanaElhami

6 лет назад, # ^ |

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

→ Ответить

....

6 лет назад, # ^ |

← Rev. 2 →

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

→ Ответить

6 лет назад, # |

How to solve DIV2 C?

→ Ответить

6 лет назад, # ^ |

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

→ Ответить

6 лет назад, # ^ |

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

→ Ответить

6 лет назад, # ^ |

Most likely overflow.

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

→ Ответить

6 лет назад, # ^ |

Thanks :)

→ Ответить

6 лет назад, # ^ |

Me too bro :(

→ Ответить

-_-_-

6 лет назад, # ^ |

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

→ Ответить

6 лет назад, # ^ |

← Rev. 2 →

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

→ Ответить

Gannu_raj

6 лет назад, # ^ |

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

→ Ответить

ameya

6 лет назад, # ^ |

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

→ Ответить

-_-_-

6 лет назад, # |

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

→ Ответить

johnhoth

6 лет назад, # ^ |

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

→ Ответить

T1duS

6 лет назад, # |

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 ?

→ Ответить

kr_abhinav

6 лет назад, # ^ |

← Rev. 3 →

5 2

1 1 2 1 1

Your solution fails on this case, ans should be 3

→ Ответить

xuanquang1999

6 лет назад, # |

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

→ Ответить

6 лет назад, # ^ |

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

→ Ответить

xuanquang1999

6 лет назад, # ^ |

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.

→ Ответить

Jeel_Vaishnav

6 лет назад, # |

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

→ Ответить

VijiZa

6 лет назад, # |

What was test case 5 for c?

→ Ответить

6 лет назад, # ^ |

x==0

→ Ответить

6 лет назад, # ^ |

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

→ Ответить

6 лет назад, # ^ |

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

→ Ответить

amulyagaur_111

6 лет назад, # |

+10

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

→ Ответить

6 лет назад, # ^ |

How to modify it to include the range specification?

→ Ответить

Sharon

6 лет назад, # ^ |

← 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

→ Ответить

alwerty

6 лет назад, # ^ |

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

→ Ответить

bira37

6 лет назад, # ^ |

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

→ Ответить

6 лет назад, # ^ |

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

→ Ответить

6 лет назад, # |

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

→ Ответить

dzyura_christopher

6 лет назад, # ^ |

probably x = 0, I completely forgot about it

→ Ответить

6 лет назад, # ^ |

i think thats problem c

→ Ответить

dzyura_christopher

6 лет назад, # ^ |

sorry, i misread your comment

→ Ответить

6 лет назад, # ^ |

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

→ Ответить

DonMichaelCorleone

6 лет назад, # |

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

→ Ответить

alwerty

6 лет назад, # ^ |

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.

→ Ответить

Single_Ready_To_Mingle

6 лет назад, # ^ |

Same situation :(

→ Ответить

6 лет назад, # |

Why is the system testing happening so slow?

→ Ответить

EliasMera

6 лет назад, # ^ |

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

→ Ответить

OptxPrime

6 лет назад, # |

pretest 5 in B? Coldnt pass it

→ Ответить

6 лет назад, # ^ |

Case when y is not divisible by x.

→ Ответить

6 лет назад, # |

+44

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

→ Ответить

CarlosGoogles

6 лет назад, # |

+28

The math skills...

→ Ответить

6 лет назад, # |

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

→ Ответить

raja1999

6 лет назад, # |

+16

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

→ Ответить

6 лет назад, # ^ |

+16

x is multiple of 1000000007

→ Ответить

LuckStillWins

6 лет назад, # ^ |

-26

Such a cancer test case honestly.

Bad luck keeps hitting me at contest.

→ Ответить

6 лет назад, # ^ |

+50

Such a cancer comment, honestly.

→ Ответить

LuckStillWins

6 лет назад, # ^ |

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

→ Ответить

just9n

6 лет назад, # ^ |

+10

spj_29

→ Ответить

Jhin

6 лет назад, # |

the writer of problem B is germa 66 fan

→ Ответить

Ahmad

6 лет назад, # ^ |

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

→ Ответить

Jhin

6 лет назад, # ^ |

most WA are on 66 testcase

→ Ответить

Kasapoglu

6 лет назад, # |

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

→ Ответить

6 лет назад, # |

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

→ Ответить

AlexArdelean

6 лет назад, # ^ |

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

→ Ответить

6 лет назад, # ^ |

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.

→ Ответить

Benq

6 лет назад, # ^ |

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.

→ Ответить

Qumeric

6 лет назад, # ^ |

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

→ Ответить

Mucosolvan

6 лет назад, # ^ |

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

→ Ответить

6 лет назад, # ^ |

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

→ Ответить

6 лет назад, # ^ |

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)

→ Ответить

Darui99

6 лет назад, # ^ |

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

→ Ответить

Jostic11

6 лет назад, # |

← Rev. 2 →

Ребят у меня в D Ошибка исполнения на тесте 132.. кто знает почему?? Изменил константу inf с 3*10^18 на 10^18 и зашло.. как такое может быть..?

→ Ответить

_Dark_Shadow_

6 лет назад, # |

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

→ Ответить

TMHMR

6 лет назад, # |

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

→ Ответить

6 лет назад, # ^ |

Should be overflow somethere.

→ Ответить

6 лет назад, # ^ |

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

→ Ответить

6 лет назад, # ^ |

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)

→ Ответить

6 лет назад, # ^ |

please attach the solution link

→ Ответить

6 лет назад, # ^ |

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)

→ Ответить

6 лет назад, # ^ |

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

→ Ответить

6 лет назад, # ^ |

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

→ Ответить

6 лет назад, # ^ |

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

→ Ответить

Daniar

6 лет назад, # ^ |

-11

if(b == 0) return 1;

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

→ Ответить

mredigonda

6 лет назад, # |

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

→ Ответить

amnesiac_dusk

6 лет назад, # ^ |

+10

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

→ Ответить

mredigonda

6 лет назад, # ^ |

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

→ Ответить

Nanami_chan

6 лет назад, # ^ |

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

→ Ответить

Ashishgup

6 лет назад, # ^ |

+14

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

→ Ответить

Nanami_chan

6 лет назад, # ^ |

+10

Oh yes I missed that, thanks

→ Ответить

6 лет назад, # |

How calculate lcm in Div2 B?

→ Ответить

312352145215

6 лет назад, # ^ |

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

→ Ответить

6 лет назад, # ^ |

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

→ Ответить

312352145215

6 лет назад, # ^ |

Yes :)

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

→ Ответить

6 лет назад, # ^ |

OH, my math is very baad, thanks!

→ Ответить

Kyochi

6 лет назад, # ^ |

For the input 1 12 1 12

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

→ Ответить

312352145215

6 лет назад, # ^ |

because gcd(2, 6) = 2

→ Ответить

Diegogrc

6 лет назад, # ^ |

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

→ Ответить

6 лет назад, # ^ |

Oh, you are right, mistake in another.

→ Ответить

travelers

6 лет назад, # ^ |

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

→ Ответить

acIN1go

6 лет назад, # |

can anyone explain D ??

→ Ответить

6 лет назад, # ^ |

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.

→ Ответить

calabash_boy

6 лет назад, # |

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

→ Ответить

mouse_wireless

6 лет назад, # ^ |

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

→ Ответить

calabash_boy

6 лет назад, # ^ |

+17

Thanks a lot.

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

→ Ответить

_Dark_Shadow_

6 лет назад, # |

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

→ Ответить

Jakube

6 лет назад, # ^ |

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

→ Ответить

kessido

6 лет назад, # |

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

→ Ответить

6 лет назад, # ^ |

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.

→ Ответить

kessido

6 лет назад, # ^ |

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

→ Ответить

Laiu

6 лет назад, # ^ |

← 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

→ Ответить

kessido

6 лет назад, # ^ |

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?

→ Ответить

CodingKnight

6 лет назад, # |

← Rev. 5 →

-8

Thanks for the delightful problems.

→ Ответить

ak532

6 лет назад, # |

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?

→ Ответить

Workforces

6 лет назад, # ^ |

This comment will help you.

→ Ответить

prakhar897

6 лет назад, # |

In problem C(div2),is there any rule of thumb while taking modulo.Where should i put modulo and when.Also some people took x%mod and k%(mod-1).Taking k%mod gives incoorect answer.Can anyone explain.

→ Ответить

Uzumaki_Narutoo

6 лет назад, # |

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

→ Ответить

Zeus726

6 лет назад, # |

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 !

→ Ответить