Hello, Codeforces!

I am glad to invite everyone to participate in Codeforces Round #837 (Div. 2) , which will be held on Dec/11/2022 18:35 (Moscow time)

**Please note the unusual time!**

The round will be **rated for participants of Division 2 with a rating lower than 2100**. Division 1 participants can participate unofficially in the round.

You will be given 6 problems and 2 hours to solve them. This round was prepared by me and 4qqqq.

I'd especially like to thank:

- Aleks5d for awesome coordination of our round.
- MikeMirzayanov, for the amazing Codeforces and Polygon platforms.
- I_Remember_Olya_ashmelev, TurboPiKachu, divanik, olya.masaeva, nnv-nick, neohacker, PavelKorchagin and Kolychestiy for testing the round and providing valuable feedback.

This is my first official round on Codeforces. We are sincerely looking forward to your participation. We hope everyone will enjoy it.

The score distribution : **500 — 1000 — 1750 — 2250 — 2750 — 3500**

We wish you good luck and high rating!

**UPD1: We know about problem with C task. Now we are trying to fix it.**

waiting for the round.

ScreenCast

Egyptian Russian alliance. Hope it's gonna be a great round!

But where is "As a tester,...." comments XD

As a participant, I wish all positive delta and that there is

NOXOR problems..there is NO XOR problemsSo you want XNOR problems?

xD

NO.I meant that usually Egyptian rounds imply incomingXOR missiles.As a author... So, now "As a author" comment here. Wait for testers

Finally, a 4qqqq round! Can not wait for it <3

Heap_OverFlow Also as a author, You will enjoy the problems xD.

cap

I did A and B only they were kinda good. FSTed on C. I think pretests were

very weak? But I rewrote it and barely pass the timelimit, also many submissions following same approach ofsieving then factorizingbarely pass the TL. I wonder what is the intended solution for this problem? When will the editorial be published ?How did you approached B can you explain here please. It would be very helpful.

WOW .. Egyptian round . Good luck bro

Thanks AhmedYahia, Hope you will enjoy the problems.

As a division 5 participant, I can participate unofficially in the round.

Hope you'll prepare more interesting rounds.

As a divison 2 participant,I worship Tom66.

Good Luck EVERYONE! (◠‿◠)

CAN ANYONE RELATE ;)

NO

I mean

lol

Seriously?

Yeah bro-,-.. 1. My semester finals are from 12 December

Cheers Mate.

