Rating changes for last rounds are temporarily rolled back. They will be returned soon. ×

Vladosiya's blog

By Vladosiya, history, 4 months 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, SixtyWithoutExam, me Vladosiya.

Also many thanks to mango_lassi, espr1t, karemo, starboy_jb, Fly_37, omikad, Katya_Goryachkina, Omja, teraqqq, Bugman, 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

»
4 months ago, # |
  Vote: I like it +119 Vote: I do not like it

mango_lassi tested so good he got mentioned twice.

ORZ
»
4 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Good luck to everyone !

»
4 months 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.

  • »
    »
    4 months ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    Me too.

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

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

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

    You have solved so many problems, I will add you to my friend.

  • »
    »
    4 months ago, # ^ |
    Rev. 2   Vote: I like it +7 Vote: I do not like it

    rahul_rax You became expert without participating in this round..!

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

      Yes, I just saw, after plage check, I got a +1 rating, and reached expert. All the best for today's round.

  • »
    »
    4 months ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    This round is not rated for you now

    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it +4 Vote: I do not like it

      Yes, This will be my 1st unrated round. Yaya!!

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

        For me too. Congrats

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

        you're exactly 1600 and they wrote above, round is rated for participants upto 1600.

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

      Bro plz tell me why my ratings not increased I have given the contest and have ratings under 1600

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

        Ratings are not updated for anyone till now

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

          I just wanted to ask, hh

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

          How much time it takes to Update ratings after Contest

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

    Only expert for whom the round is rated.

»
4 months ago, # |
  Vote: I like it +49 Vote: I do not like it

First unrated div3 for me, yay :)

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
4 months ago, # |
  Vote: I like it +27 Vote: I do not like it

Guess who is skipping school tomorrow hahaha

»
4 months 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!!

»
4 months ago, # |
Rev. 2   Vote: I like it +15 Vote: I do not like it

Is this challenge suitable for beginners?

  • »
    »
    4 months ago, # ^ |
      Vote: I like it +24 Vote: I do not like it

    Yes, significantly easier than Div2s and Div1s I would say

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

good luck guys:)

»
4 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Div3 contest, long time no see

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

At long last...

»
4 months 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!!

»
4 months 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.

»
4 months 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!!

»
4 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

I like div.3 thanks codeforces great site

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Codeforces is a great platform to develop skill on coding besides build up logic.

  • »
    »
    4 months ago, # ^ |
      Vote: I like it +26 Vote: I do not like it

    Thanks for the information!

    The world would have never known, if not for you to write this useless comment

»
4 months ago, # |
  Vote: I like it -7 Vote: I do not like it

Whenever You are having tough div 2 contest and you got -ve rating change then arrives Div 3 for resque . I loved them :) .

»
4 months ago, # |
  Vote: I like it +1 Vote: I do not like it

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

»
4 months ago, # |
  Vote: I like it +1 Vote: I do not like it

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

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hey Codeforces, please add a calendar invite to every contest, it would be great.

»
4 months 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

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

»
4 months 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.

»
4 months 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 !

  • »
    »
    4 months 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

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

      maybe (simply wonderful) means also means what you said :) ?

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How long have I been waiting for this moment...

»
4 months 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?

»
4 months ago, # |
  Vote: I like it -8 Vote: I do not like it

Good luck at International Women's Round #1!

»
4 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

.

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Lets Rock!! newbies

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Finally** DIV 3** contest :)

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Plz, no number theory in problems

»
4 months ago, # |
  Vote: I like it +13 Vote: I do not like it

Finally my first participation as unrated one.

  • »
    »
    4 months ago, # ^ |
      Vote: I like it -8 Vote: I do not like it

    how to check if I am doing unrated one?

»
4 months ago, # |
  Vote: I like it +8 Vote: I do not like it

implementation forces

»
4 months 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

»
4 months ago, # |
  Vote: I like it +13 Vote: I do not like it

Really cool round. Thanks to creators

»
4 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Logic for C please?? is it implementation based problem

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

    Take 2 * n minimums and after sort them by coordinate

    • »
      »
      »
      4 months 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 ?

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

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

      • »
        »
        »
        »
        4 months 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

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I hate test case 27 of G.

»
4 months 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

  • »
    »
    4 months 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.

    • »
      »
      »
      4 months 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

      • »
        »
        »
        »
        4 months 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

»
4 months 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
»
4 months 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.

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

    Took me eternity and 2-3 wrong submissions to figure that out on my own

»
4 months 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

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

    yeah, if it weren’t for the useless output of indexes in C, I wouldn’t get a bunch of execution errors and would have passed 20 minutes earlier, perhaps there would have been enough time to solve task D

  • »
    »
    4 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    +1
    30 minutes*

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

    I got the logic really early, but spent 30 minutes after misreading allotment of index i to coordinate. I alloted them according to their position of number line and spent a lot of time there :(

»
4 months ago, # |
  Vote: I like it +6 Vote: I do not like it

I will reach expert if not hacked.

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

    Congrats

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

    Can you explain your approach for E?

    • »
      »
      »
      4 months 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

      • »
        »
        »
        »
        4 months 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

        • »
          »
          »
          »
          »
          4 months 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.

      • »
        »
        »
        »
        4 months 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].

        • »
          »
          »
          »
          »
          4 months 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.

    • »
      »
      »
      4 months 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.

