Vladosiya's blog

Codeforces Round #776 (Div. 3)
By Vladosiya, history, 3 years ago, translation, In English

Hello! Codeforces Round 776 (Div. 3) will start at Mar/08/2022 17:35 (Moscow time). You will be offered 7-8 problems 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 a rating of 1600 or higher, can register for the round unofficially.

The round will be hosted by rules of educational rounds (extended ACM-ICPC). Thus, solutions will be judged on preliminary tests during the round, and after the round, it will be a 12-hour phase of open hacks.

You will be given 7-8 problems and 2 hours and 15 minutes 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 participant of the third division, you must:

take part in at least five 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 our work. Problems have been created and written by ITMO University teams: MikeMirzayanov, MisterGu, myav, Gol_D, Aris, senjougaharin, me Vladosiya.

Also many thanks to mango_lassi, espr1t, karemo, starboy_jb, Fly_37, omikad, Katya_Goryachkina, Omja, teraqqq, oversolver, Jostic11, yorky, _4dr_ and doreshnikov for testing the contest and valuable feedback.

Good luck!

UPD: Congratulations girls on International Women's Day <3.

UPD 2: Editorial

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

Comments Comments (129)
| Write comment?
»
3 years ago, # |
  Vote: I like it +119 Vote: I do not like it

mango_lassi tested so good he got mentioned twice.

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

Good luck to everyone !

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

This will be an important contest for me, the wait has been long, let's hope to turn blue.

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

First unrated div3 for me, yay :)

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

I might become pupil after this round. I am excited :)

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

Guess who is skipping school tomorrow hahaha

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

First div 3 contest for me yay!! thanks to all the testers and it will be challenging as we have to solve more problems in less time!!

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

Is this challenge suitable for beginners?

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

    Yes, significantly easier than Div2s and Div1s I would say

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

Div3 contest, long time no see

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

I am happy to participate in a contest on by birthday. I wish to be pupil after this contest. Wishing everyone positive delta. GL&HF!!

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

As a first time tester for a Codeforces round. Please give me some upvote :).

Good Luck and High Rating.

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

Good to see a contest after every one two days. Well done codeforces!!

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

Hope I can solve today's problems and get my handle colored.

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

Very excited for div3 after a long time. All the best everyone.

→ Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it -9 Vote: I do not like it

Dear contest, make me > 1700 rated pls. thx in adv, wil pay the <> by tomorrow evening

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

Vladosiya's Div 3 rounds are really good. Looking forward to some great problems in the contest.

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

Nice gift for 8th of march , and here's my best wishes to you on International Women's Day 2022 ! Wishing a very happy Woman's Day to strong, intelligent, talented and simply wonderful women of this world! Don't ever forget that you are loved and appreciated. And also good luck on Div 3 !

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

    Good luck also for mediocre and normal women (not only talented and strong ones) which also deserve respect

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

Can anyone help me understand why untrusted people will not be included in the rankings? The round is rated for anyone having a rating less than 1600 anyway so how is the decision having any effect on rating changes?

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

Good luck at International Women's Round #1!

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

Plz, no number theory in problems

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

Finally my first participation as unrated one.

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

implementation forces

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

It took me 20 minutes to understand the statement output 2 numbers in next n lines of the problem C

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

Really cool round. Thanks to creators

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

Logic for C please?? is it implementation based problem

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

    Take 2 * n minimums and after sort them by coordinate

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

      how can we sort the array in a way that we would know the index of every element before sorting with O(n log n) solution ?

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

        Just store indexes somewhere, for example make a tuple (x, w, index)

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

        I used map, where key is w and value is index in not sorted vector

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

when i read E I thought it's too easy but then i realized there are things i didn't count in my solution and it was too late

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

    i thought too what ever i was thinking should work but it didn't. then i changed my perspective and did some implementation with multiset to check what would be answer if i change $$$i^{th}$$$ exam date.

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

      I think you should only change the smallest value but I didn't check that maybe if i delete a1 for example and put it somewhere else then maybe a2-a0 is the new smallest value

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

        yes you are right only difference can be made by removing minimum gaps. also need to make sure there are two ways to remove each gap that is not the left most. and also the way i implemented it didn't hurt to check every index, so to keep code a bit simple i didn't think of optimizing on that

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

Problem G: Counting Shortcuts is a great extension of ABC211: Number of Shortest Paths

In fact, you only need 5 to 6 lines of code changes in the Atcoder version to get it working.

I've summarized my approach for ABC211: D in this comment

How to extend it to this version?

First, break it into 3 parts. If the shortest path is of length $$$\delta$$$, we need to compute paths of length $$$\delta - 1$$$, $$$\delta$$$ and $$$\delta + 1$$$. Computing $$$\delta - 1$$$ is a trick question, you should figure that out yourself. Computing $$$\delta$$$ is same as ABC211:D. So, we just need to compute paths of length $$$\delta + 1$$$.

