vovuh's blog

Codeforces Round #686 (Div. 3)
By vovuh, history, 4 years ago, translation, In English

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!

  • Vote: I like it
  • +402
  • Vote: I do not like it

Comments Comments (121)
| Write comment?
»
4 years ago, # |
← Rev. 2   Vote: I like it -47 Vote: I do not like it

:)

→ Reply
»
4 years ago, # |
  Vote: I like it +29 Vote: I do not like it

I wish this round becomes unrated for me soon.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +32 Vote: I do not like it

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

    → Reply
»
4 years ago, # |
  Vote: I like it +14 Vote: I do not like it

And finally the wait is over!

→ Reply
»
4 years ago, # |
  Vote: I like it +11 Vote: I do not like it

DIV 3 rounds can be risky for higher specialists.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    Agree

    → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Why?

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +9 Vote: I do not like it

      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

      → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      They are the LGMs of Div 3

      → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    true

    → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +7 Vote: I do not like it

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

    → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

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

    → Reply
»
4 years ago, # |
  Vote: I like it +25 Vote: I do not like it

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.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    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)

    → Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    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

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +17 Vote: I do not like it

      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.

      → Reply
»
4 years ago, # |
  Vote: I like it -22 Vote: I do not like it

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

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +19 Vote: I do not like it

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

    → Reply
»
4 years ago, # |
  Vote: I like it -23 Vote: I do not like it

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

→ Reply
»
4 years ago, # |
  Vote: I like it +118 Vote: I do not like it

→ Reply
»
4 years ago, # |
  Vote: I like it +6 Vote: I do not like it

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

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    no option except to go for virtual

    → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    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 .

    → Reply
»
4 years ago, # |
  Vote: I like it -10 Vote: I do not like it

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

→ Reply
»
4 years ago, # |
  Vote: I like it -9 Vote: I do not like it

yay DIV 3 round

→ Reply
»
4 years ago, # |
  Vote: I like it -12 Vote: I do not like it

Is this Rated for me? guys?

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
4 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Wish you all the best ♥

→ Reply
»
4 years ago, # |
  Vote: I like it -32 Vote: I do not like it

Is it rated?

→ Reply
»
4 years ago, # |
  Vote: I like it -13 Vote: I do not like it

When will div. 4 return ?

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Good Luck for Everyone :)

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

It's valuable for waiting such long time :)

→ Reply
»
4 years ago, # |
  Vote: I like it +5 Vote: I do not like it

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

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

.

→ Reply
»
4 years ago, # |
  Vote: I like it +2 Vote: I do not like it

Hope I can reach green this time

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it 
int rating=1134;
rating+=150;
→ Reply
»
4 years ago, # |
  Vote: I like it +8 Vote: I do not like it

This comment section is shit.

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    DELETED

    → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

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

      Is that correct?

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Yes.

        → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        yup, this is true only for Educational and Div. 3/4 rounds. In regular div 2/1 rounds only last pretest passed submission is considered afaik.

        → Reply
»
4 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Screenshot-2020-11-24-215410.png
I felt like the dumbest person on the planet on reading this line after wasting 40 mins to solve a #P-complete problem.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
»
4 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
»
4 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

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

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it +12 Vote: I do not like it

        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.

        → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        What was your approach?

        → Reply
        • »
          »
          »
          »
          »
          4 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

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

          → Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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.

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
»
4 years ago, # |
  Vote: I like it -7 Vote: I do not like it

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

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

    → Reply
»
4 years ago, # |
  Vote: I like it +6 Vote: I do not like it

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    true 100% i was like that XD

    → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

What is the case 7 on the problem D?

→ Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Try for 75

    Answer is

    2
    5 15

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      My code produces the right answer there.

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

        → Reply
        • »
          »
          »
          »
          »
          4 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

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

          → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

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

    → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

easy peasy Japanesey

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

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

→ Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 2   Vote: I like it +5 Vote: I do not like 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

    → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

where is the wrong in this code?

wrong answer 161st numbers differ — expected: '2', found: '1'

can I know it?

http://codeforces.net/contest/1454/submission/99493118

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it -23 Vote: I do not like it

    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.

    → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Is there anybody who solved problem D with backtracking? :)

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    are you a masochist person?

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Excuse me, optimized brute-force.

      → Reply
»
4 years ago, # |
  Vote: I like it +14 Vote: I do not like it

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

→ Reply
»
4 years ago, # |
← Rev. 3   Vote: I like it +5 Vote: I do not like it

submission: 99493024

if(n==100000123) {
    cout<<1<<endl<<2<<endl;
    continue;
}

submission: 99494601

if(n==2001) {
    cout<<10000<<endl;
    continue;
}

Make system tests more and useless. Why do this?

→ Reply
»
4 years ago, # |
  Vote: I like it +4 Vote: I do not like it

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

→ Reply
»
4 years ago, # |
  Vote: I like it +3 Vote: I do not like it

E was an awesome problem!

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
4 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Nice set of problems

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

.

→ Reply
»
4 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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 ?

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    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.

    → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +7 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +17 Vote: I do not like it

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

      → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
4 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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

→ Reply
»
4 years ago, # |
  Vote: I like it +4 Vote: I do not like it

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

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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://codeforces.net/contest/1454/submission/99406543 2. https://codeforces.net/contest/1454/submission/99419833 3. https://codeforces.net/contest/1454/submission/99456510 4. https://codeforces.net/contest/1454/submission/99468339

→ Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 2   Vote: I like it +6 Vote: I do not like it

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

    → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it +5 Vote: I do not like it

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

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply