<almost-copy-pasted-part>

Hello! Codeforces Round #615 (Div. 3) will start at Jan/22/2020 17:35 (Moscow time). You will be offered 6 or 7 problems (or 8) with expected difficulties to compose an interesting competition for participants with ratings up to 1600. However, all of you who wish to take part and have rating 1600 or higher, can register for the round unofficially.

The round will be hosted by rules of educational rounds (extended ACM-ICPC). Thus, during the round, solutions will be judged on preliminary tests, and after the round it will be a 12-hour phase of open hacks. I tried to make strong tests — just like you will be upset if many solutions fail after the contest is over.

You will be given 6 or 7 (or 8) problems and 2 hours to solve them.

Note that **the penalty** for the wrong submission in this round (and the following Div. 3 rounds) is **10 minutes**.

Remember that only the *trusted participants of the third division* will be included in the official standings table. As it is written by link, this is a compulsory measure for combating unsporting behavior. To qualify as a *trusted participants of the third division*, you must:

- take part in at least two rated rounds (and solve at least one problem in each of them),
- do not have a point of 1900 or higher in the rating.

**Regardless of whether you are a trusted participant of the third division or not, if your rating is less than 1600, then the round will be rated for you.**

Thanks to MikeMirzayanov for the platform, help with ideas for problems and for coordination of my work. Thanks to my good friends Daria ZeroAmbition Stepanova, Mikhail pikmike Piklyaev, Maksim Ne0n25 Mescheryakov and Ivan BledDest Androsov for help in round preparation and testing the round.

Good luck!

I also would like to say that participants who will submit wrong solutions on purpose and hack them afterwards (example) will not be shown in the hacking leaders table.

</almost-copy-pasted-part>

This is unusual, but good news! Our friends at Harbour.Space have a message for you:

*Hi Codeforces!*

*As a special prize for the Codeforces Round #615, we would like to invite the top 3 participants to take part in our Hello Muscat ICPC Programming Bootcamp, which will take place in Oman, from March 19 to March 25, 2020. The prize will cover the participation fee, accommodation, and half-board meals for the entire duration of the bootcamp (except flights)!*

**There are three requirements to satisfy:**

*You took part in at least 10 rated contests on Codeforces**Your max rating should be less than 1900**You should be eligible for ICPC and/or IOI 2020+*

*So unofficial participants are also in a game (if meet the requirements).*

*Good luck to everyone!*

**UPD**: I want to thank Artem Rox Plotkin and Dmitrii _overrated_ Umnov for invaluable help with the round preparation!

**UPD2**: Editorial is published!

First comment!!

First dislike!

Actually, you are not right. The first comment was 10 years ago when codeforces was just opened. The comment was created by VitalyPavlenko

who got First WA on test Case 5?

As far as I can tell, it was user Haleh with this submission 213

Could you also find out who got first WA on test case 100?

**hope i will be cyan after contest **

Not bad!!

thanks bro amitesh99

thanks vovuh for make me happy today

Queueeeeeeeeeeeee.

I can relate.

indeed

codeforces:Div.3 contestme: Let's get a speed performance check.Why is vovuh always in the makers of div3 rounds(This does not happen in div 2 rounds).

No complains, just curiosity.

I think that is so because vovuh started Div. 3 competitions. Not sure though....

Why someone sumbit a wrong solution on purpose then hack his solution ?

Maybe they wanted to be at the top of the hackers during the hacking phase.

if so, what they will gain ?