As mentioned in the previous comment, edges in a BFS tree can only exist between nodes of same level (horizontal edges) or consecutive level (vertical edges). If we observe a shortest path, it needs to descend the tree at each stage, i,e, it can only contain vertical edges. A path length of $$$\delta + 1$$$ implies that we added one extra edge in our shortest path. Notice that this extra edge cannot be a vertical edge, as we will miss the target vertex by 1 height. So, we are allowed to add one edge between nodes on the same level. This simplifies it to,

How many paths from source to target are present such that you are allowed to use EXACTLY 1 edge at same level.

Let's rename the DP of the previous problem to $$$dp\_tight$$$, and the DP array of the new problem to $$$dp\_loose$$$.

$$$dp\_tight[node]$$$ is the number of ways to reach $$$node$$$ from $$$source$$$ when you are not allowed to use unnecessary edges.

$$$dp\_loose[node]$$$ is the number of ways to reach $$$node$$$ from $$$source$$$ when you are allowed to use exactly one extra edge.

To compute $$$dp\_loose[node]$$$, we need to consider every edge on the same level (horizontal edges), and increment the $$$dp\_loose$$$ of one vertex by $$$dp\_tight$$$ of the other vertex. Since we should precompute the DP values of all nodes on the same level before populating DP values of next level, we can use a temporary queue for each level (Although I think we can do it in one pass too).

Time Complexity: $$$O(N)$$$

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

Feel like output for C could have been simplified without taking away from problem difficulty. But pretty fun contest anyways.

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

Anyone else ? Who wasted 10 minutes thinking about output in C because of poor language

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