»
4 months 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.

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

    agree

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

    Well, if you look at the shortest solutions the problem is very simple to code.

    I also did not find the simplest solution and ended up needing 60+ lines of C++.

    I had prefix sum array, suffix sum array, set when calculating the sums (dealing with inserting the biggest element or the same element in the heap), and then had to rediscover the pairs after finding the minimum.

    The complexity was $$$O(m \log{m})$$$ for initial sort, and then $$$O(m \log{n})$$$ for the suffix sums and then $$$O(m)$$$ for min, and then again $$$O(m \log{n})$$$ for discovery of pairs.

    I have no idea how I can simplify my thinking for the future.

    On every contest I participated I wrote too much code, even if it was correct, it was just too much unnecessary stuff.

»
4 months ago, # |
  Vote: I like it +17 Vote: I do not like it

Question C was worded so poorly!

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

amazing problems) going to become a pupil

»
4 months ago, # |
  Vote: I like it +6 Vote: I do not like it

too heavy implementations

»
4 months ago, # |
  Vote: I like it -8 Vote: I do not like it

I am beginner and Today i am able to solve one problem first one. is it good for me

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

    If you at least got idea of question 2 then you are at par with average pupil I guess!

»
4 months ago, # |
  Vote: I like it +8 Vote: I do not like it

ImplementationForces

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Really amazing contest. Thanks for creating this.

»
4 months 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?

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can we get -1 in D?

  • »
    »
    4 months 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.

    • »
      »
      »
      4 months 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 ?

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

        Go in reverse. Think about how many rotations are required to move n back to the last index. Now look at the array till n-1 index only and do the same thing.

  • »
    »
    4 months 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

    • »
      »
      »
      4 months 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

»
4 months ago, # |
  Vote: I like it +1 Vote: I do not like it

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

  • »
    »
    4 months 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$$$.

»
4 months 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

  • »
    »
    4 months 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.

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

      you don't really need binary search tho

  • »
    »
    4 months 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

»
4 months 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.

»
4 months 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:)

»
4 months ago, # |
  Vote: I like it +4 Vote: I do not like it

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

  • »
    »
    4 months 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:(

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

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

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

is anyone else getting TLE on problem C??

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve G? any hints?

»
4 months ago, # |
  Vote: I like it -8 Vote: I do not like it

Video Editorial for A-E for anyone looking

»
4 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

I try to hack c but i got Unexpected verdict what is this mean ?!

»
4 months 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.

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hints for problem E ?

  • »
    »
    4 months 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
»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

can we do d in o(n)?

  • »
    »
    4 months 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))

»
4 months 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

»
4 months 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!

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

did rating change for anyone? pls ack (myself new to codeforces) It hasn't changed for me yet

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
4 months 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. :(

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

    after system testing it will be rated

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

      But I remembered that it used to show 'System Testing' rather than 'Finished' ?

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

      What is system testing?

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

        That is testing your code with all successful-hacking datas.

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

          thanks. how long does this usually takes?

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

          I actually participate in the edu model for the first time,when usually does the rating change after the open hack?

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

    But why today System test came so late unlike before? XD

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

      Forgive my poor English. It works as the "Educational Codeforces Round",so you do not need to get through the System test and you cannot hack others through the contest too. However,after the contest,everyone's submissions will open to the public 12 hours.Then everyone can make a hack. But the open hack has already ended long time ago,so i don't know why either.

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Why this round i have unrated?

»
4 months 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

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

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

    • »
      »
      »
      4 months 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.

  • »
    »
    4 months 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.

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    4 months 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 :(

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

      ya same bro :(

      • »
        »
        »
        »
        4 months 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

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

          I would be close too. :(

          • »
            »
            »
            »
            »
            »
            4 months 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.

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Everyone's rating hasn't been changed yet.I hope I can get to green.

»
4 months ago, # |
  Vote: I like it +1 Vote: I do not like it

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

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

    I agree with you.I hope that Codeforces can hold more div.3 contests.

»
4 months ago, # |
Rev. 2   Vote: I like it +5 Vote: I do not like it

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

»
4 months 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?

  • »
    »
    4 months 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...

  • »
    »
    4 months 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 !?

»
4 months 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.

»
4 months ago, # |
Rev. 2   Vote: I like it -12 Vote: I do not like it

[deleted]

»
4 months 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!

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I got my first rating from this contest :) Thanks for creating Div.3!

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

is there an Editorial?

»
4 months 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?

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

My solution https://codeforces.com/contest/1650/submission/148871334 for problem C of this contest coincided with the solutions of other users. So, I was skipped from the contest. But it was nothing but a coincidence because the entire solution was thought and implemented by me. So, it's a mistake from your side. My solution can't be stolen by others since I don't use any online IDE. The screenshot of my written code is attached below. Please take this into consideration.

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem E can d (number of sessions) be less than n (number of exams) ?

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

12 1 7 2 6 3 5 10 1 6 2 5 3 4 -6 1 5 2 4

why this output is not correct for C problem as {1,7} {2,6} {3,5} are nested

»
4 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

I don't use any online IDE. https://codeforces.com/contest/1650/submission/148896660 for problem C of this contest coincided with the solutions of other users. So, I was skipped from the contest,And i got minus 147 point this round it should be unrated for me But it was a coincidence because the entire solution was thought and implemented by me. So, it's a mistake from your side. My solution can't be stolen by others,take that into consideration because i got minus 147 point at this round not only was skipped for me it was skipped and my rate has been changed -147 point

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

one thing i am not getting according to given tutorial we have sort and remove all those (m-2*n) but how is it sure that we will be able to make pair in nested segments