Cant relate more. The day after tomorrow is my exam and here I am.(Though couldn't solve sintgle problem)

After a long time. Best of luck Everyone.

After a long long break. Missed the rounds badly.

It's a long time for an Egyptian round ..

No interactive problems?

After a long time, 7 contests in 9 days. Great!

finally a contest

+

An Egyptian round !!(❁´◡`❁)

I am so excited ❤❤

Good luck everyone ;)

As an Egyptian, I hope this round isn't all about bit masks

After a long day...

This is the most anticipated contest for me, keep up _HossamYehia_ :DDD

Thanks Yossef.

My first Egyptian round (My lovely country), so i'll memorize this round, i hope +ve delta for me and everyone.

love from Egypt

Egyptian Russian alliance. Hope it's gonna be a great round!

long time no see kiddo, _HossamYehia_

Egypt <3

Morocco famous win and now Egyptian contest... African vibes coming

Finally after a long time..YAY!!!

As Egyptian I love how we are here.

I am best

ok

Can't wait for the contest. The codeforces contest creators had enough vacation :)

The contest will start at 23:35 in China:(

If I'm beginning in programmation. Should I participate or it will be too difficult for me?

It will never be difficult. You will not Learn running unless you start walking. So participate in this contest and try to solve atleast one or two problem. Best wishes.

Can't wait to see wangzheng2008's performance.

I hope this African Round is as good as they are performing in FIFA World Cup with Morocco.

Hope to become pharaon this round

Codepairses

Why does this feel like a Div 1 round or maybe it's just tough for me.

It's nothing compared to div1 rounds. You need more practice

E has a strong ROI 2015 in Arkhangelsk problem 6 vibe

Bloody Hell. What a pairful round!

Congrats man for solving 3 questions

let me guess, you forced online version of F because $$$O(mlog^2n)$$$ parallel_bs + BIT is faster than $$$O(mlogn)$$$ persistent_tree? :D

I think it's also because of easy Mo's algorithm solution.

Why only 1 second limit for problem D? Java barely passes after optimizations & 3 TLEs...

Cuz why not ?

My solution had a complexity of $$$\mathcal{O}(n^2\log{n})$$$, using LCA and dp.

Because it screws Java users... My solution is O(n^2) and it might fail on system tests.

My n^2 solution for D runs very slowly, can you tell why

How to solve B?

i was thinking in the direction that ith and (i+1)th friend must not be connected in the given m queries, though kept failing 3rd pretest

bro you leave the case of all number are same in an array, eg; 1 1 1 1 1 if n=5, 6 6 6 6 if n=4 in this case the ans = n*(n-1).(becoz for every element there in (n-1) combination for 1 there is n-1 then for n it is n*(n-1)).

I will try my best to explain what I did, So a few observations first, The permutation is 1,2,3,4....n 1) Number of subsequences starting from 'i' are n-i+1.

2) If we have a pair (1,2) that means that it includes all pairs (1,2),(1,3),(1,4)...(1,n) are included in it (because if we take any pair they will have (1,2) always). So if we have 2 inputs given as (1,2) and (1,4) so we can ignore (1,4) and take only (1,2) in consideration for calculation.

3) Now take a case like this we have only (2,3) as the pair, So when we consider subsequences starting from 1, They are: {[1],[1,2],[1,2,3],[1,2,3,4]}. Now as we have (2,3) as a pair we have to stop before 3. So we have to consider the effects of the number after 1 to get its stopping point.(once read code comments to be more clear)

4) if we only consider the pair (1,4), lets say n is 5. so the possible subsequences are 1,{1,2}, {1,2,3} == 4-1 {or b-a for a pair (a,b)}

Code With comments

SpoilerSorry If I complicated in explaining something.

Some observations:

Individually, these observations should be obvious, but this leads to the following solution:

`nextstranger`

, such that when we read a non-friend pair $$$a, b$$$ with $$$a < b$$$, we set`nextstranger[a] = min (next_stranger[a], b)`

.`nextstranger[a]`

.My submission: 184766262

I used

`non`

to refer to`nextstranger`

and`cut`

to represent the person right after the longest good subsegment ends, i.e., for a given value of $$$i$$$,`cut`

becomes the minimum of`nextstranger[i]`

and the previous`cut`

(i.e. the cutoff point for the largest good subsegment that begins at $$$i + 1$$$).can you please explain the variable cut? I couldn't understand it clearly.

When considering the largest good subsegment that begins with $$$a$$$, the variable

`cut`

represents the cutoff point, i.e., the largest good subsegment that begins with $$$a$$$ is $$$[a, cut - 1]$$$ and it has length $$$(cut - a)$$$.How do we calculate the current value of $$$cut$$$? Let $$$cut'$$$ represent the cutoff point for the largest good subsegment that begins with $$$a + 1$$$, i.e. the subsegment is $$$[a + 1, cut' - 1]$$$. Now, if $$$a$$$ knows everybody in the range $$$[a + 1, cut' - 1]$$$, then $$$cut = cut'$$$. But if not, then we should set $$$cut$$$ to be the first person in this range that $$$a$$$ does not know (which we already calculated as $$$non[a]$$$). We can cover both of these cases by simply setting $$$cut = \min (cut', non[a])$$$.

Understood thankyou!

[](https://ideone.com/fZzHMQ)

Worst contest of my life, i hate it :( T_T

me frfr.. A- easy B- meh cool C- easy, done, submitted----why does it not work!!!!! D- okay can do this, coded, submitted---- might just pass the TC,- TLE,TLE,TLE,TLE

Yeah same for me, for me, I found C difficult. WA x4 and the memory limit exceeded. Quite painful since I was expecting to solve C :(

I can't solve 1 problem

In first one I did 10 wrong submissions which takes all the time, then I realize one case of all same number was missing

Hope so To perform well enough in the next contest

+1

TL on problem C

Really upset about problem C. I had a beautiful Python/PyPy solution but it kept timing out on pretest 3 :/

This solution is too long, because lcm(a) and prod(a) can be ~ 10^(n * 9).

The included link says that that calculating the LCM this way can be O(n k), with n being the amount of numbers (10**5) and k being the amount of digits (9). So it should really pass, unless the Python implementation is inefficient.

I think the problem is doing

`math.prod(a)`

. I think the Python implementation of this function is inefficient because according to this forum thread, Python uses Karatsuba algorithm to multiply big numbers instead of a Fast Fourier Transform-method like Schönhage–Strassen algorithmThe link about LCM you used also assumes multiplication is $$$O(1)$$$ time, which is not true when your numbers are this big, so taking the LCM of the whole array like this may also be slow.

`math.prod(a)`

is so huge number...`power(10, 9 * 1e5)`

It's actually possible to get AC with your formula with some constant factor (and some other) improvements.

for example: 184805714

How was the round? I personally found it a bit hard.

Is there eratosphen's sieve solution of C?

find first 3400 prime numbers and rest is easy.

i did the same but it still failed on pretest 2 184795451

silly me,

Yes, but it will probably FST (184750417).

IdeaFind all the primes below $$$\sqrt{10^9}$$$ and factorize each $$$a_i$$$. Check if some prime occurs more than once.

UPD. It passed

Daaamn, I did exactly the same, but got TLE, so gave up on this idea: 184746680

It was a typo.

Nevermind, got the most stupid mistake ever there

What's the significance of this part of the code? How do we know for sure that this remaining part of x (if(x>1)) will be the prime number

actually never mind

There can be at most one prime divisor > $$$\sqrt{n}$$$.

Proof. Let's prove it by contradiction. Let $$$p$$$ be the first such divisor and $$$q$$$ be the second. Then the least number divisible by both $$$pq > \sqrt{n} \cdot \sqrt{n} = n$$$. Contradiction.

So this part of code is only needed if $$$x$$$ is a big prime number.

Yeah I didn't considered that case initially BTW Thanks

i did same but got tle? my solution https://codeforces.com/contest/1771/submission/184811896

I think it's because you keep all primes in map, so every incrementing of prime's count works for logn. Try to count primes under sqrt(1e9) in vector, and over sqrt(1e9) — in map, should help (Also, I would check if m[v[i]] > 1 after the prime decomposition)

Hey can you tell me the idea/proof as to why this approach works?

It would be a great help!.

[UPD : nevermind i got it, thanks.]

plz show me calculate the time limite Find all the primes below 109−−−√ and factorize each ai. Check if some prime occurs more than once. this idea

Why am i getting TLE. What's the time complexity of my code. Please tell.

codeIf $$$n$$$ is a large prime or a product of two primes $$$p, q$$$ such that $$$|p-q|$$$ is small, your factorization algorithm degenerates into $$$O(\sqrt{n})$$$ which is unable to pass.

I am so dumb that I have to nuke it with the Pollard Rho algorithm after failing 7 times, sigh~. Look my submission 184795924 when available.

I thought there are 10^8 operations at most. which can be done in 3 seconds. :/

Since you iterating over the whole array (max $$$10^5$$$) and on every iteration you are finding out the prime factors of $$$a_i$$$ (max $$$10^9$$$) in square root time.

Therefore the total time complexity is $$$O(n \sqrt{a_i})$$$, which in worst case would be over the allowed limits.

i don't no why,but i think B was

Harderthan C . :+(Tfw you nuke C with Pollard's rho algorithm and Miller-Rabin because you're too stupid to solve it normally. :cry:

Not sure of system tests though but the basic solution passed.

pseudo codeI don't think that'd work, what about this input:

SpoilerI also think so it should not work.

But let's see system tests are on now.

Also A very bad problem in a cp contest who expects one to know these heavy math number theory algorithms. It is a very bad problem

No, I'm wrong, it does pass on this input.

Oh cool!

i don't think A is that bad and also this problem doesn't require "heavy math number theory" at all

I meant C is A very bad problem :(

I feel in B, i'm trying to solve B in div1.

It really exhausted mind I guess it will not be less than *1400

I need the roadmap !!

Soooo, True This is one of the worst DIV 2

Although this was a harder div2 B, it most certainly is not on the same level as a div1 B.

I realized that it's not hard, but i didn't take it easy "D

You need to fix your contest i guess? :)

https://codeforces.com/contest/1771/submission/184796886

Any idea why

`Runtime error`

for such a code?I also got it for few of my submissions. Still couldn't find out why !

`assert(condition)`

terminates the program with exit code = 3 which results into runtime error if the condition is not true.sample explanation in B also does not have latex

Even worse than the incorrect constraints

Problem B was stolen from 652C - Foe Pairs

Btw I found editorial for 652C to be much more readable

Probably the worst contest I've ever seen.

Glanced at all problems and know how to solve them in one minute with no any interesting points.

C: know how to factorize large numbers with pollard or things?

D: very obvious and classical dp from one dimension to tree. though I dont know what's wrong with my code.

E: standard dp -- crafting the largest H C F O I D ....

F: also very standard online ds problem. I didnt get time to solve it bcz of D.

Also A and B is very terrible. It's not beginner friendly and it introduces some tricky cases to let many newbies to fail.

I can't remember the last contest with such bad quality was — I assume it should be on 2015 or before. Anyway I did not AK this contest but I got a very bad impression on the whole problemset. That's it.

I used sieve for C — worked well within the time limit.

I disagree.. The contest was good. B was very good. (It required a bit more thinking unlike usual Div 2 B where you just see the problem and start coding, also no tricky edge cases were there for me least).

Even though I wasn't able to solve C. I guess that's what makes the problem

good. Must have missed some observation.can you share your approach of B?

i was not able to implement it on time but i think we had to subtract all subarrays starting from 1 to n contianing x and y from n * (n + 1) / 2, for all unique pairs and after that we have to add those subarrays which were counted more than once. it was a question of permutation and combination i guess! i hate it :(

when you're trying to solve an A or B problem in a div2 contest, try not to make it complicated, think it in an easier way

https://codeforces.com/contest/1771/submission/184805442

If you think problem C is good bcz it checked if people with good factorization tools or not, then you should check other problem Cs in past contest rounds.

Please improve your taste before improve your rating.

I'm pretty sure that intended solution DOES NOT involve those weird factorization methods. (Although people overkilled it..but I don't care about "other" people).

It has to be simple and elegant, and such problems are really good, whose solution is actually simple yet it doesn't strike easily.

YEs exactly. Don't say a problem bad by just seeing it. There is a solution which passes within 100 ms. Try to find it rather blaming that problem man. Though I personally think time limit should have been more restricted to filter out this factorization solution. This factorization solution is seems pretty straight forward for me. Just personal opinion.

Yea within 100ms you mean these totally wrong submissions which got accepted due to the weak tests?

Just let you know, all < 100ms submissions have been hacked. I cannot learn anything from here.

The problem is if you know some fast factorization tools (like pollard-rho), you can just use it with 0 minute of thinking.

So it become kind of knowledge checking problem, if you know it, you kill it instantly, and if you don't, you will need to making observation and have more penalty then the other.

if they wanted intended to be sieve, then they should have lowered the limits, my sol just uses a extra set and doesnt pass

It was "good" because you solved it, let me guess! Segments for a B with some corner cases to think of is an utter shit for B div 2

b was also very https://codeforces.com/contest/652/problem/C

this basically sums this contest up

can't agree more... I didn't see any interesting problems in this contest

Not bad for today! Thanks _HossamYehia_!!

What was not bad ? Round has 3 nice problems with more or less short statements — A, C, F. Everything else is shit on a stick

Could have gone worse. For me, it was my first contest

How to do C? :(

Contests like these always bring my little bit hope left down, i just don't know what to say.. feeling so sad right now

Why this solution (184800271) for

Cgives WA???I am generating all prime numbers up to $$$\sqrt{10^9}$$$ because if $$$xy=z$$$ then $$$min(x,y)\leq{\sqrt{z}}$$$.

Then I am looking for two multiples of every prime number generated.

It's not enough to check until 10**4.5, you do need to check until 10**9. For example, you might have 2*192763567 and 3*192763567 in the data set (192763567 being prime).

Just check and factorize every number until sqrt(n). The number remaining would be the remainding prime!

If only F were 512MB instead of 256MB. I'm depressed... My solution using sqrt decomposition.

can u explain ur sqrt decomposition logic ?

Sory, I have just found out it's wrong.

I managed to write a solution using sqrt decomposition that passes, but just barely. I had to implement range paint using a vEB tree instead of DSU (which turned out to have a better constant factor than making the log log n faster than the inverse_ackermann n for this problem).

Explanation of the solution: Divide the array into B blocks. Then process each block individually like this: Look at each value that occurs in the array, but not in the block. Assume the left bound of some query is inside the block, and the right bound is outside the block. Then if the answer is a value that isn't in the block, it must occur an odd number of times outside the block. And which is the smallest of these for a given right bound does not depend on the left bound, since the left bound is inside the block, and the block doesn't contain the value. So by range-"painting" values you can compute the answer for every right bound, assuming the left bound is inside the block and that the answer is not a value inside the block. Range painting can be done in O(n log log n) with good constant factor using a vEB tree.

Then to answer a query, you can look only at the block corresponding to the left bound of the query. Brute force count how many occurrences there are in the range of each value that appears in the block. There are n / B values in the block, so this can be done in O(n / B * log n) time by binary searching in arrays of positions of occurrences.

Then take the minimum of this answer and the pre-computed answer for the right bound in the block.

Total running time is O(qn / B * log n + Bn log log n). Code: 184822603

Had to steal some fast IO from nor and vEB tree from mango lassi and nor to make it pass.

It was hard :D

Entire contest I was searching for some efficient solution of C, at last tried brute force and it worked. Do the brute force really for C or am I gonna get FST?

What brute force did you think of?

Weird round. D was easier than C ;_;

I came up with the solution of D, but it got the WA.

Can you please explain your logic for problem -D ?

It's midnight in most of Asia and I'm regretting my sleep.

problem a is just same as https://codeforces.com/contest/459/problem/B but with *2

When approaching problem A, if the maximum and minimum values were different, i multiplied the number of maximum and the number of minimum and multiplied by 2, and if the same, i gave n * (n — 1). Why is A wrong? https://codeforces.com/contest/1771/submission/184799055

Use long long

you mean when print the answer, 1LL * answer? the contest is closed now so i cant submit revised code.. I'm so upset. I want to raise my score but I don't know what to do

C is way too standard, but its hard to optimise your solution

got it

I guess because of overflow

I can assume, if you are working with C++ the set of numbers can be of arbitrarily large primes, thus the lcm can be as much of 10^40(each of the ~10^5 numbers are different ~10^9 primes). I don't know if this can work in python due to the bignumbers

For A if the smallest number != largest number the number of occurrence of the smallest element * the number of occurrence of the largest element * 2 ;

else if all elements are same nC2 . why won't this work .

for the second case nC2 will actually divide the answer by 2 but answer must be n*(n-1)

nc2 is if all elements are same . 2nd example case the elements were different right

no, it's not nc2 because you're not selecting two elements independently, you're choosing the second number on the basis of the constraints imposed by the first number, simply said, the first number's index could've been one of n, and the second number's index could be one of n-1, (all except the first number's index since they can't have the same index)

If all elements are same the answer is $$$n(n-1)$$$.

same as n*(n-1) == nC2

Wait, what does nC2 actually mean?

yes (* 2) for permutation . nC2 * 2 i missed this in the contest

n*(n-1) == nP2

What is nP2/nC2?!

permutations and combinations search for it

I feel that constraints on problem C should have been either tighter or looser because solutions using Sieve and then factorizing each number using a list of primes and storing number of occurrences of each factor are barely passing and even failing for a few submissions depending on how the code has been written, which isn't fair to everyone

can u share ur solution plz ? :)

I generated the list of primes up to 31622 (sqrt of 1e9), and 3401 primes are less than 31622 (I checked this after generating).

After this, I created a map, facs, to store the number of times each prime factor has occurred in the prime factorisations of the elements of the array (this will require roughly 3400 operations at max to check for each prime number less than sqrt(ai)) and then if anytime, we get that a prime p divides ai and after doing facs[p]++ if facs[p]==2, then we are done and can output yes else if we have finished traversal then we can output no.

You can check code here

How do you estimate time complexity of this? I thought of same thing but I assumed no. of operations as 3*10^3 * 10^5 (correct me if I'm wrong here). I thought that's not the number of intended operations for given Time Limit forcing me to think other ways. I tried my luck by submitting some bullshit at last moment which of-course failed

I got the same complexity, roughly 3.4*10^8 operations (you can do roughly 10^8 operations in 1 sec, so I gave it a shot), and somehow it fits in at 2.4 sec for me, which is why I feel the constraints were not fair to everyone as whether or not your code passes depends on your implementation too

It took you 2.4 sec in C++, I'm sure it won't work in Python, until they come up with solution that works with all language this is a really bad problem :(

damn, I just randomly checked 100*n pairs of indexes and if their gcd is 1 or not bc I thought it will give tle.

This doesn’t pass in python

I think it is possible to make it pass in python ... I think this user has done it.

but how does this pass? , we have 1e5 elements in the array , for every one of them we will go through 31622 numbers to check , which then becomes 1e5 * 31622 , this is 3162200000 ~~ 3e9 , so i don't get how this is not a tle , can u plz explain ?

nvm , i get it , we have 3401 primes , it becomes 3401*1e5 ~~ 3e8 :D

please tell the idea of C .. I thought sieve will simply give TLE so gave up that idea ...

C easy than A

how did u solve it ?

منو لله حسام حبيب

Porblem C explain ... Basically How to find prime factors of a number<=1e9 in log(n)?? help....

There are only 3401 primes smaller than sqrt(1e9) so you only need to check for those primes. Then, once you are done dividing by all the primes, if the number left is greater than 1 then it is another prime.

so for each no in the array if I do this .. complexity can go upto 3401*n if all the numbers are a prime bigger than sqrt(1e9) . which will be 10^8 . Why wont it give TLE ?

I feel like 10^8 operations shouldn't TLE for one second and also this problem gives 3 seconds anyway.

To be fair, I know mod is slower than the other operations, so maybe one second is cutting it close but it should be fine for 3.

Square root of 10^9 is 31622. There are atmost 3402 primes in 31622. There are 10^5 numbers and try to prime factorize by 3402 primes. Complexity O(n*3402) will pass.

i Had this silly rule till now that 10^8 give a tle .... :(

Same, I thought operations should be in order of 10^6 for a second time limit

Any idea why my solution gives TLE here

Will this pass in python as well?

I saw your solution. My question is about your inner loop which at most can run 30 times. why you did not count complexity analysis. Can you give me an explanation, please? I think the complexity of your code would be O(n*3402*30). Please explain.

No. It's always up to O(n*3402). Because of, while inner loop is true, d[i] reduce by d[i]/prime[j]. If you notice carefully you will see, middle loop up to sqrt(d[i]). So reduce d[i] always reduce middle loop.

How to do D ꒦ິ^꒦ິ

https://codeforces.com/contest/1771/submission/184787882

Anyone knows why is this wrong at pretest 3? Idea: Check all routes from one leaf to another. I could understand this getting TLE'd, but not WA

Take a look at Ticket 16607 from

CF Stressfor a counter example.Constraints on C in fact very tough. It is easy to notice that there is $$$P=3500+-$$$ primes up to $$$\sqrt{10^9}$$$. But I think a bunch of people thought that $$$O(n*P)$$$ would get tle. moreover, we have some sets or hashtables that also affect the time complexity. Also, $$$O(n*P)$$$ theoretically should get tle

I thought it will get TLE, so I didn't write it. Too bad.

Same for me, I don't recall ever seeing CF problems where the intended solution is that slow. I hope that there is a more "elegant" solution that I'm missing.

You can avoid hash table by taking a 3500 length array for storing frequency of each prime, but I agree that it was not clear that $$$3.5e8$$$ modulo operations would pass in tl.

True. I got TLE using python

great contest thx

EDIT: after VAR and discover it may be unrated contest it is second worse contest after this

Oh, in problem D, my solution works for $$$n^2\cdot26$$$, I thought it would pass, The asymptotics match, after all.

For D, I tried finding the longest palindromic subsequence for each leaf-to-leaf path.

Is this approach wrong, and if so could someone please explain why :3

My submission: https://codeforces.com/contest/1771/submission/184793847

1 1 a this should be 1

The approach shouldn't get you WA but TLE. I did the same approach and TLEed on testcase 17.

A broom shaped tree. It can be $$$O(n^3)$$$.

What is the intended solution to C?

Is it the $$$O(n \cdot \pi(\sqrt{a_i}))$$$ solution? (where $$$\pi(x)$$$ is the number of primes less than $$$x$$$) I was hesitant to submit it for some time since ~4e8 ops in 3s felt risky.

Also, I don't know if I'm just being dumb, but in E why can't we just try all horizontal parts in $$$O(n \cdot m^2)$$$ and for each check the longest possible vertical segment in O(1)?

By "check the longest possible vertical segment in O(1)" I mean:

about problem C. I was hesitating for about an hour, and only after giving up decided to submit 3e8 '/' operations and it did not TLE for some reason, still not sure why

C++ can do about 1e8 operations per sec. So 3e8 is done in 3 secs. And this is number theory, everything's faster than should be because a lot of cases are just skipped.

Good lord

I desperately tried to find a better solution and brushed off the idea that it doesn't pass because of python. Because it would be so weird to have language problems in d2C (and because I was too lazy to rewrite it today)

Also it means C was a very straightforward problem with tight constraints.

And now I see that there are only 10 successful submissions in pypy3-64 and most of them had to use some magical rho algorithm I have no idea about...

Yeah, I did same stuff in E.

For problem C, I just used Pollard-Rho, which is complexity $$$O(n\cdot (a_i)^{1/4})$$$. My submission runs in time but still takes over one second, so I wonder if there is a faster solution.

so you know that if x is not an prime number there will be a prime divisor of it <= sqrt(x) so it is max about sqrt(1e9) and the number of primes number up to sqrt(1e9) is about 3400 so you just need to fact the x by 3400 prime number

I did something very similar to yours; the technique is similar to sweepline but easier: 184788266. Funny how I solved E before C. ¯_(ツ)_/¯

Never felt so frustrated... Thank you! :|

As a participant, C and D were complete garbage

How do you do C?

I didn't solve it. I have just looked through the solutions after the contest.

D was ok, C is indeed.

D seems quite standard. But, alright, I have seen worse Ds.

idk how to solve it, i know array dp but not with tree

Well, it's quite similar. You can make transitions in the order of d[v][u], where d is the distance between v and u. If you sort all the pairs by d, you can make dp transitions, which is basically dp on array, if you know the parents of the vertices on the path

Is click here solution is too slow to pass problem C ? please check this anyone's

You are iterating over the vector v three times, all the reqd steps can be done in a single iteration while factorizing the number. Try doing that. Also the constraints are very tight, so avoid using functions.

hey can someone tell me why this gives tle:

https://codeforces.com/contest/1771/submission/184791207 i know its o(n * sqrt(N))) where N = 1e9 but what is the diffrent between this and the prime factorization approach since its also suppose to be the same complexity

sqrt 10^9 is 3x10^4, in total it can degrade to > 10^9

but people discussed above in the comments solutions that have the same complexity but it passed but maybe it fst after system test thanks anyway ps : n = 1e5, N = 1e9 just saying

In the prime factorisation approach, you only check all primes till sqrt(1e9), which comes to be around 3e3. While you are checking all numbers till sqrt(1e9).

oh my bad ! didn't consider that thanks alot

An unpleasant contest, a lot of newcomers fell for int in A, solutions on the verge of TL in C and D. When I was taught to do contests, they said it was not good to catch a constant or log, because there would be those who wrote a sloppy correct solution, but would not be able to pass it.

What is wrong with my A task submission ?

int n;

n*(n-1) is int, and overflows when $$$n=10^5$$$

Hi!! can anyone tell where can i find the editorial??

It will be uploaded in some time, be patient

https://youtu.be/OjkLLxePe6o

what is wrong with this problem B submission 184799218

Gives wrong output for below input:

Click HereI'm unable to find out why this code fails for pretest 3 for A. please help me

You're using int, the product of a and b may overflow.

This was my first contest and I was unable to find this and I submitted it 3 times with other variations. Thanks!!

Overflow if all elements are same

The result may larger than int,you should use long long

you must using

unsigned long long inttype for variable nsolution:

or

EDIT: I'm sorry, this idea won't work, since it should trigger integer overflow. It passed pretests though, but will likely FST. This is what I wrote, if anyone is interested

(but it is not supposed to pass):C does not need a sieve or anything more complicated than Euclid's GCD algorithm.

All you need to do is maintain a running LCM. Initially, the running LCM is just the first element of the array. Check the GCD of the running LCM and the next value. If the GCD is not 1, then there must be an overlapping factor between this next value and one of the earlier values (doesn't matter which), so the output is YES. Otherwise, update the running LCM (by multiplying the current running LCM with this next element that we just found to be coprime to it) and move on. If we read the entire array, and the GCD was always 1, then the output is NO.

My submission: 184790195

You can run into overflow with multiplying?

Am I missing something or is SIGNED INTEGER OVERFLOW on vacation?

lol

Hi, your LCM will overflow very very fast.

Here's a test that breaks your solution

1 10 999999937 999999929 999999893 999999883 999999797 999999761 999999757 999999751 999999751 999999757

Oh, crap, pretests didn't cover overflow. I'm sorry!

u gone now

I think this is the first time in a very long time that I only solved two problems in a Div2 round. My rating is gonna drop like a rock :(

My solution for A has fallen in the system test because i forgot to print a new line in in the case when all array is equal , i hope you can skip this mistake as it is a presentation error and it is also not included in the pretests , i was about to get back to specialist and i hope you MikeMirzayanov can consider it correct.

Same here vro

same, but it's a dumb mistake from both us and those who made pretests lol. Also, C's pretests kinda weak too.

i agree it's a dumb mistake but there should be a strong pretests so that i can look back and fix it , also it is not some corner case or overflow issues , i hope the system can consider our solutions correct

Fuck so close to solving D. It’s just going level by level and do DP.

no idea how to solve C.

You just need to know that there are O(sqrt(M) / log(M)) primes from 1 to M. Then You can just check, if there are 2 numbers that both divide a prime below sqrt(10^9) ~= 35000. Also you should divide each number on all primes below sqrt(10^9). Then you'll have either 1 or a big prime. Then check if there are 2 primes.

What is idea for D, i know solution dp n^2 for 1d array with size n and that solution must be between 2 leaves in tree but thats it.

Pretests were comparable to a steaming pile of shite

Wow!! what this pretests.

.

WTF was C?

I FSTed C 184739561 on test 16. I typoed and only factorized out 2 and 3. This passes 15 tests...

This is my first div 2 contest and I was able to solve 2 problems (system tests passed)

I solved the second problem using

`set`

and`sliding window technique`

, the solution is pretty intuitive and simple to understand, hence I thought of sharing it.184778086 is not correct

184778210 also

184766650 also

please add more tests

Problem F is a specialization of 1479D - Odd Mineral Resource. (Technically, that problem doesn't ask for the minimum value but most solutions for that problem will find the minimum anyway.)

In Odd Mineral Resource the queries are not online so parallel binary search + sweepline fenwick tree can be used, but in problem F a persistent segment tree is required. The two problems are still really similarly though

True, I forgot about that. I tried the persistent segment tree solution for Odd Mineral Resource so it was the same to me.

Weak pretest.

)

I'm just much surprised that how my solution for problem C got accepted in system testing (It shows that main tests are really weak), can anyone hack it? 184797036

Maybe your code hit the omission in making data.

Yeah I know, That's why I asked people to hack it.

Can this idea work or is just way too slow even with a better implementation? (Problem C):

https://codeforces.com/contest/1771/submission/184805467

I think approaches with sieve on Python get TLE on this problem. I also kept getting TLE during the contest. But when I re-implemented the same approach with C++, I got AC.

Thank you :)

Very weak pretests for $$$C$$$.

What would be the expected rating of the first 2 questions?

What is wrong with my solution of A? It fails on 24th test. 184739221

No clue, but I would suggest to convert all your variables to long long and submit again.

I think you need to remove the "else" from:

Thank you so much!

Is it possible to hack solutions and get points? I think I see some wrong solutions for some questions but I don't know how to hack. They just need different input.

Got TL on F in system tests. Replaced map with unordered_map, got at least 10x speed-up on test 30: before that I was getting TL on test 30, but with unordered_map it works under 150 ms. It was log(N) per query anyway, and I was still using std::map O(N) times, but changing coordinate compression container to unordered_map somehow miraculously sped up the program. Just wondering, is it okay that such a small change caused that much performance loss?

„Small change”? unordered_map is a hash map whereas map is a BST.

Yeah, but the size of the map was at most 2*10^5 (also at most 4*10^5 queries), and it shouldn't be anywhere close to time limit. As AlternatingCurrent pointed out, it seems like it is a problem from C++ standard library.

The same problem was mentioned in this blog. It seems like a problem from c++ itself :(

how to solve F?