I will reach expert if not hacked.

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

    Can you explain your approach for E?

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
      ← Rev. 5   Vote: I like it 0 Vote: I do not like it
      1. use a sorted map, such as TreeMap in Java, then maintain all the gaps' count;
      2. Try to remove a[i] for i in [1, n — 1], you will have 2 cases: case 1. insert a[i] in a gap where it has exams on both ends; you will pick the largest gap maxGap and put it in the middle to get a new gap of (maxGap — 1) / 2; case 2. insert a[i] at d with a new gap of max(0, d — a[n] — 1);

      take the better one of the above 2 cases and compare it with the smallest key and update answer. During step 2, remember to update your map accordingly: first remove deleted gaps and add newly generated gaps. After processing a[i], restore the map for the next element.

      I had this idea but forgot to take care of the special case where if we put a[i] at the end on d, it is just d — a[n] — 1 instead of (maxGap — 1) / 2. Feels bad :(

      I've added some comments in my submission, the idea is fairly straightforward: 148911439

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

        i tried using map in C++.... my last brain cell is trying to figure out why my code mutates the map in each iteration, tried using delete when key's value is 0, but when i add some value to it, keys are not appearing back.........

        edit: i mistakenly deleted the value of the map not the key T_T, still got WA tho

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

          I ran into a similar key not found error during contest. I think it is because the way I updated the sorted map.

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

        but would'nt the complexity become more O(n*n) or O(n*nlogn)? That should give tle. You are doing this O(n) computation for every a[i].

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

          it is O(N * logN), each iteration we uses 6 map operations (3 insert, 3 removal). Building the maps takes O(N * logN) then for each iteration, it takes 6 * log(N) time.

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

      I binary searched the answer (maximum μ possible by shifting the element with minimum rest days before it). You can see that for some μ: all smaller values are possible to achieve, this forms an array of True and False: T T T T T F F F F ...

      So now you can apply binary search to find the last T (Last T is maximum possible μ). Now, to find if the current candidate for μ is T or F. You can write a function F(M) which will return True/False if rest days before A[i] <= M for all i. You can try to achieve this by removing the element E with smallest rest days before it and placing it in between any two elements with maximum rest days.

      My implementation for F() is very bad and I believe you will find much better code for understanding in top standings. Please ask if there is anything you didn't understand.

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

C is the one of the worst questions I have seen in a while. The last paragraph of the problem is so confusing, even looking at samples didn't help. I had the idea in 5 minutes, but took 4 WA's on test 1 just because the output formatting is wrong. Also, what does this line have anything to do with anything? 

The order in which you output the endpoints of a segment is not important — you can output the index of the left endpoint first and then the number of the right endpoint, or the other way around.

This just makes the problem even more confusing. And lastly, would it kill you guys to give the initial points as sorted? So much extra implementation just to print the indices of the points in original order after god knows how many times I used sort().

On the other hand, the problem itself and the idea behind it is nice. I just don't like the fact that I have to spend 10 minutes on thinking about the solution + implementations and then 30 minutes to properly format the output just so that it passes samples.

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

Question C was worded so poorly!

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

too heavy implementations

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

ImplementationForces

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

Open hacking means if I fail in hacking a solution it would not negatively affect me?

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

Can we get -1 in D?

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

    No. It is always possible to sort the array. Think of it as bubble sort, but use rotates instead of swaps. Every time we move the greatest element to the right, and repeat the same process on the remaining elements until the array is sorted.

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

      Can you elaborate on what do you mean by Every time we move the greatest element to the right ?

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

    no, it is always possible to sort an array by rotating its prefix. actually what i have observed, this fact is used in quite some problems. For instance, this problem

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

      Thanks for sharing. I wrote a -1 condition in the contest without thinking much

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

        It's better to have it and don't need it than need it and don't have it.

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

Is it necessary for the answer of Problem G to module 1000000007?

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

    Yes

    It is easy to construct a test case for which answer is $$$2^k$$$ if $$$n=3k+1$$$.

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

is there a solution for E that does not involve too many caseworking? my solution had to consider like 6 cases to pass.

Also, props to the very strong sample case that actually helped a lot

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

    Binary search, to check if x is okay find first gap with length < x and try to remove one of endpoints of the gap. Try to place the removed exam in midpoint of gaps, or at the end of session.

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

    you can check out my solution, I made it pretty similar to yours. solution

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

Problem G is very similar to this problem, with the subject of weighted directed graph;

Additionally, more sophisticate version is NOIP2017-S P3953, with the restrict of weighted directed graph($$$w_i \ge 0$$$), to calculate the number of ways of path length no more than minimum_path + k.

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

It's funny that there is no pretest with answer >=998244353 in G:)

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

Is there an O(n) time complexity solution for D?

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

    misread D's constraints, for almost 1.5 hrs was trying to find O(n) for D but couldn't:(

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

    Dunno, but you can do it in O(nlogn) with implicit treap.

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

How to solve G? any hints?

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

Video Editorial for A-E for anyone looking

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

There is an issue with the problem G: the variable $$$t$$$ has been reused. Please fix immediately. Highest priority.

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

Hints for problem E ?

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

    I think the way I solve wasnt the expected solution but try this:

    hint 1
    hint 2
    Solution
    → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

can we do d in o(n)?

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

    As we think it can't be solved faster than O(n * log(n))

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

hope to be Specialist

Oh, I submitted B for three times. I might not be Specialist

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

The pretests of G were so weak that I used 998244353 as the modulo in this problem and passed them!

But today I was hacked!

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

My rating is 1200. Why was this round unrated for me?

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

Is there any indication that the match has been unrated? My friends and I have found that this match is Unrated for us. A lot of thanks if you could reply to me. :(

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

In this contest, I found an act of unfair means where the user D_K_307 hacked his solution from a fake account to increase his score. Is there a way to report such things ? Proof here

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

    In div.3 contest you can't increase your score with hacking

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

      Cool, but still it's a wrong practice and will be effective for some contests. I have seen some users in past too doing this.

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

    I did not have any Idea about hacking So I just tried it in div.3 contest Beacause I don't know this. Sorry For that.

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

After the system testing. Still didn't change the rating...

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

    Waiting for the same. Expecting increase in rating but not scared if it goes unrated or something :(

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

      ya same bro :(

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

        Man I was about to go expert, why this rating haven't changed yet

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

          I would be close too. :(

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

            The rating predictors ain't couting out the not-trusted participants.

            So, I think +10 extra will be definitely there.

            Hope we both get the DARk BLUE.

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

Mr. Vladosiya I think it is your best contest.Make more contests

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

Waiting for rating changes with 29138 others :)__ Edit: Released yaay

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

The system told me that I cheated because of my Problem G solution coinciding with others. However, this problem had a same version on http://poj.org/problem?id=3463 ,and I had finished the problem with the help of a blog https://www.cnblogs.com/xingxing1024/p/5224363.html .So I use the code to finish problem G.Is it illegal?

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

    The blog was posted in 2016,I cant understand why i am cancelled in this round...

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

    my problem d is coinciding with others but i did it on my own what can i do in that case !?

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

The system told me to cheat because my g question is highly similar to others, but this question is written with reference to a board written before. The link is: https://www.acwing.com/problem/content/385/ , I did this question six months ago. I hope I can get a reply. Thank you.

→ Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it -12 Vote: I do not like it

[deleted]

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

Nice contest, I really liked it! I went from newbie all the way up to specialist :D!

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

is there an Editorial?

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

There's a piece of news floating around on Reddit that Russia is gonna cut off the global internet from 11th March. Is it correct? And is it gonna affect codeforces?

→ Reply