Educational Codeforces Round 145 [Rated for Div. 2]
By awoo, history, 21 month(s) ago, translation, In English

Hello Codeforces!

On Mar/23/2023 17:35 (Moscow time) Educational Codeforces Round 145 (Rated for Div. 2) will start.

Series of Educational Rounds continue being held as Harbour.Space University initiative! You can read the details about the cooperation between Harbour.Space University and Codeforces in the blog post.

This round will be rated for the participants with rating lower than 2100. It will be held on extended ICPC rules. The penalty for each incorrect submission until the submission with a full solution is 10 minutes. After the end of the contest, you will have 12 hours to hack any solution you want. You will have access to copy any solution and test it locally.

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

The problems were invented and prepared by Adilbek adedalic Dalabaev, Ivan BledDest Androsov, Maksim Neon Mescheryakov and me. Also, huge thanks to Mike MikeMirzayanov Mirzayanov for great systems Polygon and Codeforces.

Good luck to all the participants!

Our friends at Harbour.Space also have a message for you:

Harbour.Space

Hey, Codeforces!

We're excited to announce that registration for the Leagues of Code Summer Camp is now open! This year, Harbour.Space University and Leagues of Code are organising a programming camp in Menorca from July 1st to the 15th!

Our Summer Camp is a training program that will teach participants competitive programming. We are inviting students ages 10 to 18 interested in improving their skills or seeking intensive, high-level training. Participants will be divided into classes based on their level and previous experience. Classes will be held in English.

Join a coding camp that brings you the brightest stars in tech!

Here is a summary of the camp :

  • Duration: 2 weeks
  • Dates: July 1st to 15th
  • Place: Menorca
  • Levels:

  1. Zero: Our "Zero" course is designed for anyone without programming experience. Through interactive lessons and engaging activities, they'll learn the fundamentals of coding and build a strong foundation for future learning

  2. Beginner: Our beginner coding course is designed for participants who have some basic programming knowledge but want to take their skills to the next level. The course covers programming fundamentals and builds on prior knowledge, focusing on problem-solving, critical thinking, and project-based learning

  3. Intermediate: Become a pro-grammarians by diving into the main concepts of web and game development. No coding experience? No problem! We'll help you get started, and by the end of the bootcamp, you'll be a coding ninja with a cool project under your belt!

  4. Advanced: Ready to put your brain to the test? Our camp will have you solving algorithms like a pro and competing like a champion with the guidance of world medalists. By the end of camp, you'll be a coding champion with a trophy in your virtual hands!

Ready to join our Summer Camp in Menorca? We have a 30% discount for Codeforces participants using the code CODPARMEBO30.

Register here→

UPD: Editorial is out

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

Comments Comments (213)
| Write comment?
»
21 month(s) ago, # |
← Rev. 2   Vote: I like it -132 Vote: I do not like it

"Unfortunately, due to network issues, we are forced to reschedule the round. Let's do it in the coming days. Apologize."

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +47 Vote: I do not like it

    "Unfortunately, due to network issues, we are forced to reschedule the round. Let's do it in the coming days. Apologize."

    → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it -32 Vote: I do not like it

      "Unfortunately, due to network issues, we are forced to reschedule the round. Let's do it in the coming days. Apologize."

      → Reply
      • »
        »
        »
        »
        21 month(s) ago, # ^ |
          Vote: I like it -49 Vote: I do not like it

        "Unfortunately, due to network issues, we are forced to reschedule the round. Let's do it in the coming days. Apologize."

        → Reply
        • »
          »
          »
          »
          »
          21 month(s) ago, # ^ |
            Vote: I like it -41 Vote: I do not like it

          "Unfortunately, due to network issues, we are forced to reschedule the round. Let's do it in the coming days. Apologize."

          → Reply
          • »
            »
            »
            »
            »
            »
            21 month(s) ago, # ^ |
              Vote: I like it -52 Vote: I do not like it

            "Unfortunately, due to network issues, we are forced to reschedule the round. Let's do it in the coming days. Apologize."

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              21 month(s) ago, # ^ |
                Vote: I like it -47 Vote: I do not like it

              "Unfortunately, due to network issues, we are forced to reschedule the round. Let's do it in the coming days. Apologize."

              → Reply
              • »
                »
                »
                »
                »
                »
                »
                »
                21 month(s) ago, # ^ |
                  Vote: I like it -43 Vote: I do not like it

                "Unfortunately, due to network issues, we are forced to reschedule the round. Let's do it in the coming days. Apologize."

                → Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +248 Vote: I do not like it

    Then donate to CodeForces? I don’t get why you are complaining when you are using the website for free anyways, and the website is ran by a small group of people.

    → Reply
»
21 month(s) ago, # |
  Vote: I like it -13 Vote: I do not like it

Hope contest will provide positive delta to all.

open please
→ Reply
»
21 month(s) ago, # |
  Vote: I like it -7 Vote: I do not like it

Can I cancel my registration? I dont think I can attend today for the new, rescheduled date.

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +25 Vote: I do not like it

    If you don't submit anything your rating won't change. Also you can cancel your registration by going to ghe registrants page, and press the X sign next to your handle

    → Reply
»
21 month(s) ago, # |
  Vote: I like it +7 Vote: I do not like it

Hi, what is the difference between a normal div 2 and an educational div 2?

→ Reply
»
21 month(s) ago, # |
  Vote: I like it -7 Vote: I do not like it

almost 30k registered in edu round *_*.

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +3 Vote: I do not like it

