When submitting a solution in C++, please select either C++14 (GCC 6-32) or C++17 (GCC 7-32) as your compiler. ×

By awoo, history, 12 months 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

»
12 months 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."

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

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

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

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

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

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

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

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  12 months ago, # ^ |
                    Vote: I like it -39 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."

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

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  12 months ago, # ^ |
                    Vote: I like it -37 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."

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  12 months ago, # ^ |
                    Vote: I like it -8 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."

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  9 months ago, # ^ |
                  Rev. 2   Vote: I like it 0 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."

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

    .

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

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

This time there should not be any issue...

»
12 months ago, # |
  Vote: I like it -13 Vote: I do not like it

Hope contest will provide positive delta to all.

open please
»
12 months 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.

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

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

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

almost 30k registered in edu round *_*.

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

Hoping there will be no network issue today!

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

Hope to perform better

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

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

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

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

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

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

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

how to solve c?

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

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

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

      • »
        »
        »
        »
        12 months 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
      • »
        »
        »
        »
        12 months ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        (Everything is 1-indexed) Case 1: k is 0 fill whole array with -1.

        Case 2: k is of the form (n*(n+1))/2. Let x = (n*(n+1))/2. Fill the first n elements of the required array with 1 and the remaining ones with (-1000)

        Case 3: k is not of the form (n*(n+1))/2. Find highest index i such that (i*(i+1))/2<k. Let count=k-(i*(i+1))/2. Fill first count elements of the array with 30 and remaining elements upto i with 1. Fill ith index with -31 and rest of the array with -1000

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

How to solve B?

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

    Output sqrt(n-1)

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

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

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

        n = (1+K)^2

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

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

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

              Thank you. It's really like a filled square. And the area of the square is a square. You could have guessed by that, too.

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

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

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

      Used these formulas only. Here are some math on it.

      sequence go in this way

      odd : 4(1 + 3 + ... + (2k - 1)) -> sum = 4(k^2) -> maxCost = 2k - 1
      even: 1 + 4(2 + 4 + 6 + ...+ 2k) -> sum = 4(k^2) + 4k +1 -> maxCost = 2k
      

      Note : here for even distance 0 -> there is only one point.

      if we loop over this for some starting numbers we will get to know that it follows the sequence of square over maxCost.

      cout << "maxCost, max num of points plotted" << endl;
      	forn(i, 0, 10)
      	{
      		int odd = 4 * i * i;
      	
      		int even = odd + 4 * i + 1;
      	
      		cout << 2*i - 1 << ", " << odd  <<  endl;
      		cout << 2*i << ", " << even << endl;
      	}
      

      Like maxCost, max num of points plotted (0, 1) (1, 4) (2, 9) (3, 16) (4, 25) (5, 36) (6, 49) (7, 64) (8, 81) (9, 100) (10, 121) (11, 144) (12, 169) (13, 196) (14, 225) (15, 256)

      Based on this the answer would be

      	int t;
      	cin >> t;
      	
      	while (t--)
      	{
      		int n;
      		cin >> n;
      		int root = sqrtl(n);
      		int ans;
      		if(root * root == n)
      			ans = root - 1;
      		else
      			ans = root;
      		
      		cout << ans << endl;
      	}
      
    • »
      »
      »
      12 months 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)??

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

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

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

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

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

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

  • »
    »
    12 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it
    Hint 1
    Hint 2
    Hint 3
»
12 months 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?

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

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

      Thanks, this sounds much easier

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

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

      Thanks, this is a lot cleaner

    • »
      »
      »
      6 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 ?

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

    I also came across this problem few years back I figured out these two ways to get that done.
    1. Declare the dp vector a(n , vector<int>(n , -1)) in the main itself and pass by reference to every function using this vector.
    2. Declare a global dp vector<vector> a and then clear and resize the vector based on each testcase constraint a.clear() a.resize(n , vector<int>(n , -1)) or in one liner a.assign(n , vector<int>(n , -1))

    Note-> don't forget to clear the vector after each Testcase
    If there is any better way let me know

»
12 months ago, # |
  Vote: I like it +9 Vote: I do not like it
Problem B and Google Calculator
  • »
    »
    12 months 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.

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

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

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

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

    hint:

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

    shifting to bing after this contest

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

can anyone provide a python solution for the points on plane problem. I think sqrt gives an error here in python.

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

    Use Binary search to find the square root and if its a true square then output result-1 else result.Check my solution

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

      Thank you for this approach. However, I got a usual answer using root but it has some strange behavior. However, it is accepted entirely.

      I have got this soln from the comments.

      Check this

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

