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

CAN ANYONE RELATE ;)

NO

I mean

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

Cheers Mate.

After a long time. Best of luck Everyone.

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

+

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

Thanks Yossef.

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

I am best

ok

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!

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

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

+1

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?

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.

i did same but got tle? my solution https://mirror.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.]

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.

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.

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

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

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.

You need to fix your contest i guess? :)

https://mirror.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://mirror.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://mirror.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

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://mirror.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://mirror.codeforces.com/contest/1771/submission/184799055

Use long long

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 .

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

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

Wait, what does nC2 actually mean?

n*(n-1) == nP2

What is nP2/nC2?!

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

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.

https://mirror.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

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

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

hey can someone tell me why this gives tle:

https://mirror.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).

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

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

solution:

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

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://mirror.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 is wrong with my solution of A? It fails on 24th test. 184739221

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

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?

Main idea is that if you take xor of numbers, numbers that will appear even number of times will cancel out from xor. To find smallest odd appearing number you can just binary search for minimal i that xor of numbers less or equal than i is > 0, with segment tree. To answer queries in a segment, you can use persistent segment tree. There are also cases when xor of numbers is zero (like 1, 2, 3) but there are numbers that appear odd number of times, but it can be fixed with just mapping numbers to random 64bit numbers, and the probability of xor being zero will be very low (don't know how to prove it).

wow that's why there was mt19937 in accepted codes. thank you

Here is the proof of probability of two randomly chosen subset's xor being equal is very low.

please let me know if anything is incorrect..

Say there are

k basis elementsout of n elements in the array..claim: Then the probability of xor of two different subset being equal is ~ $$$1/2^k$$$..(note that k can be atmost 64)

~~Assume that, for first 64 numbers of array, we map them all to two powers(eg 1,2,4,8,....)...resulting in first 64 number being linearly independent to each other(ie: any of them cant be represented as xor subset of other)... and all further numbers(i>64) can always be represented as linear combination of first 64 numbers(ie: as some xor subset)...~~Directly to the proof: There are total $$$2^n$$$ subsets possible..

Thus N = $$$2^n*(2^n-1)$$$ pairs of subset..

Let Z be number of pairs of subsets with equal xor..

claim: Z = $$$2^n*(2^{n-k}-1)$$$proof:1. There are $$$2^k$$$ unique xor values out of $$$2^n$$$ subsets xors.

2. In that, each unique value is repeated exactly $$$2^{n-k}$$$ times..

refer: https://stackoverflow.com/a/72195021/15971867

\begin{Bmatrix} x_1 & x_1 & x_1 & \cdots & x_1 \cr x_2 & x_2 & x_2 & \cdots & x_2 \cr x_3 & x_3 & x_3 & \cdots & x_3 \cr \vdots & \ddots & \ddots & \ddots & \vdots \cr x_{2^k} & x_{2^k} & x_{2^k} & \cdots & x_{2^k} \cr \end{Bmatrix}

Thus number of ways in choosing pair of subset such that their xor are equal, is number of ways choosing two different subset along same row in above matrix...

(note that here each xi is the subset(xor-ed).)

There are $$$2^{n-k}$$$ elements in each row..

thus there are $$$2^{n-k}*(2^{n-k}-1)$$$ such pairs in each row, and there are $$$2^k$$$ rows, hence $$$2^k*2^{n-k}*(2^{n-k}-1)$$$ pairs total..

So, probability of choosing pair of subset with equal xor value is

P = Z/N = $$$\frac{2^n*(2^{n-k}-1)}{2^n*(2^n-1)}$$$

~= $$$2^{-k}$$$

which is very low for k = 50..

~~Note that, it seems even if we take all numbers as random from the beginning, still it works..~~So, for upto n<=64, if we choose n random numbers, then there are high chance that all of them being independent..(I dont know to prove this.)

upd: I have proved it here that If you generate some n random numbers, then atleast first 50 of them will be linearly independent of each other.. (atleast first m, with probability 2^m/2^64 in general.)

Here is the modified jiangly's solution with first 64 numbers as two powers and remaining are just filled with unused natural numbers starting from $$$2^{25}+1$$$. (i=64 to n are then shuffled to avoid hacking) ref:https://mirror.codeforces.com/contest/1771/submission/184878249

note: it is better to choose random number instead of continuous numbers, cause if you dont shuffle them, then xor of all numbers between 4k1+1(or 3) to 4k2+1(or 3) for any k1<k2 will be equal..

Also even if you shuffle, the code is prone to hacking... for example, By looking at above accepted code, it is known that there exist {$$$2^{25}$$$,$$$1$$$,$$$2^{25+1}$$$} in the array, hence for n = 65, by just choosing all 65C3 combinations in each query, one can exploit this triplet.

Hi! We know about problem with C task. Now we are trying to fix it.

solutions will be rejudged ?

Yes, some later.

All the submissions will be rejudged or just the ones which were failed?

we don't know now.

what was the issue?

some troubles with validator and tests.

Not a good contest, The time limits are absurd. The problems are weird. I literally had my heart in my mouth while systests. I think either solution should pass with ok margin or tle in pretests. Staying on the border with dumb luck passing or failing solutions doesn't make much sense.

So this passes: https://mirror.codeforces.com/contest/1771/submission/184813075

But this doesn't: https://mirror.codeforces.com/contest/1771/submission/184792445

What was the incident? Was there a problem with the tests or something?

Some submissions got FST during the system test for Time Limit. Then after finishing the system test they magically appeared to be Accepted

My submission got rejudged a few times before getting accepted, so I hope that's fixed now. It could be the invalid

`n=1`

testcase.https://mirror.codeforces.com/blog/entry/109999

Can anybody help me find out what's wrong in my solution to question A.Thanks in advance

https://mirror.codeforces.com/contest/1771/submission/184726214

Maybe in the general case output it takes it as an int. You could try to precompute the answer as a ll and then output it that way

The C++ STL count function returns an unsigned int and you need to typecast it to long long while outputting, which you didn't and so you are getting WA due to overflow

use long long

Auto comment: topic has been updated by _HossamYehia_ (previous revision, new revision, compare).BruhFor me, this round was very unusual and tricky. The problems were challenging and hard, but the contest was good. Solved B and F, but not A, C, D or E. <3

Problem B is exact copy of this problem: https://mirror.codeforces.com/contest/652/problem/C

Make this contest unrated.

Well, a lot of easy problems look same. There are not many ideas for div2A and div2B. And ofc the idea of problem B is well known. And if we made every round, where problem A or problem B is not 100% unique, unrated, there would be no rated contests

Put the damn editirial slready , pls

If my country was in World Cup Semi-finals I wouldn't care about editorial, wouldn't even do a cf contest lol

Well it wasnt at that time so

Ankara Messi bro

Dont know why people hating b imo b was very easy here is my submission link https://mirror.codeforces.com/contest/1771/submission/184805442

Have the ratings been finalised or still solutions are being rejudged?

problem D was easier than B in my opinion , i regret i didn't read it during the contest and kept trying to solve B

You're not alone regreting about that

Umm, ok, and?

"I'd especially like to thank:

MikeMirzayanov, for the amazing Codeforces and Polygon platforms."Tbey are such amazing platforms that they even remind you (pretty adamantly) to tests the inputs for inconsistencies

i

it really was a bad div for a newbie

Worst generator for C

By the way, it's harder to write the generator than to come up with this test. I think 256KB limit for the hack is sometimes tight.

I switched long long to int in problem C and it passed. :/

same

Can anyone help me with this or this submission where I got TLE for O(max(n,m)) complexity in problem B?

you are creating a vector of size 1e6 in every test case.

And also it'll give wrong answer (for m=0 atleast).

In problem C, I submitted the same code in pypy3 and pypy3 64bit but the code gave

TLE in pypy3 64bitandAC in pypy3.- Is this a problem with pypy64 bit ? why this difference happened?

Unfortunately, it was found that the validator in the problem C allowed the case n = 1. We found all the participants whose result was affected by this issue (146 in total), for them the round will be unrated. For other participants, the round remains rated.

We apologize for this incident. :'(

Ratings updated preliminary, it will be recalculated after removing the cheaters.

Instead of declaring round unrated for some people, validator should have been corrected for above mentioned case. Due to mistake in creating test cases, declaring round unrated for some participants is totally senseless.

Validator has been fixed and it affected mentioned 146 participants and their solutions have been rejudged.

I saw this kind of judgement (some participants are unrated) sometimes, but how about the case for those who have good $$$+\Delta$$$ still with some negative effected troubles? I think the participants can choose their rated/unrated, or, everyone is unrated is fair. 146 participants are not a small number to decide to make the whole round unrated.

I'm a little frustrated with problem A. I was stuck on this problem for over an hour. In the condition of the problem, 1<=n<=10^5, but the problem fails when n is an int number.

Some submission in during contest — https://mirror.codeforces.com/contest/1771/submission/184727850

Fixed (int to long long) — https://mirror.codeforces.com/contest/1771/submission/184836287

use #define int long long int

i will. But its 1<=n<=10^5

but n*(n-1) is 10^10.

So C needs a precise execution time estimation (provided that we don't use advanced number theory algorithms).

Some discussions on Codeforces about

the number of operations C++ can do per second:Blog 1

Blog 2

how to solve problem c?

just check, if there minimum 2 even numbers in the array. If so, then yes. Because a pair of even number has at least one common divisor which is 2.

Otherwise you have check with prime factorization using sieve.

Just store the primes factors of every element of the array in a map.

Every time, before storing a factor, just check whether this factor stored before or not.

If not found, then print No at the end.

If needed you can check my solution : 184772682

According to your explanation, wouldn't the time complexity be like n x |{Primes}|? What if n numbers are all large prime numbers? Could you elaborate on the time complexity aspect?