Hope to perform better

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +8 Vote: I do not like it

I want to request a feature where participants can submit their own authored and properly documented solutions. I know people do share the approach they used to solve the problem but I feel if something other than editorial is available, it can be helpful to each and every one.

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    thread with comments is usually not too long + people upvote some interesting solutions, so i dont quite understand why you need it

    → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      It would be nice to quickly find approaches to the particular problem you need. Ctrl + F doesn't always work since people phrase their questions in different ways.

      → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it +4 Vote: I do not like it

      Leetcode does this and I would say it is very good. You have access to detailed explanation of solutions in different methods and languages. Codeforces users are generally more experienced so I guess we can find solutions on our own, but sometimes I still struggle to find solution (if the editorial is hard to understand) for 2400+ problems.

      → Reply
»
21 month(s) ago, # |
← Rev. 2   Vote: I like it +18 Vote: I do not like it

I received 10 penalties because I set INF to 1e16 for problem D. Feel free to laugh :') https://imgur.com/a/F5VcnwL

→ Reply
»
21 month(s) ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

when that error came up I got almost sure that the contest is cursed. I submitted at 10 seconds remaining am I the last correct submission though.

→ Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

how to solve c?

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    C is a constructive algo based problem. There are usually multiple ways to solve these kind of problems

    → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      i'm weak in constructive can u tell your logic?

      → Reply
      • »
        »
        »
        »
        21 month(s) ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        1. Find a number w such that w(w+1)/2 Making this long sequence in the front will contribute this much to positive segments.
        2. There are rem = (k — w(w+1)/2 ) remaining segments we need. We can obtain them if we cancel out w — rem last positive number with our first negative. If our positive numbers were 5's, then putting a (w-rem)*(-5) will do. The rest can be filled with -1000.198797255
        → Reply
»
21 month(s) ago, # |
  Vote: I like it +1 Vote: I do not like it

