Hello! Codeforces Round 686 (Div. 3) will start at Nov/24/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 nooinenoojno Stepanova, Mikhail awoo Piklyaev, Maksim Neon Mescheryakov and Ivan BledDest Androsov for help in round preparation and testing the round. Also thanks to Artem Rox Plotkin and Dmitrii _overrated_ Umnov for the discussion of ideas and testing the round!

Good luck!

**UPD**: I would also like to thank Ivan Gassa Kazmenko for invaluable help with the round preparation!

**UPD2**: Editorial is published!

:)

I wish this round becomes unrated for me soon.

I wish this "soon" may not come in between of running contest though:)

And finally the wait is over!

DIV 3 rounds can be risky for higher specialists.

Agree

Why?

Because they have the highest rating for rated participants, they need to get a really good rank to get +ve rating, which is ofc easier said than done

They are the LGMs of Div 3

true

i think if u are thinking more about rating it will decrease your performance!!! this happens with me

it happens to me too

Yes! if you are a higher specialist, you need to get a high high high high rank that your rating can go up

Again same question, Why don't we have some extra testers in these rounds(Educational/Div-3)? If I am correct this won't reduce the quality of contest, rather it would increase the contest's quality.

Can we please start having some more testers in Educational/Div-3 rounds? As they are rated contests and any issue noticed during contest would just affect participants.

I just encountered one more past educational round which was unrated because of an issue with problem A statement. Educational Codeforces Round 64 (Rated for Div. 2)

They do have 6 testers in this round. Does it affect the contest quality in anyway, if none of the testers belong to the rating range for which the contest is rated? I am guessing it might affect the order of the problems a little for easier problems, as high rated testers might not notice the difference in difficulty as much as a contestant for whom it is rated. That apart other issues related to questions should mostly be covered

I am just trying to make a point that having a list of testers with different rating group won't adversely affect the contest quality, rather it may improve it.

Exicted for the rare div 3 round. Does div 4 round even happens? Hoping to see some nice questions

what the hell is that profile pic? get that nudity out of here

More than half of the comments are downvoted ! :-{

'Cause of people Like You

Is there a way to participate after the 9:35 UTC-5? Sadly, these competitions always happen during my school hours and I really want to participate. :(

no option except to go for virtual

well div3 happens not so often . and i think you can take holiday that day . Afterall it will be worth it . coz we do it that way .

Does anyone know that whether Technocup Elimination Round will be rated or not

yay DIV 3 round

Is this Rated for me? guys?

Yes, it is.

Can't wait to see the problems! Good luck everyone! :D

Wish you all the best ♥

Is it rated?

wtf you stole my comment

When will div. 4 return ?

i think never :D

There's an unofficial Div. 4 round tomorrow. You can check it out here

ye but it was unrated

Good Luck for Everyone :)

It's valuable for waiting such long time :)

Finally wait is over. Hope I can get rating above 1000 today:)

.

Hope I can reach green this time

What is the points distribution for the problems? Or are there none for Div. 3 contests.

`cout << "Congratulation! you have reached pupil." << '\n'`

damn where is ;

That's the reason still I am pupil :)

This comment section is shit.

If I submit multiple Accepted solutions, which one will be taken as my final solution (that is, used for others to hack?)

DELETEDall accepted solutions can be used for hacks, and for final testing first accepted will be considered and if failed then second and so on.

So if one of my accepted solutions survive the hacks, then I solve the problem.

Is that correct?

Yes.

yup, this is true only for Educational and Div. 3/4 rounds. In regular div 2/1 rounds only

lastpretest passed submission is considered afaik.I felt like the dumbest person on the planet on reading this line after wasting 40 mins to solve a #P-complete problem.

me too!! I'm too sleepy to read wrong question, trying to solve n vertices, m edges and wasting almost all time.

What's the solution of E? Really liked problemsetting (especially F).

Hey, video to solutions to everything are available here if you're interested

GOD SPEEDI got the idea for C but completely messed up thinkin about the first and the last digit . BTW that was very fast editorial .SecondThread

How to solve E ? F was easier than E for me

There are 2 paths between all pairs except for adjacent pairs within the root on the cycle of the almost-tree. Details and code are explained here.

You have an "almost a tree"-graph. Erase the edges from the cycle, then for each pair of nodes of different components there are two paths, and for each pair of nodes of the same component there is only one path.

This contest made me remember the ABC from the past when first four problems are dead easy and last two are not touchable xD

F was easy idea wise if you understand binary search & know a data structure(for range min queries like segment tree or sparse table), it was just about implementing.