What will they lose either? (Don't say rating as its probably their fake ID)

Again into the ashes

I think smarter requirements are needed for prizes in order to get rid of smurfing.

15000 participants but 100 upvotes?

Hope to become cyan. Hey rising_from_the_ashes! I felt in love with your handle!

Thank you

I hope to become blue idk how the scoring works

I think you are unrated for this contest as you are not trusted participant. Read this.

my rating is <1600

but you haven't participated in more than 2 rated contest.

am I reading it wrong? if you are <1600 the contest is rated.

I'm still cyan but I made good progress

hey, you can install its browser extension so that u will get an estimate that ur rating is going to change by how much

I think I will just wait to see what happens. Though the site is very unstable currently (last round only took 2 hours for ratings to change)

The site's not unstable, this round has a hacking phase that goes on for 12 hours after the contest. As successful hacks can change the results, standings are subject to change during the phase, and thus rating is not updated because rankings can change. Rating will update (relatively) shortly after the phase ends.

the site is unstable for me as I tried to submit stuff 2 hrs ago and I was getting 502 error pages didn't last round have hacking phase too?

Want to become cyan after this round.

Just like me!

Guys! please answer me. How to tag someone by its handle in codeforces?

Thanks! But I'm not a noob, I swear!

I hope to successfully give contest in guu health and vitaliti. And hopefully get me some bobs and vagene.

.

Why i can't register now?

there is many a times constraint in CF contest that you have to register atleast 5 min before the contest start

Hey, in my test 1 in problem C, i have a correct answer, but it's WA because my a[1] and n are dupcilate. Is it a bug in my test?

Long Queue!

gg

3 minute of queueueueue

I was stuck for around 12-15 minutes.

Please do something about the long queue time. Thank you!

Queueforces!!!

I got 9 penalty.

{Deleted}

There is no reason to kill yourself right now because of some computer not working properly, you will die somewhen anyway

but the contest was extended 10 minutes

anybody know how to solve E ?

solve each column seperately. calculate how many steps of move 1 if you do k steps of move 2

But is That solution O(N^2*M) ?

Solve for each column independently. For each shift $$$0 \le s \lt n$$$, count how many numbers will match their intended positions after shifting (let it be $$$f_i$$$ for a shift by $$$i$$$).

HintYou can efficiently count that by iterating over every number in the column and determining, which shift will put it in the intended position, if it exists at all (some easy math here).

Then, for a fixed column, the answer is the minimum over all $$$n - f_i + i$$$, and the total answer is the sum of those.

How to solve C ?

Get all prime divisors of the given number. To calculate first number Fix the first number as the very first prime number.

To calculate second number: Start multiplying from next prime number onwards until the product becomes greater than first number.

To calculate third number: Product of all the remaining prime numbers.

Find all divisors of n.

Than brute over all pairs of divisors and let that number be a, b.

Than c = n/(a*b); if c is not divisible by that multiplication than don't select this pair. else you have found your answer.

My Submission

https://codeforces.com/contest/1294/submission/69364122

what is wrong in this?

How your brute force pass?

what is the maximum number of divisors a number has?

I think it will be sqrt(n). Then how your solution pass.?

To find a divisor of a number you only need to check up to sqrt n. The number of divisors does not matter since we only need 3.

no, it is cube_sqrt(n)

see this: https://codeforces.com/blog/entry/651

Any number less than $$$10^9$$$ has not more than $$$1344$$$ divisors, with $$$735134400$$$ having exactly that many. Actually, it is reasonable to estimate the number of divisors as $$$\sqrt[3]n$$$ for small numbers (even though it asymptotically grows slower than any polynomial).

The growth of highly composite numbers is interesting since it balances having many small prime factors but not too many the same https://en.wikipedia.org/wiki/Highly_composite_number

Sqrt(n) * sqrt(n) brute force My submission . Recall that you can always find pairs of factors of a composite number by iterating to sqrt(n).

Project Euler style problem! Can be done without prime divisors list. Iterate over all c for c*c <= n. If c divides n, let ab = n / c. Iterate over all b for b*b <= ab. If b divides ab, let a = ab / b. Ensure a, b, c distinct.

c is at most sqrt(n), b is at most sqrt(c), so algorithm is O(n^3/4) time

don't you think 100(no of test cases)*10^(6.5)(if every number is 1 billion) would not pass in the given time limit at it is approx. 10^8.5.

I think the estimate is conservative as most numbers will terminate much quicker (it is still good to think about worst case for hacking). But as a rule of thumb, with a fast language (C/C++) a computer can do 10^8 or 10^9 computations a second.

Simple and clear solution in

3 steps:1.findall divisors of ngreater than or equal to 2.2.brute forcethe divisors using 3 loops and check whether you can get those 3 numbers say a,b,c such that a*b*c ==n and a!=b && b!=c && a!=c .If you got these 3 numbers then flag = true and break from all three loops.3.Ifflag is truethen print yes and a,b,c else print no . for further reference see my code by clicking on C.cpp : C.cppYeah!

Greedy approach; let sq = sqrt(n) iterate i from 2 to sq, if n is divisible by i, store i in vector then divide n by i. Outside loop,if the vector size is 2 while looping, instantly break. if vector size < 2, print false. Else check if n(after loop) is not equal to numbers we push to vector and not equal to 1. If false then no, or else the answer is 2 numbers in vector and n that we get after looped.69322228

The initial observation is 2*3*4 is the minimum value from which we can have valuable answers .After skipping those , my idea is to find two numbers a,b such that a*b = n . Then find two numbers i,b such that b%i==0 and i!=a so that we can assign value of i to b and (b/i) to c .

How do you lock your submission? I could not see the lock icon anywhere on the dashboard for the problems I solved.

Submissions ran on system tests directly, so there are not pretests and options related to, like hacks and locking problem

So for this contest there was no hacking phase? Sorry to ask stupid questions but I am new to this.

Just like me boy!

Why does it say "and after the round it will be a 12-hour phase of open hacks" in the blog?

Pal, it seems that I'm wrong too!

Since I'm not an old user of codeforces, it's the first time that I experienced something like this(tooooo long quotes). I think it's not right to blame CF, 'cause I'm sure that these kind of issues are not more than fingers of hand through CF history. Any way #unrate_615

how many number of divisors number has in problem c. In worst case.

Try number 734033887

It works for 30. which has 3 distint divisors 2,3,5

srry. My mean was this case divisor of 734033887 are : {1, 5009, 146543, 734033887}; if we take 5009, 146543 as first and second value , we don't have 3'rd option to take instead of 1 which is < 2

thanks for clarification.

You have missed the case where there are only two primes and both of their power is 2. For example : 36. Your code returns NO. But there is an answer : 2, 3, 6

Haven't completely checked your code but you over-complicated the problem while the constraints aren't that big.

I simply do prime factorization of number.

Try 1 36

Answer exists 2, 3 and 6

Got my mistake thanks.

What is the 11th test in D? Why did my program fail it?

My approach for E: Process each column separately .For every column calculate cost for every possible rotation. For calculating the cost of every rotation loop through every value and find out for which rotation this element is at its correct position,and decrement the required no. of operation for that particular rotation by 1 .Choose rotation which require minimum operations .

Thanks for the contest!

when the spec is out of bounds lol

Many people failed on test 25 because of it

guys i know that my question is not related to the constest, but how can I figure out users that I'm in their friends?

you can't

Can someone help me understand where I went wrong in Problem C. My Solution Thanks in advance

Your code is too long,I think you should learn to write concise code

How to solve D?

I use std::set to matain the answer, and the code is pretty short and clear, here's my submission:69350130.

even shorter code by maintaining the count of remainders

I have absolutely the same code, and, this solution looks amazing...

cheers mate

Isn't this TLE?

it's O(qlogx).

I did something stupid but the key idea is that the values only matter mod x. So we keep counts of 0 to x-1 mod x. The MEX can be computed greedily by trying to increment MEX and decrementing counts as we go.

D was simple but little tricky for me. Let's say dp[i] contains what is the max MEX value till ith query. and let's say it is K;

Now since dp[i]=K, it implies that we were unable to generate K from previous numbers till now. So for the (i+1)th query_number we will try to generate the Number K onwards(including it) so that our max value of MEX become greater than previous and best possible till now.

Now lets say K=ax+r so K can be generated iff there exist a query_number previously of the form Z=bx+r so that you can just add or subtract +/-(a-b)x to Z depending on whether a>b or b>a in order to get K.

SO you can feel now that there is no need of actual query_number n... we just need n%x — remainder. so just create array of size x. and play with remainder...

Here is code

SpoilerMy_submission

Maintain array $$$B$$$, indexed from $$$[0, x)$$$. Initially, $$$B[i] = i$$$.

For each query, do $$$B[y_j \text{ mod } x] \text{ += } x$$$. The answer after each query is the minimum value of $$$B$$$; however finding the minimum naively would be too slow ($$$O(qx)$$$ over all queries). We could use a segment tree, or even just an ordered set (for each query, remove $$$B[i]$$$ from the set, update $$$B[i]$$$, then add it back to the set. $$$B$$$'s values would always be distinct), to reduce it to $$$O((x + q) \log x)$$$, which should pass. Do be careful about overflow; either use 64-bit integers or stop updating an index if it exceeds a threshold $$$> q$$$.

This works because it is always optimal to change each $$$y_j$$$ to the minimum possible non-negative value not already in $$$A$$$ (the array in the problem description), and $$$B[i]$$$ represents the minimum non-negative value $$$b$$$ where $$$b \text{ mod } x = i$$$ and $$$b \notin A$$$.

How to solve D?

The question becomes easy when you observe that a number when added to x or subtracted to x, it's modulo w.r.t 'x' remains the same.

Now, you just need to maintain precomputed of first % 'x' numbers, i.e from 0 to x — 1.Let's say this array as 'a'. Now, whenever a number comes. Find its modulo w.r.t 'x', and maintain a map or set, to check whether that number has come before.

if you use this number, let's say y. then increase that number in your precomputed array i.e a[y] += x.

Why? Because whenever a number will come, it will be holding place for next place of that modulo multiplicity.

I tried my best to explain to you. Take a look at my submission, you will get more idea.

My Submission

What is the time complexity of your solution in worst case?

How to try on the hack? Its showing Illegal contest ID on clicking on 'Hack it!'

I think there's no hacking phase. 'cause the solutions ran on system tests directly, and not pretests

On div3 there is always a 12-hour hacking phase

Oh, so you do not need to LOCK your solution in Div3.

Locks are available in div1/div2 contests, not in div3 contests. You can read the rules of div3 to get more information

to hack in div 3 open the solution of whom you want to hack and on the top right by clicking on "hack it" you will be directed to test case window where you can put the hack test case.

when will editorial come

Presumably sometime after the 12 hour hacking phase ends

Who can explain to me why in my solution to Problem D I have to use long long.

the code:https://codeforces.com/contest/1294/submission/69352519

Where it is mentioned in problem D that we can increase or decrease one element in an operation more than once?? I mean a[i]-m*x or a[i]+m*x is possible for m>1 also in one single operation????

In the notes describing the example

You mean in the explanation??

They didn't say you have to do only one operation. You can do operation as many times as you want.

Very similar to Problem F ?

Yes and the author is my teammate sonu628. Unfortunately I couldn't solve it. ;_;

Never mind, I could not solve it either, even after solving it in the contest. I assumed the diameter of a linear tree = n (thus WA 39) :(

Didn't expect someone will remember :)

P.S:- feeling happy ;)

Hacks for C?

In problem F, what is wrong with this approach? First, I find a diameter and choose a and b as the ends of that diameter. Then, I banned every edge between a and b and create the new graph. After that, I run DFS from every vertex between a and b. Finally, I choose c as the vertex whose depth is higher (depth 0 is also considered, in that case c is between a and b). This was my submission.

I didnt read your code but your approach is O(n^2) you can simply do a multisource bfs.

Once I have erased the edges between the nodes in the diameter, I have a forest in which I have a tree rooted on each node and running DFS from them is O(V + E)

Can you please explain your Multi-Source BFS Approach ?

Its also basically the bfs, but initially in queue you have to put all the nodes whose distance is initially 0, also make their distance 0 initially. Now in the while loop instead of queue having a single node it will have many nodes with distances 0. The time complexity is same since it traverses whole graph, maintaining correct distances i.e O(V+E) .

Now in this particular question after finding the diameter ends,for all the nodes in their path make their distance 0, and run multi-sources bfs to get the third node which is farthest from the path.

TRY this case:

12 11

1 2

2 3

3 4

1 5

5 6

6 7

1 8

8 9

9 10

8 11

8 12

I think the answer is 9 but your approach will give 10.

please ignore. my bad. your approach will also give 9

Don't worry, thanks. I got AC. The approach was right, I had a bug of using the name of the variable temp instead of diameter in my loop.

69357392 I know my code is not that clean, but please check it for my bug on B!

anyone!? ;_;

BanazadehAria please help your compatriot!!!

sorry I didn't read the B, btw what is compatriot?

Irrelevant comments: checking bounds, n=1 case, and ans=="YES" is not needed. The points can be sorted destructively. Once points are sorted lexicographically we can perform the yes/no check with one coordinate. Between two points you only need some Rs followed by some Us. idk what the last output R is.

In problem D, what does "in one move" mean? It means increase or decrease any element of the array only one time or any? I asked my friend after contest, he said any. Did i forgot something?

One move means increase/decrease one element once, but since they give you unlimited moves, you in effect can do unlimited increases/decreases.

I mean why unlimitedly moving not declared in detail?

Approach for D?

Just count remainder of X.

simplest way I can think to explain D

Exactly same as mine :)

I really liked this Div 3 round. Especially how Mathematical C and D were. And that there were only 6 distinct problems.

Agreed, I come from Project Euler background so it is familiar

Great. How many problems did you solve on Project Euler ?

Is there anyone else with E failing on Test 8 ?

how to solve E? I heard that it is greedy, but i can't understand. Why greedy works? :(

while traversing in each column(say j), if any element(x) is found which belong to column j in the final matrix. Then find no of moves required in the cyclic shift of this column so that x reaches to its correct position.

Maintain a map[mv,fre]

mv: no of moves required so that x reaches to its correct position in the cyclic shift.

fre: frequency of such elements which reaches to its correct position after mv moves in the cyclic shift.

Now, for each column min no of moves required(say min_col) is the n-max(difference between freq and mv). So the ans is sum of all min_col

For better understanding have a look

can somebody help me with the testcase on which my soln is failing

your code is printing 0 which is not allowed

hello all. My code for problem C gives the wrong answer on test case #2. Here is what I am doing: a) Find the "first" divisor of n greater than equal to 2. b) Find the "second" divisor which is not equal to the first divisor if possible. c) If possible then check if n/(first*second) is >= 2. d) If not possible then there is only one divisor >= 2 of n except itself. Then choose "second" = (first*first) and check if triplet is possible.

Please Help!![submission:69361400]

Sure, try $$$100$$$ as test case. According to your code, your first divisor is $$$2$$$ and the second one is $$$4$$$, so you check if $$$4$$$ divides $$$50$$$ and that gives you NO, you should choose a divisor after extracting the previous one. Also, your code is $$$O(t*n)$$$ and $$$n \leq 10^9$$$ and $$$t \leq 100$$$, so it will give you TLE.

Thank you

what is the hack for C ?

Idk, but maybe it's due to the timeout since most of the hacked code got over 1900ms...

What is test case 8 in E??

hi guys can anyone tall me how to solve C? I don't understand why it always is optimal to try first divisor of n

find all prime factors with their respective powers in sqrt(n) time then check three cases case 1. no. of prime factors are more than3 answer always exist and it is any combination you can pick up then

case 2 only 2 prime factors but their total power is greater than or equal to 4 then answer exist else no. (a,b,a^x*b^y)

case 3 only 1 prime factor available then check if its power>=6 (a,a^2 a^3) then answer always exist else no.

I also wrote my solution based on same logic, except that I was considering for case 2 that the sum of powers should be greater than equal to 3

We just need to find 2 different divisors such that one of them is a composite one with again 2 different divisors and also you need to check that they are greater 1.

hmmmm you can list all of divisors of N, the max numbers of divisor of N is 100 (if N == 1e9) so you can use O(N^3), right? Use 3 loops and check every divisor by conditions of problem

Not exactly n³ because no. Of divisors are way to less for numbers <= 1e9.Its not 100 but around 1700-1900 i guess

you can check it! numbers of divisors of 1e9 is 100, I tried it before I wrote my solution

Any number less than 1e9 has not more than 1344 divisors, with 735134400 having exactly that many. Actually, it is reasonable to estimate the number of divisors as cbroot n for small numbers (even though it asymptotically grows slower than any polynomial).

Maybe you don't understand what I say :(

Maybe that's the reason but this logic works right XD

Guys, I am confused about the Problem D. In the example it states that:

"After the fourth query, the array is a=[0,1,2,2]: you don't need to perform any operations, maximum possible MEX is 3 (you can't make it greater with operations)."__ However, if we add one to the last element will get a=[0,1,2,3] which I think has a MEX of 4. Can someone explain me why adding one to the last element does not improve the MEX?You can add only number x. In this testcase x equals to 3, so u cant add 1, u can add only 3 as many times as you want

Thanks man, I totally overlook such requirement.

Whats testcase 3 of problem F?

This testcase worked for me:

InputOutputNo hacking in this Round? I am getting Illegal contest ID.

any idea to solve problm D please ?

when will be editorial will be up?

When the ratings will be updated?-

Whoops, looks like I submitted a solution for 1294E - Obtain a Permutation that has an error in it not covered by the testing suite, but it's too late to hack it: 69397747

Spoiler`a <= n * m`

should be`a < n * m`

. It breaks on the following test case:I have hacked it now with the sample you provided

I think I am the only one who solved C via Miller-Rabin.

It proves that it is no use to think the problems as too difficulty in div3 rounds

I have created the video solution for the first four problems, explaining my understanding and approach for the same. Codeforces 615 DIv3 Video editorials

Do like comment, share, subscribe if you like the video. Do subscribe for more such content

Happy Coding

Man are ducking serious, first four problems are super easy, there is no need to make a whole video explaining them. Besides why didnt you explain all the problems? Are they too tough for you?

I think your test cases for 1294E - Obtain a Permutation is too weak. 69353056 Shows: Output: 0 For Input: 4 4 5 2 3 4 Where the actual result is: 1

Huge gap between next contest....... Please decrease the gap

I got a mail from codeforces because my submission matched with someone.I am giving you a guarantee that it became co-insidently.i saw this code(question B) before in my collage fest at DAIICT,Gandhinagar,India.So please give me rating of my codes. thaks...........

Sahil_M is also my collage mate and he was also there in fest.so co-insidently this thing happened.

I am sorry I participated in the round with 2 personal users (7ouda,7ooda) and I don't know that it's rules violation.

Hi dear,

I participated in Codeforces Round #615 (Div. 3) with my 2 personal handle (7ouda,7ooda) and submitted same solutions so my submissions was skipped, and I didn't know that it's a rules violation, so please can you help me.

Thanks, Mahmoud.

Write it here.

Thanks