How to solve B?

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Output sqrt(n-1)

    → Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Draw a 2d grid. You can fill the grid in two ways:

    Way 1: |x|+|y| = odd

    Way 2: |x|+|y| = even

    Then binary search upon the answer

    → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it -7 Vote: I do not like it

      Can you explain in more detail. I understood that the sum is accumulated as follows (let's say when starting from 0) n = 1 + 2*4 + 4*4 + 6*4 + 8*4 + ... How to use binary search to find on which element we will get n?

      → Reply
      • »
        »
        »
        »
        21 month(s) ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        n = (1+K)^2

        → Reply
        • »
          »
          »
          »
          »
          21 month(s) ago, # ^ |
            Vote: I like it -8 Vote: I do not like it

          Yes, after I wrote out all the prefix sums, I can see that it is k^2. But until that, you won't understand it. BAD PROBLEM.

          → Reply
          • »
            »
            »
            »
            »
            »
            21 month(s) ago, # ^ |
            ← Rev. 2   Vote: I like it 0 Vote: I do not like it

            I think visualizing it will be more understandable for the solution. Consider k is the answer, you can put chips on:
            k = 0 : (0, 0);
            k = 1 : (1, 0), (0, 1), (-1, 0), (0, -1);
            k = 2 : (0, 0), (2, 0), (1, 1), (0, 2), (-1, 1), (-2, 0), (-1, -1), (0, -2), (1, -1);
            If you draw these points on the 2D grid by each k, you'll find it's a square with 1 increment on the length of side and 45° rotation with growing k, and maybe you will find the farthest points are with cost k.

            → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      adityagamer why only fill odds or only fill even. Can we not have some combination of odd and even? like (2, 0) (-1, 0)??

      → Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    Notice that, if you have 1 chip you can put it in (0,0) therefore answer is 0. If you have 4 chips you can put them in (1,0), (1,1), (0,1), (0,-1). If you have 9 chips you can put them (-2,0),(-1,1),(0,2),(1,1),(2,0),(1,-1),(0,-2),(-1,1) and (0,0). You have to notice that solution is ceil(sqrt(n))-1.

    → Reply
»
21 month(s) ago, # |
← Rev. 2   Vote: I like it +6 Vote: I do not like it

My approach in D was to iterate on the number of elements to remove, If we remove i elements then we'll remove those which contribute most to the number of inversions(leftmost 1s or rightmost 0s) Is there something wrong?

Edit : Just saw some solutions of other people and looks like I went completely off tracks..

→ Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

i try some inversion contribution type things in d problem But i didn't get anything Any hint for d problem

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I used standard dp with memoization for: position, whether there was a previous 1 in the array, and whether we swapped

    → Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    After trying some cases, you will found out that swapping elements $$$\ge 2$$$ times is worse than deleting an element. Therefore, you only need to check the minimum number of elements to delete for not swapping and swapping once.

    → Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Try to think about greedy, what is the relationship in position between numbers that should be removed, and those that should be kept?

    → Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +3 Vote: I do not like it
    Hint 1
    Hint 2
    Hint 3
    → Reply
»
21 month(s) ago, # |
  Vote: I like it +5 Vote: I do not like it

Can someone teach me or refer me to a resource where I can learn to make my DP not ugly? I learned DP on Leetcode and for multidimensional DP I will do something like:

int dp[MAX_N][b][c][d] = {};

memset(dp, -1, sizeof dp);

But this doesn't work on Codeforces because testcases may be <= 1e5 and initializing the DP array for this many testcases results in TLE. So on Codeforces like this contest's problem D I ended up using:

vector<vector<vector<vector<vector>>>> memo(s.length(), vector<vector<vector<vector>>>(2, vector<vector<vector>>(2, vector<vector>(2, vector(2, -1)))));

But surely there's a better way to do this, right?

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    instead using memset,for each testcase manually set dp state as -1 for only n(size of array) positions in dp array.

    Because there are always constraints like, for all testcase sum of n will be <=3e5 or something

    → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks, this sounds much easier

      → Reply
  • »
    »
    21 month(s) ago, # ^ |
    ← Rev. 2   Vote: I like it +5 Vote: I do not like it

    In c++ 20, you can write multiple dimensional easily. For example for 3d, you can write: vector a(n, vector(n, vector<int>(n,-1)));

    → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks, this is a lot cleaner

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

      But if we want to pass it in function then we have to write in old fashion ?

      → Reply
»
21 month(s) ago, # |
  Vote: I like it +9 Vote: I do not like it
Problem B and Google Calculator
→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    So true, I solved it with sqrt but I don't have proof.

    → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I still don't understand how root of number is connected

      → Reply
      • »
        »
        »
        »
        21 month(s) ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        You can create square of x * x points with (x-1) maximum value for all the points

        I don't have proof but I drawed it for different even and odd values.

        → Reply
»
21 month(s) ago, # |
  Vote: I like it -25 Vote: I do not like it

include<bits/stdc++.h>

using namespace std;

define endl "\n"

define ll long long

int main() { ios::sync_with_stdio(false); cin.tie(0);

int t; cin>>t; while(t--) { string s; cin>>s; map<char,int>mp; for(auto i:s) { mp[i]++; }
if(mp.size()==1)cout<<-1<<endl; else if(mp.size()==4)cout<<4<<endl; else { if(mp.begin()->second==1||mp.begin()->second==3)cout<<6<<endl; else cout<<4<<endl; } }

}

Why this code don't work 1st problem... Can anyone help me out?

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +2 Vote: I do not like it

in C++20 inbuilt sqrt() is giving wrong answer but in C++17 it's accepting?? sqrtl() worked for C++20

→ Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

How did so many people figured out answer for B is sqrt(n-1) is this some known concept or if someone could share how they landed up on this solution.

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    checking the last sample test case

    → Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    I just draw it on the plane, and noticed that max distance changes over powers of consecutive numbers(1^2, 2^2, 3^2 etc.)

    → Reply
»
21 month(s) ago, # |
  Vote: I like it +40 Vote: I do not like it

In the beginning 5min, the server was heavier than usual, hope the situation becomes better until the coming Div1+2.

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it -13 Vote: I do not like it

    Hi, a totally unrelated question but it would be great if you could help me. Can you look at my profile and tell me whether I am doing something wrong coz I feel like I am unable to solve D questions of DIV2's. I usually practice in the range 1400-1900(sometimes 2000, but not often).

    I get it I need to solve harder problems to solve 4th question but then should I stop solving < 1600 rated questions and just focus on the harder ones?

    Thanks!

    → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it +7 Vote: I do not like it

      When practicing, you should not solve easy problems. I won't give an exact rating because it depends, but the easiest problems you should solve when practicing should probably take you at least 45 — 60 minutes to solve completely (from first reading the statement to getting AC). Obivously I'm not saying that you're not allowed to solve some easier problems every now and then if you find something you'd like to solve, but know that it is really effective if you just focus on the harder problems.

      Also remember that it is (almost) equally important to be able to solve easy problems fast and with very few or no wrong answers in contests. The best way to practice this is by doing contests; the second best way is by doing virtual contests. But I'd still say that most of your practice should be doing hard problems if you want to improve quicky. It will take a lot of effort but I promise it is worth it. And don't feel demotivated if you can't find the time of motivation to solve hard problems on some day. You should practice when you feel like it and you should not force yourself to do it (unless you actually want to, but then it's your own choise).

      → Reply
      • »
        »
        »
        »
        21 month(s) ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I'll try to stick too it.. but most of my <1600 rated problems are for speed practice :/. I try to do a couple of 1700-1900 ranged questions everyday so that I actually feel myself struggling a lot and then I do a couple of managable ones to improve speed

        → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it +32 Vote: I do not like it

      First of all, the difficulty of D2D is not so stable. Sometimes it's 1400 and sometimes 2400. So it's better to aim to solve Xdiff than Xth question.
      In my experience,

      • (Stable rating -500 or lower): You must solve this task almost 100%. Good to use for the practice of speedsolving.
      • (Stable rating -400 to -300): You must solve this task with high probability, but sometimes you can't solve this (and if that case, the problem includes a new concept for you)
      • (Stable rating -200 to +200): 50% zone. Practice and gaining the probability of solving the problems of this range is the fastest way to growth (but don't forget, practicing only in this zone isn't enough). It's good to use VCs including these problems.
      • (Stable rating +300 or higher): Challenge zone. Too much practice in this zone isn't effective(or even harmful?), but it's good for learning the process to solve very difficult problems.
      → Reply
      • »
        »
        »
        »
        21 month(s) ago, # ^ |
          Vote: I like it +11 Vote: I do not like it

        Your stable rating is about 1700, so stop practicing <1600 is bad idea because you can't find the things you don't know(or you can't do), and also can't practice speedsolving. keep going!

        → Reply
        • »
          »
          »
          »
          »
          21 month(s) ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          I see, thanks!

          Seems like I am on the right path

          → Reply
»
21 month(s) ago, # |
  Vote: I like it -6 Vote: I do not like it

I'm waiting for the proof of B.

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I think it was more of guessing than educational :((

    → Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    It will create a series of 4,8,16,24,36,48,64,80,....

    We can rewrite the series 4*(1,2,4,6,9,12,16,20,25,30,...) which is a quater squre.

    Here are two picture

    → Reply
  • »
    »
    21 month(s) ago, # ^ |
    ← Rev. 2   Vote: I like it +4 Vote: I do not like it

    n^2 points fully fills a diamond with cost n-1. in other words, the minimum cost for n^2 is n-1, and n-1 cost hold a maximum of n^2 points. so if (n-1)^2<x<=n^2, minimum cost for x would be n-1.

    → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      kinoud how to see that n — 1 cost will only have maximum of n^2 points?

      → Reply
      • »
        »
        »
        »
        21 month(s) ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        hint: if (x,y) is selected, then its up, down, left, right should be empty. if you draw lines: up--left--down--right--up, they forms a diamond with area of 2. so every selected point covers an area of 2. and no two selected point cover shared areas.

        → Reply
»
21 month(s) ago, # |
  Vote: I like it -10 Vote: I do not like it

I think the round should be made unrated

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +28 Vote: I do not like it
    Spoiler
    → Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it -8 Vote: I do not like it

    yes it should be unrated because at beginning of the contest there was a lot of traffic on site due to which it took a lot of time to load the problem and also showed gateway error.

    → Reply
»
21 month(s) ago, # |
← Rev. 2   Vote: I like it +2 Vote: I do not like it

Problem B might be my least favorite problem ever, hopefully I can understand the solution when the editorial comes out, not just have people say they've guessed it :D

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +14 Vote: I do not like it

OOOOOOOOOOMG!I finally passed a C in div2

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +1 Vote: I do not like it

Badly stucked in B.

→ Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Other than a terrible Div2 B, this was a great contest.

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Agreed, I drew a square pattern on a piece of paper, brute forced the answer to n = 9, then decided to take a guess and output sqrt(n-1).

    → Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    No, B was great. It is not the authors' problem that you can't use sqrt function properly.

    → Reply
»
21 month(s) ago, # |
← Rev. 2   Vote: I like it +4 Vote: I do not like it

B is so hard. how does it get so many ACs? What's the solution for B? I used binary search for even and odd count of points on one side and do a sum series. But it's so complex. What's the easier solution?

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I used pen and paper for when ans = n — 1. I was able to draw n * n points. in each quadrants n points.

    → Reply
»
21 month(s) ago, # |
← Rev. 3   Vote: I like it +18 Vote: I do not like it

...(sorry for multiple comments caused by internet connection issue)

→ Reply
»
21 month(s) ago, # |
← Rev. 8   Vote: I like it +61 Vote: I do not like it

First time solved div2 A-F in 1.5 hours. (1801B - Buying gifts: What did you say?)

A: We can count the occurence of each color. There are only 5 ways to divide 4 bulbs into different colors: 1111, 112, 22, 13, 4. The answer for these situations are 4, 4, 4, 6 and -1.

B: The optimal way to place chips: choose an upper bound k, place chips on all points (x, y) with |x|+|y|<=k and (k-|x|-|y|)%2==0. We can find the optimal k by binary search.

C: We consider array {s[i]}=a[1]+a[2]+...+a[i], where 0<=i<=n, then {s[i]} will have exactly n*(n+1)/2-k inversions. First we let s[i]=i, the initial inversion number is 0. Then we swap some pairs of adjacent elements to increase the number of inversion. We can do this like what we do in bubblesort: first for j=0...n-1 do swap(s[j], s[j+1]), then for j=0...n-2, then for j=0...n-3, and so on. Every swapping will increase inversion number by 1. When we reach n*(n+1)/2-k we stop swapping and output {s[i+1]-s[i]} as answer.

D: It's optimal to use at most 1 swap operation (that's something like 00010111 -> 00001111). We need to choose an index i, remove all occurences of 1 on its left, and remove all occurences of 0 on its right. But if there are something like ...[1]0|11..., instead of removing [1], we can move it to right by swapping and save 1 coin. Similar for something like ...00|[1]0... , so we can solve the problem by prepare prefix-sums, suffix-sums and look for all choices of i.

E: Consider for all pairs of (c, d) with same value of t=c+d. Let v1 and be the current volume of water in the first and second tank. Then in the whole process, we have 0<=v1<=a and 0<=v2<=b. since v2=t-v1, we can write the second inequality as t-b<=v1<=t, then we have max(0, t-b) <= v1 <= min(a, t). Then for all possible values of c in this range, the lower bounds and upper bounds of v1 are the same, so we can let f(v;i,t) be the value of v1 after we do the i-th operation if v1=v before the operation and v1+v2=t, then the answer is the composition of functions f(_;1,t), f(_;2,t), ..., f(_;n,t). We can observe that every possible compositions can be determined by a tuple (f0, x1, x2), which means:

-if x<x1, f(x)=f0.

-if x1<=x<=x2, f(x)=f0+(x-x1).

-if x>x2, f(x)=f0+(x2-x1).

For each value of t we can find the answer for (c, d) with c+d=t by doing function compostions by some caseworks, and we can solve the problem in O(n*(a+b)+ab).

F: The optimal solution is: Fill fuel for the remained journey at cities with b[i]=1, and fill fuel to reach the next city at cities with b[i]=2. Thus when we leave a 1-city, we have at most k-a[i] liters of fuel for following 2-cities, which means we can save min(k-a[i], a[i+1]+...+a[j]) liters of fuel, where [i+1, j] is a maximal block of 2-cities. So the answer of all 1-cities are the same, and for some 2-cities we need to consume more fuel because we lost the opportunity for saving fuel.

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
    ← Rev. 2   Vote: I like it +39 Vote: I do not like it

    Holy hell, the inversion model and solution for problem C is really cool. Now the model approach (which was written by me) looks lame.

    → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      This also allows a linear time solution for problem C(as it just boils down to building a permutation with k inversions): https://mirror.codeforces.com/contest/1809/submission/198841950

      → Reply
      • »
        »
        »
        »
        21 month(s) ago, # ^ |
          Vote: I like it +16 Vote: I do not like it

        My solution can also be improved to linear, although I wrote it in recursive fashion without improving, so it works in $$$O(n^2)$$$. When designing this problem, I envisioned an approach which gradually reduced the problem to smaller values of $$$n$$$ and $$$k$$$.

        Basically, I consider two cases:

        • if $$$k < n$$$, it's quite easy to build the answer. Although I impose an additional constraint (which I'll need later) that the sum of elements in the whole is greater than $$$-1000$$$. Even with this constraint, it's quite easy: I make something like $$$[-1, -1, -1, \dots, -1, 100, -200, -1, -1, -1]$$$, where $$$100$$$ is the $$$k$$$-th element of the array. All segments ending with the $$$k$$$-th element are positive, all other segments are negative.
        • but if $$$k \ge n$$$, I reduce $$$k$$$ by $$$n$$$ and $$$n$$$ by $$$1$$$ by making sure that all segments containing the first element of the array are positive. So, I set the first element to $$$1000$$$, and arrive at the same problem with reduced $$$n$$$ and $$$k$$$.
        → Reply
        • »
          »
          »
          »
          »
          21 month(s) ago, # ^ |
          ← Rev. 3   Vote: I like it +6 Vote: I do not like it
          • I did a much simpler solution in O(n)
              int i=1;
    while (k>n)
    {
        cout<<"1000 ";
        k=k-n;
        n=n-1;
        i++;
    }
    i=1;
    cout<<(k*2-1)<<" ";
    i++;
    while (i<=n)
    {
        cout<<"-2 ";
        i++;
    }
    cout<<endl;
          • Now, Understand my intuition,
          • solving for k<=n:
          • Print kth odd number and then print -2 (n-1 times)
          • Why?
          • To understand, see these test cases, You would understand the reasoning by your own observation:
          • n=4 k=1 :-> Array={1,-2,-2,-2}
          • n=4 k=2 :-> Array={3,-2,-2,-2}
          • n=4 k=3 :-> Array={5,-2,-2,-2}
          • n=4 k=4 :-> Array={7,-2,-2,-2}
          • So you get it now if k<=n then kth odd number and rest all -2's will give you k positive sub-arrays.
          • Now if k>n,
          • Then print 1000 and
          • change k to k-n and change n to n-1
          • And until k remains more than n
          • Keep printing 1000
          • Then ultimately k will become k<=n
          • Now you already have the method to print an array for k<=n
          • Feeling like you do not know what's going on?
          • Then Feel it by these test cases,
          • n=4 k=5 :-> Array={1000,1,-2,-2}
          • n=4 k=6 :-> Array={1000,3,-2,-2}
          • n=4 k=7 :-> Array={1000,5,-2,-2}
          • n=4 k=8 :-> Array={1000,1000,1,-2}
          • n=4 k=9 :-> Array={1000,1000,3,-2}.

          • If you still do not get it then just make observations by my given test cases and you'll be infering the solution itself

          → Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    What is this notation, {s[i]}=a[1]+a[2]+...+a[i] or {s[i+1]-s[i]}?

    → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      First: 0, a[1], a[1]+a[2], a[1]+a[2]+a[3], …

      Second: s[1]-s[0], s[2]-s[1], s[3]-s[2], … which is same as a[1], a[2], a[3], …

      → Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Is there a simple proof that at most 1 swap is optimal? I have a proof but it doesn't feel direct enough.

    → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Can you explain your proof?

      I have an idea but I'm not sure if it is correct or not.

      Think about when you have 2 swaps.

      Case 1: Swap same element [Example: 100]

      You can just remove the 1 instead of swapping.

      Case 2: Swap different elements [Example: 10 ... 10]

      After swapping both pairs, the second 0 will still be after the first 1, and it would be more optimal to just directly remove the second 0.

      → Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    And how did you notice that the number of inversions corresponds to the subarrays of the required sums? Thank you.

    → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Sum of subarrays = difference of prefix-sums

      This is a useful technique for many d2B-d2D problems.

      → Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    why not only remove ones in d why both zeroes and ones????

    → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      For example: 1111110111111 we can remove the single occurence of 0.

      → Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

there's no way to get a correct answer on B unless you binary search the square root, did none of the testers notice this?

→ Reply
»
21 month(s) ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

You can solve B by this observation: one way to start placing chips is to start at [0,0] and then place chips a total distance 2 from the first one on positions [0,2], [1,1], [2,0], [1,-1] etc., forming a kind of a "star" this way, following this pattern you can place 8 + 1 starting chips, then each next amount of chips is greater than the previous one by 8 and the distance is going to increase by 2, so we end up with an arithmetic series which total sum is equal to:

1 + (k / 2) * (8 + (k-1) * 8), this should be equal or greater than the total amount n of chips that we want to place. After solving the quadratic, the minimum distance would be equal to 2 * k.

Another way to start is by placing 4 chips on positions [1, 0], [0, 1], [-1, 0], [0, -1], this way we can minimize the initial cost of placing chips to 1. Similar to the previous case, each next step we can place 8 chips more than the last step, each time increasing the total cost by 2.

In this case we end up with sum looking like this: 4 * k^2 = n, so the total amount of times k we should place portions of chips should be equal to k = sqrt(n) / 2 (careful with the rounding). The total cost in this case will be 1 + (k-1) * 2.

After we calculated the cost for each of two methods we should take the minimum one, that is our answer.

→ Reply
»
21 month(s) ago, # |
← Rev. 2   Vote: I like it +16 Vote: I do not like it

...(sorry for multiple comments caused by internet connection issue)

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +1 Vote: I do not like it

Anyone know B test2 5002nd input?

wrong answer 5002nd numbers differ — expected: '999999999', found: '1000000000'

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    sqrt issue.

    → Reply
  • »
    »
    21 month(s) ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    its 10^18, its a problem on their side, i think, i have msys 2 gcc, i ran it on my device and got the right answer, any compiler except gnu c++17 gives wrong answer. I hope they compensate for that specific test case. EDIT: Sorry, this is a noob question, it worked using sqrtl(), though i don't understand how even sqrt gave the correct answer on c++17

    → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      maybe its not 10^18 i test it, my ansower is 999999999 not 1000000000

      198838252

      → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      i get it, like 1000000000000000000L-50L

      → Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Why in problem B, data

1

1000000000000000000

The answer is 31622776 is an unsuccessful hack?

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Sorry, I made a mistake myself. I outputted a 1e17

    → Reply
»
21 month(s) ago, # |
← Rev. 3   Vote: I like it +19 Vote: I do not like it

We found a guy **https://mirror.codeforces.com/profile/LUFFY_02** LUFFY_02 he has created three fake accounts __LuFFy LuFFy___ -LuFFy- he use to do correct submission from his official account and hacks his solution in fake accounts by putting a edge case on test cases for getting successful hacks. 198783958 198783958 198784476 198784572 198783173 198780641.

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it -30 Vote: I do not like it

    Well, I did that first time today, to see how much it's gonna change.... There's no +ve delta for hacks right? So this wont be a issue if I did it today just to see how much it affects :/

    → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      Yes, there's no positive delta for hacks, but in according to the contest rules you're not allowed to use more than one account. Although this didn't really cause any harm, you shouldn't do it again.

      → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      If you did this in div2. You would have probably gained a huge amount of points. That's equal like solving another problem.

      → Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I saw that too, this [user:https://mirror.codeforces.com/profile/SCOR_PION] and [user:https://mirror.codeforces.com/profile/__LuFFy] accounts are fake and are getting used for hacked submissions

    → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      He is genuine guy just the curious one. I was suspecting him too. Then i saw his graph looks decent hardworking guy to me.

      → Reply
»
21 month(s) ago, # |
  Vote: I like it -8 Vote: I do not like it

Unethical hacking attempts are going on in this contest. I'm unsure if the hacks contribute to the rating for this event, but similar hacks can be performed in other contests. I have explained how this is being done there. https://mirror.codeforces.com/blog/entry/114270

Please check out and make sure this won't happen further

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +3 Vote: I do not like it

Awesome Problem F!

Solution Sketch

198831015

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +18 Vote: I do not like it

Spent 1.5 hr making useless drawings for B.

Cyan color will suit me.

→ Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Am i the only one who solved D by DP , maybe i overcomplicated it :(

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    I don't think anyone solved D with an uglier DP solution than mine. 198822901

    → Reply
  • »
    »
    21 month(s) ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Can you explain your dp state ? @AdityaG

    → Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    I did too, 198854887

    → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      Can you please tell what does the line array<int, 2> ans = min({dp[n][0], dp[n][1], dp[n][2]});do?
      Does it assign the minimum $$$2$$$ values out of those $$$3$$$ to the array?

      → Reply
      • »
        »
        »
        »
        21 month(s) ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Hi! dp[n][0], dp[n][1] and dp[n][2] are all instances of array<int, 2>, so it compares all of them and returns the minimum of them. Think of it as sorting those 3 elements (except with direct comparisons instead of sorting) and returning the first of them.

        → Reply
        • »
          »
          »
          »
          »
          21 month(s) ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          So what is the difference between int ans = min({dp[n][0], dp[n][1], dp[n][2]}); and array<int, 2> ans = min({dp[n][0], dp[n][1], dp[n][2]}); ?

          → Reply
          • »
            »
            »
            »
            »
            »
            21 month(s) ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            The difference is that the first line won't work at all, since all of the elements you are comparing are array<int, 2>, so it will return an array<int, 2>. I'm storing it in such a way because it allows us to maintain both the total number of operations and the number of deletion operations, which I guess isn't needed. You can reimplement it with long longs instead of array<int, 2> used everywhere.

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              21 month(s) ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              OK Yes, understood.
              My bad, didn't even look at the global declaration.
              Thank you!

              → Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Could someone help me out with how to combine observations in problems like D, I was able to find out that if I perform a swap operation, both the numbers should reach their correct positions , like on 0010111 -> 0001111 , but I wasn't able to do anything after that. I don't understand why I can't come up with a solution even after getting good observations. Please help

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    I will omit the part about importance of proving observations. Considering the fact that you and I are green as hell, I think having at least "proofy" gut feeling of correctness, or being unable to construct counterexample should be enough to solve ( guess).

    Your so called observation: if I perform a swap operation, both the numbers should reach their correct positions. What do you exactly mean by that? One way to interpret: perform swap only if it yields to correct position. But then it means that all of the performed operations are deleting, excluding only maybe the last operation. I won't continue because your observation is wrong anyway. What I intended to show by writing all of this is that, as you could not evolve your idea even if it is wrong shows me that you can't interpret your intuition in terms of strict statements and/or you don't really understand what observation means, have little to no experience of proving statements. I think you should try proving all of your observations or construct counterexamples during practice. At first it is hard, but as you gain experience in proving things, and gain experience, it will really become a second nature. Good observation for this problem will be (don't read if you want to try again):

    Spoiler
    → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Ohhk I get it , btw thanks for help .

      → Reply
      • »
        »
        »
        »
        21 month(s) ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Good luck bro

        → Reply
        • »
          »
          »
          »
          »
          21 month(s) ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Yes u were right there that I was thinking all operations before this were deletion, and anyhow by some kind of deletions I was thinking to make the string look like 00010111 so that my last step performs a swap .

          → Reply
»
21 month(s) ago, # |
  Vote: I like it +30 Vote: I do not like it

About problem F:

Don't get me wrong, I'm not trying to say that this problem should not appear in the contest, it's ok and seems like a lot of people liked it, but there is much harder version of this problem from joi 20-21. It's a really cool problem, for those who solved problem F, I recommend to solve it as well, here is the link and you can submit here.

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    is there any english editorial of it?

    → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      I'm not sure, I didn't find it. But here is a short solution. I hope it will help in case you don't know what to do.

      Solution
      → Reply
»
21 month(s) ago, # |
  Vote: I like it +1 Vote: I do not like it

in Educational Codeforces Round 145 (Rated for Div. 2) in problem 1809B - Points on Plane during the contest i have submit code with C++20 and had Wrong answer on test 2 and after the contest i submit it again with C++17 and had been Accepted 198780726 Wrong answer on test 2 198858827 Accepted anyone to say why?

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +3 Vote: I do not like it

I solved B using binary search...didn't think of any other methods during the contest. Learned a lot! Epic round huge thanks to the authors!

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +1 Vote: I do not like it

In Question C, It's giving wrong output on test case 7,i.e, n = 17, k = 48 my output is 2 4 6 8 10 12 14 16 18 -79 -500 -498 -496 -494 -492 -490 -488 this output is having exactly 48 positive subarrays. but codeforces is showing wrong answer. It is request to codeforces to see this issue asap as my rating will affect vastly in this case. here is my submission link : https://mirror.codeforces.com/contest/1809/submission/198828726

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I just view your submission and it show that you wrong in this case (codeforces also comment why you fail): n=30, k=319

    Checker comment
wrong answer the number of segments with positive length should be 319, but is 325 instead (test case 4)
    → Reply
»
21 month(s) ago, # |
  Vote: I like it +3 Vote: I do not like it

Damn I suck at Geometry, my brain froze at B :(

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +3 Vote: I do not like it

Why is this guy Mido. submitting all these different solutions ( 198880211, 198880252, 198880324, etc) for Problem A while giving different edge cases that would fail to let AhmedSayed. hack all of them? This is weird...

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +4 Vote: I do not like it

Great contest! I have a editorial video (dicord discussion) on this contest, where problem A, Problem B, Problem C and Problem D have been discussed. you can view it here- video editorial!

Thanks!

→ Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Educational contest（×） Reverse pair contest（√） problem C and E are good as problem conversion exercises

→ Reply
»
21 month(s) ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Failed to notice in D operation 2 is always better than swapping as long as the swapping letter is not consecutive
Though it makes me wonder: what if the costs of two operation is given in the form of a, b? I think I got a solution but not sure about it.

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +26 Vote: I do not like it

Where's editorial

→ Reply
»
21 month(s) ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Question c Why did my code make an error at the test point of 17 48： https://mirror.codeforces.com/contest/1809/submission/198828047 but When I modified the output rule, it passed： https://mirror.codeforces.com/contest/1809/submission/198884256

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    When all the subarrays need to be positive you are still printing a negative value at the end in the first version.

    testcase (you print 3 values for this, n = 2):

    1
2 3
    → Reply
»
21 month(s) ago, # |
  Vote: I like it +1 Vote: I do not like it

Update in Ratings?

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +4 Vote: I do not like it

Why AC code getting WA ??
AC: https://mirror.codeforces.com/contest/1809/submission/198912757
WA: https://mirror.codeforces.com/contest/1809/submission/198912608

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I got into similar issue during contest. I have used Math.sqrt()[java], but not sure why it was failing in 2nd testcase.

    → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      I used

      while (sqrt * sqrt < n) sqrt++;

      Because you can get sqrt(25)=4.9999..

      → Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    The only difference is the language chosen. Check the differences in both versions.

    → Reply
  • »
    »
    21 month(s) ago, # ^ |
    ← Rev. 2   Vote: I like it +3 Vote: I do not like it

    sqrt is floating point (using the double type), and the c++ specification doesn't require double to be accurate enough to solve the problem.

    The implementation is allowed to use higher precision for calculations if available and 32bit x86 tends to use 80bit floating point for intermediate results, 64bit will usually keep everything at 64bit. If you want to know exactly why then https://randomascii.wordpress.com/2012/03/21/intermediate-floating-point-precision/ is a good read.

    → Reply
»
21 month(s) ago, # |
← Rev. 3   Vote: I like it +1 Vote: I do not like it

B is a Good problem

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +5 Vote: I do not like it

Is this contest unrated ?

→ Reply
»
21 month(s) ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

same code :

WA : c++ 20 : 198836355 AC : c++ 17 : 198857463

→ Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Upload the editorial please. Can someone explain how to solve E. I can't come up with any kind of logic

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +8 Vote: I do not like it

Did anyone else miss the fact that $$$1\leq b_i \leq 2$$$ in problem F? :(

I know it can be solved without that restriction, but that simplifies the problem a lot.

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +3 Vote: I do not like it

Please release editorials soon.

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I am also waiting for the editorial to be released... I think it will be released after the rating changes updated..

    → Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Was this round unrated because the blog says this was rated ??

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +8 Vote: I do not like it

When will the ratings be updated? I am so much excited to cross 1200 for the first time.

→ Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Hi guys, I hope I'm not bothering you with my question, but I've seen that I haven't been classified in this last contest, could someone tell me why...

→ Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

So the rates still don't be updated yet?

→ Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Have the final tests run? I don't see any failed system test, only hacks

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +4 Vote: I do not like it

Can anyone please suggest a good Rating predictor extension or website..? The waiting for this rating update is too long.....

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    I use carrot (https://addons.mozilla.org/en-CA/firefox/addon/carrot/) for rating prediction

    Chrome link: https://chrome.google.com/webstore/detail/carrot/gakohpplicjdhhfllilcjpfildodfnnn?hl=en

    → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      How accurate carrot is for rating prediction. I felt like it predicts much higher +ve delta than actual +ve delta that you will get actually.

      → Reply
      • »
        »
        »
        »
        21 month(s) ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        From using it it's been pretty accurate, maybe at most about an error of +-5 points. Since it's calculating the changes based on the current results the eventual rating change can fluctuate a bit due to people being removed from the rankings for whatever reason. Also Carrot will probably have some weird predictions on the first 6 contests since it 's calculating rating change based on the visual rating rather than internal rating

        → Reply
      • »
        »
        »
        »
        21 month(s) ago, # ^ |
        ← Rev. 3   Vote: I like it 0 Vote: I do not like it

        For me, it's worked good.

        The difference between my actual rating and predicted rating usually less than 30 (I guess). Sometimes it's my actual rating > predicted rating and sometime it's opposite.

        Note: The final result after system running may change a lot because some reasons (some contests has many failed final tests)

        For example:

        In Codeforces Round 859 (Div. 4) it predict I will +67, but the real is +51

        In Codeforces Round 857 (Div. 2) it predict I will +20, but the real is +38

        → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      thank you so much...

      → Reply
»
21 month(s) ago, # |
  Vote: I like it +11 Vote: I do not like it

Auto comment: topic has been updated by awoo (previous revision, new revision, compare).

→ Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Why it take longer time for educational rounds rating update?

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +26 Vote: I do not like it
Spoiler
→ Reply
»
21 month(s) ago, # |
  Vote: I like it +3 Vote: I do not like it

I need +42 to reach specialist, and the carrot extension is showing + 56. Hope, I reach in this contest only, even if I miss by few points, after this contest, I have confidence that I would definitely reach specialist in the next one!!

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
    ← Rev. 4   Vote: I like it 0 Vote: I do not like it

    how accurate is the carrot predictor, I read up above that it becomes more accurate after 6 contests or so you know how accurate is it

    → Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone tell me how much times does educational round takes to update the rating ig there is a delay as compared to other contests?

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +10 Vote: I do not like it

I am sorry guys, since i am mastering, Mike gonna make all of you wait 1 more day

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +9 Vote: I do not like it

Finally!

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +3 Vote: I do not like it

I noticed something weird regarding rating changes. Me and the person next to me both got the exact same rank (226) and our initial ratings are only 1 apart. However, our rating changes are significantly different (+137 vs +172). Heres the picture for reference https://imgur.com/a/vU5nqyT.

Does anyone know why this happened?

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    I suspect it's because it's only frgnhite's 6th contest, and their true rating was not shown prior to the contest. Users start from a rating of 1400, but it is shown as starting from 0 (to not discourage people), and so, are shown a reduced rating to show progress. After each of the initial few contests, this reduction is reduced, until eventually (at 6 contests maybe) it shows their true rating.

    → Reply
»
21 month(s) ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Can someone explain me this rating change ??? Like I just saw a higher rated coder who got higher rank than me got more rating changes??? Also some peoples with 0 problem solved and wrong submissions got +ve del???

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    For the first situation that's natural...if the rank is high enough why not...? For the second the first 6 contests of each account works in particular with a base line of 1400(that's if you just meet the level you'll precisely reach it after 6 participations,+500/350/250/150/100/50),and in the quick ranking one gains more rating points(turning negative to positive inclusively). Pretty hard to get a negative rating change in this peroid

    → Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

I really liked problem E, it reminded me of IOI21 Candies.

→ Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Hi I have a problem. My submission is https://mirror.codeforces.com/contest/1809/submission/199501601 and it told me that in test 2, the 22nd test point I got wrong answer. The input is "22 232" and my output is twenty-two 2 and one -41. I think my output is correct, can anyone help me?

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    okay I figure it out. I am an idiot. That's why I cannot get a medal in ICPC.

    → Reply