Now I am "Afraid" because I did not use a Binary search or segment tree or sparse table.

I agree that other approach will work. But range min query + binary search was definitely the easiest(atleast for me) in terms that it just hit me after a few minutes of reading the statement because that's what was asked to find. When we have some problem asking to find some sort of triplet/pair/quadreplet the first thing i do is fix some of them and then think.

What was your approach?

It is I think same as Gassa's approach in the editorial.

Nice contest! I just want to ask what's the trick behind F. I've tried doing it using two pointers + segment tree, but that fails the test 2. My idea may be too off the right track, but that's what it is. Thanks.

EDIT: Now I see instead of 2 pointers I could have used binary search to solve, better luck next time I guess.

Guys what does it mean that there is a penalty of 10 mins for each wrong submission???

Your final score time would be added with the penalties. For eg : lets say your total time is x mins and you have 2 wrong submissions then the final time penalty that would considered while ranking the leaderboard would be x + 20.

My Explanations for ABCD

A

Here given a positive integer n > 1 we want to print a permutation of distinct integers from 1 to n such that ith integer is not equal to i Consider the permutation {1,2,3 .. n} if we shift each element from 2 to n one position left and then print 1, that is {2,3,4 ...,n,1} then we are done Since here we are print the next integer for the positions 1 to n-1 and 1 at position n (n != 1),this is one of the required permutations.

Topic : Constructive Algorithm

B

Here we are given an array of n integers. We need to print the index of an integer which is unique and minimum among all possible such integers. So we maintain a map to track the frequency of each element. Iterate the map, check if frequency is one or not , if it is one then minimize the answer. if there is no unique element then print -1.

Topic : Implementation, Brute Force

C

Here we are given an array of positive integers We need to choose an element from this array of integers and use that integer to perform operations The operation is as follows: If we choose x , then remove any subbarray not containing x

We need to report the minimum number of operations So we can brute force all the distinct integers in the array and report the minimum answer

To do this , we maintain a map from integers to vector of integers. This map is from each unique integer in the array to it's indices .

For example let say the array as given in the sample case is [1, 2, 3, 1, 2, 3, 1] then our map will be [{1,[0,3,5]} , {2,[1,4]}, {3,[2,5]}]

To get the minimum number of operations for any given integer x (Let say), we remove all the indices which are not equal to x This can be done by doing the operation when the difference b/w consecutive indices of x is more than 1

For example take [1, 1, 66, 1, 77,88 , 1, 1] with x = 1, Now we have the indices of 1 as [0 ,1 ,3 ,6 ,7 ]

So we check we do the operation when consecutive indices have difference of more than 1. Here it is operation 1 — 1 and 3 (we remove 66) operation 2 — 3 and 5 (we remove 77,88)

Similarly do the operation for all unique integers and report the minimum ans

Topic : Implementation, Brute Force

D

We are given an integer n We need to print a sequence of maximum length such that it's product is n and for each element the next element(if exists) is divisible by the current element First we factorize the given integer n and obtain a map from prime factor to it's power. now we need to print the desired sequence. Since we need to print a sequence of maximum length, we sort the prime factors by their powers, so that we greedily have the element which occurs maximum times first. Let say we have 360,so we make a vector of pairs and sort it by power. that is

{2,3} {3,2} {5,1}

Now we iterate the vector of pairs, until the powers are >= 1

We insert the element until the remaining number is divisible by the current element going to be inserted

For example

we have 2 , remaining is 360/2 = 180, so we insert it. ans is {2}

we have 2, remaining is 180/2 = 90 , so we insert it . ans is {2,2}

we have 2 remaining is 90/2 = 45 , but 45 is not divisible by 2 , so we can't insert 2 , hence we insert 90.

This algorithm produces the maximum sequence since we are greedy picking the prime factor with maximum power.

Topic : Greedy, Implementation, Sorting

Will the formula for $$$E$$$ be: $$$n(n-1)-(n-no \,of\, vertices\, in \,the \,cycle)$$$

No, it would just pass the sample, try on this graph: {1 2}, {2 3}, {3 4}, {4 1}, {1 5}, {5 6}

true 100% i was like that XD

What is the case 7 on the problem D?

Try for 75

Answer is

2

5 15

My code produces the right answer there.

Okay. My 1st submission failed and I thought of this case. My code failed for this too. Modified the logic and it passed

I already know my error. It was a noob-bug during a sieve.

How to solve problem F? Well I applied two pointer approach so it was bound to get TLE. So, I guess it would include some binary search solution.