Hardforces

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

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

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

    yes and because of that i got 3 penalties

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

    same Then i use sqrtl() instead of sqrt()

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

    Yeah, for this reason, I got 6 penalties. Whoever uses C++17 they got correct in using sqrt(),but I using same in C++17(64) ,I got wrong.

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

    yes and because of tha I got 6 penalties.

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

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

    checking the last sample test case

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

      this problem taught people to guess the solution, however it's useful

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

  • »
    »
    12 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    1. Cleary You want your points to be as close to origin as possible
    2. n = 1 is trivial, just place your point at (0,0)
    3. for n = 3 you can place at (0,0) ; (0,1) ; (1,0) so all your values are at max (0+1)=1
    4. Throw : for n = 4 , you try (0,0) ; (1,0) , (0,1) , (1,1) now you (may) see your max equals 2 which might sway you away from trying this particular approach.

    But sometimes, it pays off to calculate a little deeper. Do not abandon your approach so easily

    1. Catch: Are there 4 points (with integer coordinates) who are at max 1 distance from (0,0) == YES!! the key is abandoning the origin and choosing points diamond(/rhombus shaped). (0,1) (1,0) (-1,0) (0,-1)

    2. for n = 5 to 9 you need to fill in (x,y) , based on what we saw earlier (without a formal proof) it's paying off to use points in a diamond shape first.

    3. for n = 10 you see you have to use one of the (+- 2, +- 1) so it was deduced without "formal proof" that the ans should be sqrt(n-1)

    This was the "observation process" for me. Hope that helps. (++ we hav the same name hehe)

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

    by taking multiple test cases and plotting it. you will easily conclude that for n=2,3,4 you got 1, for n=5,6,7,8,9 you got 2 which is sqrt(n-1)....

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

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

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

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

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

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

          I see, thanks!

          Seems like I am on the right path

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

got 3 penalties in que 2 because of using sqrt() instead of sqrtl() fml

»
12 months ago, # |
  Vote: I like it -6 Vote: I do not like it

I'm waiting for the proof of B.

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

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

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

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

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

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

»
12 months ago, # |
  Vote: I like it -10 Vote: I do not like it

I think the round should be made unrated

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

How to solve Problem C. Sum on Subarrays

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

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

OOOOOOOOOOMG!I finally passed a C in div2

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

Badly stucked in B.

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

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

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

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

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

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

    during contest i'was getting demotivated, But after looking some overview of pros like you now i'm happy

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

»
12 months ago, # |
Rev. 3   Vote: I like it +18 Vote: I do not like it

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

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

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

    thankyou so much for this

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

    thanks

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

    • »
      »
      »
      12 months 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://codeforces.com/contest/1809/submission/198841950

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

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

    Thank you!

  • »
    »
    12 months 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]}?

    • »
      »
      »
      12 months 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], …

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

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

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

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

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

        Where to learn this technique ? any resources As iam a beginner , Mention any resources or articles to this concept or resources for other concepts That helped you

        Thanks!

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

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

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

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

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

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

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

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

»
12 months 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'

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

    sqrt issue.

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

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

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

      i get it, like 1000000000000000000L-50L

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

    Try c++14

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

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

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

»
12 months ago, # |
Rev. 3   Vote: I like it +19 Vote: I do not like it

We found a guy **https://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.

  • »
    »
    12 months 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 :/

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

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

        Ohh sure, wont happen again, I was just curious about it so did it. :) Btw I am consistent and my records says more than enough :)

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

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

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

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

      Btw, __LuFFy was hacked first time today :)

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

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

        Thnx and yes, I wont be trying this anymore :(

»
12 months 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://codeforces.com/blog/entry/114270

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

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

I encountered a wierd situation. The following code gives WA on test 2:

import math

for _ in range(int(input())):

n = int(input())

def sol(n):  

    m = math.floor(math.sqrt(n))
    if m*m == n:
        return m-1
    else:
        return m

print(sol(n))

But when I replace "if m*m == n:" with "if m*m >= n:", then the code gets Accepted. But since m = math.floor(math.sqrt(n)), m*m can never be strictly larger than n, so m*m >= n implies that m*m == n.

What am I missing? Thanks for help :)

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

Awesome Problem F!

Solution Sketch

198831015

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

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

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

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

    Can you explain your dp state ? @AdityaG

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

    I did too, 198854887

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

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

        • »
          »
          »
          »
          »
          12 months 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]}); ?

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

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

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

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

      Ohhk I get it , btw thanks for help .

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

        Good luck bro

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

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

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

    is there any english editorial of it?

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

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

»
12 months 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://codeforces.com/contest/1809/submission/198828726

  • »
    »
    12 months 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)
    
»
12 months ago, # |
  Vote: I like it +3 Vote: I do not like it

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

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

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

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

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

»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it
  • C simple solution with intuition 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

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

Where's editorial

»
12 months 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://codeforces.com/contest/1809/submission/198828047 but When I modified the output rule, it passed: https://codeforces.com/contest/1809/submission/198884256

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

Update in Ratings?

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

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

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

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

»
12 months ago, # |
Rev. 3   Vote: I like it +1 Vote: I do not like it

B is a Good problem

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

Is this contest unrated ?

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

same code :

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

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

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

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

Please release editorials soon.

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

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

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

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

    wait bro, rating change will reflect soon

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

      updated....for once i thought it was unrated now I am glad

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

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

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

So the rates still don't be updated yet?

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

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

  • »
    »
    12 months ago, # ^ |
      Vote: I like it +5 Vote: I do not like it
    • »
      »
      »
      12 months 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.

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

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

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

      thank you so much...

»
12 months 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).

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

Why it take longer time for educational rounds rating update?

»
12 months ago, # |
  Vote: I like it +26 Vote: I do not like it
Spoiler
»
12 months 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!!

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

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

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

Where is My Points :(

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

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

Finally!

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

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

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

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

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

Thanks to Edu Round, I am Finally green now and I want to be consistent now for some time So please give some suggestions,folks Thanks!

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

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

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

Hi I have a problem. My submission is https://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?

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

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

can someone tell why i am getting memory limit exceeded? https://codeforces.com/contest/1809/submission/199859980