What was your approach?

I binary sparse in answer. Good Qhuesion. Writer very very intelligent. You also sparse tabul. Else not accept.You understand me?

Where can I get the editorial for this contest? I am new to codeforces. Any help would be apprecited.

I think tomorrow, when the hacking fase is over

Usually the editorial gets posted eventually on the problem announcement. In the meantime, there's my solution video or neal's livestream.

easy peasy Japanesey

https://www.youtube.com/watch?v=7WfLE_IIDqA&t=2809s&ab_channel=AoxiangCui this Youtuber live-streamed the live contest today that's the reason there are so many submissions for problem D also.

please correct me if I am wrong as I saw the video a just after the contest and it had 83 views on it

Nope, she is a very experienced streamer. And the video was uploaded at the same moment when the contest ended. And it was never a live stream though

where is the wrong in this code?

wrong answer 161st numbers differ — expected: '2', found: '1'can I know it?

http://mirror.codeforces.com/contest/1454/submission/99493118

You get wrong answer because you are wrong code. Write beautiphul code. Else not accept. You write in Jabha...hahahahahaha. I not like jabha. You not write jabha. Else I not see your code.

her name is

javamy dear, not jabha hahaIs there anybody who solved problem D with backtracking? :)

are you a masochist person?

Excuse me, optimized brute-force.

The problems were awesome!! The magic of Data Structure! ;)

submission: 99493024

submission: 99494601

Make system tests more and useless. Why do this?

Today contest good contest. I very very like today contest. Make tomorrow contest. I give tomorrow contest.

E was an awesome problem!

I got an AC to it, one minute after the contest.

Getting F a couple of minutes after the round's end :(

Nice set of problems

.

His dog was competing.

Does E,F problems are actually meant to solved by div. 3 users ? Really, I saw some red coders took 30 minutes to solve E.

So how could they expect a div. 3 Candidate to solve problems like E,F in an hour ?Not all problems are meant to be solvable during a contest, some are their to learn from, that is all. And it is not that E and F are unsolvable by people with rating <1600.

Well, I solved both E and F in the contest and I'm a gray coder, so it is indeed possible.

Yeah, but you are either an alt or have done lots of competitive programming on platforms other than cf.

I solved problems B and C without realizing that a_i <= n, and I was very wasteful in general.

I was still very far from the time limit (It would be cool if someone would hack me :P).

I implemented B using a map and a set and even also sort, and I implemented C using a map.

Were those constraints meant to make implementation easier?

I did D in a weird way.

Checked every divisor's (except 1) highest power that divides n. Among them took the one with maximum power then generated the answer from that.

Submission: 99476498

Thanks vovuh for a round with such elegant problems. Nice learning. Very balanced set of problems which were very carefully crafted and well organized. I am sure this took a lot of efforts from you and team! Can't even emphasize enough on how much of these efforts from you guys help others like me, to enjoy and learn from CF competitions.

Appreciate your efforts!! Thanks again!!

Very nice contest with interesting problems. Much thanks to vovuh and MikeMirzayanov !!!

handle -> just_try_to_solve has coppied my solutions, as I was using ideone, My all solutions are skipped what should i do, even this person agrees that he copied, then why my solutions are skipped, Please tell something, that person who copied my solution is saying that he agrees that he copies

please put him out of contest, not me

my submission links are as follows — 1. https://mirror.codeforces.com/contest/1454/submission/99406543 2. https://mirror.codeforces.com/contest/1454/submission/99419833 3. https://mirror.codeforces.com/contest/1454/submission/99456510 4. https://mirror.codeforces.com/contest/1454/submission/99468339

No, you are the one who deserve to be out of contest for not reading/following the rules.

hello,I want to know whether the result are published for this round. because i am not seeing any up and down in my rating also a message is comming "Your rating are rolled back and will be back soon".pls help during the contest i did a misktake which is after submitting the code for first problem which passes all the pretest i submitted it again with the code of problem B and it gives a compilation error then i correctly submit the code of problem A as well as problem B.pls help me

Not an issue , the most recent submissions are judged for evaluation . Ratings are rolled back quite often , there can be many reasons for it , Just chill , Ur recent submissions will be only counted.

Last div.3 was rated for <=1600. But how it is rated for This id ? Before participating his rating was 1601.

Hacker.. :-O

Before rating change of this round there was rating recalculation of the Codeforces Round 685 (Div. 2). He probably was < 1600 before recalculation

Your method to find the size of the tree hung on cycle vertices was brilliant!