By awoo, history, 3 weeks ago, translation, In English

Hello Codeforces!

On Jan/08/2023 17:35 (Moscow time) Educational Codeforces Round 141 (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, Vladimir vovuh Petrov, 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 are pleased to announce the second “Hello Muscat 2023” ICPC programming bootcamp, the continuation of the “Hello” bootcamp series, organised by Harbour.Space University, in collaboration with PhazeRo, Gutech, UK Oman Digital Club, Leagues of Code, Gutech CS Club and Codeforces!

Quite exciting, isn’t it? Now it's time for you to dive deeper into the competitive programming world with the 8 days intensive Hello Muscat 2023. It will take place in Muscat, Oman and online from March 8th to March 16th, 2023, both participation formats are available. As always, we can’t wait to see you there to learn, practice and compete on the international stage, smoothing your road towards the joined World Finals 2022 and 2023 in Egypt!

Our coaching line-up combines talent and experience, featuring ICPC world champions winners and finalists, as well as legendary names from the field of competitive programming: Mike Mirzayanov MikeMirzayanov, Yahor Dubovik 244mhq, Artem Plotkin Rox, Maksym Oboznyi MaksymOboznyi and Nikolay Budin budalnik.

The Bootcamp will be split into three divisions:

  • Division A. Division A will be a mirror of the Petrozavodsk Programming Camp. Suitable for teams who already qualified for the world finals ICPC or are aiming that high.
  • Division B. Designed to help teams prepare for the next season of ICPC regional competitions. Appropriate as an introduction for teams and students just getting their foot in the door of the world of ICPC and competitive programming competitions in general.
  • Division C. Designed for newcomers to the world of ICPC competitive programming.

Types of participation: On-Site and Online

We believe that participation in our Bootcamp should be accessible by all teams wherever they are and that is why we made onsite and online types of participation. 20% Early Bird Discount is offered to universities and participants who register and pay before Jan 31st 2023.

  • On-site:

Price: 1500 € — 1200 €

What is included: training, contests, access to the recordings of the lectures, accommodation for 9 nights in a 4 star hotel Mysk, breakfast and lunch, transfer from hotel to venue every day, leisure, entertainment and welcome pack.

  • Online:

Price: 100 € — 80 €

What is included: training, contests, access to the recordings of the lectures.

Learn more about Hello Muscat 2023→

Good luck with the round!

UPD: Editorial is out

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

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

Best of luck everyone . As a participant I am going to give my best in this contest.

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

Good luck everyone. Hope i can solve problem C

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it +39 Vote: I do not like it

    I didn't solve the problem C

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it -6 Vote: I do not like it

      did you solve b?

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

        Yes! I solved it when there were 5 minutes left before the end of the competition.

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

          B was quite hard for a Div 2 B problem. Man it's really hard to improve in competitive programming, I feel like im stuck. Being stupid also doesn't help.

          • »
            »
            »
            »
            »
            »
            2 weeks ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Only two words: More Practice

            • »
              »
              »
              »
              »
              »
              »
              2 weeks ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              Only one word: repeat

              • »
                »
                »
                »
                »
                »
                »
                »
                2 weeks ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

                Thanks for the words i guess. Planning to reach 1700 by the end of the year is it realistic if I work hard?

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

              Thanks for the words i guess. Planning to reach 1700 by the end of the year is it realistic if I work hard?

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

                Idk but one thing I would say Enjoy the process!

              • »
                »
                »
                »
                »
                »
                »
                »
                2 weeks ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

                This is a good goal. I would also like to go up to 1600 a year. And I understand that this is real if you regularly work and solve problems not only that are easy for you, but also that are higher than your current level, in order to learn how to solve them.

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

Hope to get good rank at contest which I am not able to do so in previous rounds

»
3 weeks ago, # |
Rev. 5   Vote: I like it -53 Vote: I do not like it

;)

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

I am sure everyone will be successful in this competition. You can! Good luck!

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it -21 Vote: I do not like it

    I also wish everyone that no one could hack their solution! I wish everyone +100 or more than 100 to the rating of everyone!

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it -23 Vote: I do not like it

      Mathematically its not possible because if you want to get + rating changes some one has to get the negative.

»
3 weeks ago, # |
Rev. 2   Vote: I like it +2 Vote: I do not like it

i still remember awoo's favourite problem

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

Good luck to everyone!!! (I hope that I can solve at least one problem :>)

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

Wow, I'm back after a year and comments are as cringe as ever. Joining in.

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

Good luck everyone . Hope I can solve at least one problem.

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

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

good luck have fun

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

Hope to become cyan, and good luck to everyone in this contest.

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

hmm, why I has the conbutrition? can anyone explain??

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

This Contest is very beauty-full

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

me after solving a&b :

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

Classic Mathforces

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

oh yes I saved the previous non-blue profile pic somewhere else and I am getting to use it now

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

    I should find a matching green one aswell, given the amount of times I have dropped right after reaching cyan T-T

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

Any proof for B?

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it +54 Vote: I do not like it

    Pretty straightforward after trying to solve for a 1d array instead of matrix

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

      Thanks man! I wrote the solution after so many hit and trials. I need to improve my observation skills for such problems

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

      Thanks man....it was really helpful....I complicated this problem unnecessarily

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

      lol i did a snail

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

    There are $$$n^2-1$$$ possible differences $$$(1\dots n^2-1)$$$. And the chain $$$1, n^2, 2, n^2-1, \dots, \left\lfloor\dfrac{n^2}{2}\right\rfloor, \left\lfloor\dfrac{n^2}{2}\right\rfloor+1$$$ (chain ending correct modulo parity), contains all differences and has $$$n^2$$$ terms, for $$$n^2-1$$$ differences.

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

    I code brute force as the max difference can be (n*n-1). Try to create all differences from (n*n-1) to 1.

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

seriously, what is the point of problems like B, where you have to find some stupid pattern on a grid?

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

    I wasted time thinking that question is asking for only border elements.

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

    Why do you think that is a silly thing to do? It trains observational skills.

    Regardless, its not like patterns in grids of numbers are a meaningless or trivial thing to study. There are a ton of problems that can be represented as patterns in grids of numbers.. Doing regression in data analysis for example.

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    its not stupid instead you can find the logic behind the pattern. though i wasn't able to solve the problem i found its quite intuitive after contest... since there will be in total 2*(n*(n-1)) adjacency relationship and also maximum diff between any two adjacent could be n*n-1 < 2*(n*(n-1)), we can always generate pattern such that from 1 to n*n-1 all diff got generated. now take the maximum diff i.e., n*n-1 we cannot make it a adjacent diff between two big values so adjacent relationship can be between big and small values, like n*n and 1, 1 and n*n-1 like that. If we solve that for 1D array of length n^2 we have total n^2-1 adjacency relation so just making a spiral out of it to make the n^2 length array to a n x n matrix would suffice.

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yes i did it using Spiral Traversal :)

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

Too much penalty >:( and I thought the condition in problem B is $$$a_i + a_j$$$ instead of $$$|a_i - a_j|$$$.

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

    how did you solved B?

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

      There's at most $$$n ^ 2 - 1$$$ distinct value so we started from $$$1, n ^ 2, 2, n ^ 2 - 1, ... $$$ and apply it to a zig zag path on the matrix.

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

so my approach for problem C was since the nth player can at max have n wins . so a win against him would increase my chances of having a lesser rank . i tried defeating maximum players from the end. and then sort the number of wins for each player in decreasing order and decide my rank why wouldn't this logic work ?

here's my submission https://codeforces.com/contest/1783/submission/188487469

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

    See this testcase:

    1
    3 5
    2 3 5
    
  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Even i tried a similar approach. 1. Try defeating players from last. 2. Sort and try to defeat as many as possible. Then print the minimum of the two ranks. But it failed on TC 2.

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

    I was also thinking the same but this will not work because we are concerned more about the total number of wins by "me".

    even if we win against last person but our time left is 0, our total win is only 1 so players before last one (like p=2 or 3) can win and our rank will fall.

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

People asked for binary search, dp, segment tree problems aand... here we ended up

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    I think C was a beautiful problem , though B was little annoying to me

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it +23 Vote: I do not like it
    Спойлер
    • »
      »
      »
      3 weeks ago, # ^ |
      Rev. 3   Vote: I like it 0 Vote: I do not like it

      I didn't mean that, C, D, E are very much algorithmic problems, but many of my friends complained about them being too hard ( I think they are easy)

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

      You need some testers for educational round too lol. There are so many ups (and lots of downs) in the quality of these contests

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

      how to solve c?

      • »
        »
        »
        »
        3 weeks ago, # ^ |
          Vote: I like it +13 Vote: I do not like it
        Спойлер
    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      i tried binary search But not Know how to write function correctly Plzz share some hint

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

    Most of the good contests I participated in had at least one of them

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

Problem B was annoying :(

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

How to solve B?

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

    some pattern based try for n = 4 it will be like

    1->16->2->15

    13->4->14->3

    5->12->6->11

    9->8->10->7

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

      how to solve c?

      • »
        »
        »
        »
        3 weeks ago, # ^ |
        Rev. 3   Vote: I like it +3 Vote: I do not like it

        You can solve C by sorting the array and finding the maximum number of people you can defeat with the given m, let's denote it by wins.

        1) if wins = 0 or wins = n , then your position will be n-wins + 1 (last or first).

        2) If wins >=1 and wins <= n-1, if you could defeat person with a [wins] index (his total wins are equal to wins or wins+1), your position would become one better, so the answer would be n-wins, otherwise n-wins+1. (You could go 1 position higher by having total wins equal to that person.) 188489483

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

      Thanks I overcomplicated it too much

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

      how did you come up with the pattern?

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

As always Educational rounds are worst.

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

    The whole point of them is to learn (standard) algorithms, not to solve interesting tasks. And I think that $$$A$$$, $$$B$$$, $$$F$$$ and $$$G$$$ are great for that ( educational ) matter.

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

      what does one learn from B?

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

        What Wind_Eagle has said before, how to prove theorems in mathematics. Asking for a construction in CP means that one cannot randomly guess the answer, but must be aware of the proof. And I think it is an okay problem, requiring some basic implementation which is, in fact, useful. I understand that many find it annoying though, which doesn't necessarily make it bad.

        • »
          »
          »
          »
          »
          3 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it
          Asking for a construction in CP means that one cannot randomly guess the answer, but must be aware of the proof

          Infact the reverse is the case, it is very easy to guess the pattern for problems like this without knowing the proof.

          I'm pretty sure for this problem, people just randomly guessed patterns that gave $$$n^2 - 1$$$ as difference, and only a few actually proved the patterns or derived it mathematically.

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

is problem c Segtree or vector of priority queues since ai<=1000 or I completely overcomplicated ?

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

    It has to be on Binary Search but this mf B wasted an hour and my mind went blank coz of that so couldn't even think properly about C

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    Key observation is because each player plays each other the other players will have 1, 2, 3, 4... wins... If you can beat the player with exactly 1 more win than you while still maintaining the optimal number of wins than your place is (n-wins+2), else it is n-wins+1

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

GOODBYE EXPERT!! These hit and trial B's are the worst

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

Rounds like these make me wish there was an un-register button on Codeforces just like on Atcoder. Wtf was problem B???

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

How to solve D? Spent most of my remaining time trying to solve it...

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

    Try thinking about $$$dp_{i,s} := \textrm{the number of possible suffixes of the array starting at } i\textrm{ having } a_{i+1} \textrm{ equal to } s$$$.

    The transition will be something like $$$dp_{i,s} = dp_{i+1,a_{i+1}+s} + dp_{i+1, a_{i+1}-s}$$$ depending on whether $$$s = 0$$$.

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

      are we trying to find how many different types of sum are possible at end position after applying all operations. eg. if array is a1,a2,a3,a4, at max answer can 4 with 4 different sum a4+a3+a2,a4+a3-a2,a4-a3+a2,a4-a3-a2 possible at the last position?

    • »
      »
      »
      2 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Bro I did same as yours appraoch but getting TLE on test 18, can you please see and help me how to avoid it. Link to solution : Solution

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

Can we solve C using Binary search?

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

    I too want to know this, I got an intuition but couldn't mold it in any kind of solution.

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

    I did it using binary search on the number of people we rank at least as low as. So to beat $$$k$$$ people, I pick the $$$k$$$ weakest opponents (in terms of $$$a_i$$$), if their sum of $$$a_i$$$ is less than $$$m$$$, we can rank $$$n-k+1$$$, there's also another small detail but this is mostly the idea.

  • »
    »
    3 weeks ago, # ^ |
    Rev. 4   Vote: I like it +10 Vote: I do not like it

    Yes, we can binary search answer. When we check mid, we know that we can't lost the n — mid + 1 opponent. Let t = n — mid + 1. So we do it greedily to beat as many opponent as possible. Now there are 2 case : If the number we can beat >= t, we always win because player t can win at most t games. Else(number we can beat = t — 1) if we can beat player t, we can win too because now t win t — 1 games. 188457382

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

    Yes.You can see my submission.

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

Did we have to check only from prefixes and suffixes in the C problem? Like we try to win against only suffixes or only prefixes or some prefixes and suffixes combined? (for the sorted array)

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

Is D even DP ? 💀

»
3 weeks ago, # |
Rev. 7   Vote: I like it +23 Vote: I do not like it

A: If min==max no solution, else {min, max, (anything)} is a solution.

B:[1, n^2, 2, n^2-1, 3, n^2-2...] arranged along any path of the matrix

C:Sort the array and you will get an almost-best solution. But it needs an extra check to get the best solution. When you've checked first k opponents with least time to prepare, look for whether you've prepared for the opponent with index k+1. If not, check whether you can remove a prepartion and prepare for (k+1)th opponent.

D:Consider for every possible value of sum(ai*sign_i), where sign_i = 1 or -1. There are at most 180000 different values, and run dp for an O(n*A^2) solution.

E:Seemingly easy inequality problem, but naive implementation will get TLE. For certain k, if all multiples of k are not in any range [bi,ai-1], then k is good. We need a segment tree to check all values of [1,n] in O(n*log(n)).

  • »
    »
    3 weeks ago, # ^ |
    Rev. 2   Vote: I like it +5 Vote: I do not like it

    [E] You don't need a segment tree. Just do range sum using prefix arrays and iterate over all multiples of k for every k.

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

      Ohhhhh I missed it

      I just thought about "How to set a range in O(log(n))" and implemented with segment tree

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

    Do I check whether I can prepare for the k+1th opponent in the sorted array or in the orignal array?

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

      Original

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

        Please correct me if I am wrong.

        The logic is: If I can beat any k opponents it means I will rank alongside the k+1th person in the rankings right? So I check if I can add a preparation for the next highest opponent which I have not prepared for and remove prep for the lowest index which I have prepared for so as to beat k+1th opponent right? Such that my number of preparations always remain the same so I beat the opponent removed on total number of wins anyway.

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

          If you don't prepare at all, the wins of each other player is their index (1-indexed).

          In fact, if the number of preparations is fixed at k, you win k matches, and for each other players with index i, their number of wins will be i-1 (you prepared for it) or i (otherwise). Notice that if i < k+1, then i<=k and i-1<=k, which means whether you prepare or not, the number of wins of i-th player cannot be larger than you. It's similar for i>k+1 (their number of wins will be always larger). So only i=k+1 will matter.

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

            Ohh I understand it now. Thank you very much!

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

Worst contest for me!

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

Through this edu round,I know a fact that I'm a totally trash.Maybe I can never be an expert.

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

Very surprised by number of B and and C solves, B confused me while C seemed like a trivial sorting problem

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

Worst B ever. Period.

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    I didn't solve B, but I liked it. It tests one's observation ($$$n^2-1$$$ upper bound) and simplification (solve it for 1d array first) skills.

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

    That is because you didn't find a key idea of it,so your code was very long.If you found that $$$1 \sim n^2-1$$$ must be able to express,you could know that $$$n^2$$$ must be adjacent to $$$1$$$,easily we could expand it into an easy solution.

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

How to approach problems like B? I solved it by randomly guessing stuff.

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

    Have you ever solved tasks from mathematical olympiads?

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

      No. How would that be useful to tackle such problems?

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

        These problems aren't random guessing, it's just math.

        • »
          »
          »
          »
          »
          3 weeks ago, # ^ |
            Vote: I like it +15 Vote: I do not like it

          how exactly do you approach B mathematically?

          • »
            »
            »
            »
            »
            »
            3 weeks ago, # ^ |
              Vote: I like it -20 Vote: I do not like it

            This is the type of question like "how mathematicans prove theorems" or even "how tourist solve CP tasks".

            • »
              »
              »
              »
              »
              »
              »
              3 weeks ago, # ^ |
                Vote: I like it -39 Vote: I do not like it

              just noticed your round is the next cf round, rofl. with this type of shitty opinions of yours, I pity whoever participates in that round.

              • »
                »
                »
                »
                »
                »
                »
                »
                3 weeks ago, # ^ |
                  Vote: I like it -16 Vote: I do not like it

                True, He better not include these kind of problems. B pissed me off and I left contest within 20 minutes to play CSGO

          • »
            »
            »
            »
            »
            »
            3 weeks ago, # ^ |
              Vote: I like it +87 Vote: I do not like it

            The process "find the strictest lower/upper bound for the answer and then show that it's reachable" is common in math competitions (not only that, it also frequently appears in algorithm correctness proofs). This is the first step to the solution: it's quite easy to see that the answer is bounded by $$$n^2-1$$$ (all differences are positive, and the maximum difference cannot be greater than $$$n^2-1$$$).

            Then, to actually find the way to reach this bound, you need to try some common techniques to solve problems. You can take a look at MikeMirzayanov's post on these techniques. From these, we have already used "Bold Hypothesis". The "From Specific to General" (with a twist, since we actually change the problem partially instead of just simplifying it) may help us as well: 2D sounds too complex, what if the problem is in 1D instead? This case sounds way stricter: we have only $$$n-1$$$ adjacent pairs, and all of them should be distinct. Believe it or not, but having stricter constraints actually makes the solution easier, inventing a construction on one-dimensional array is not that hard.

            Spoiler

            All that's left is to convert the 1D solution to 2D, which means that we should go through the matrix visiting all its cells, which is a common math/programming problem.

            Spoiler

            Note that our process of solving the problem used something like "try to apply a concept and then see if it works" multiple times, and this is very common in both math problems and harder programming problems. So getting familiar with these concepts and methods will not only help you solve some constructive and/or ad-hoc problems, but also the more difficult ones, where you have to mix it with some standard data structures and algorithms.

            • »
              »
              »
              »
              »
              »
              »
              3 weeks ago, # ^ |
                Vote: I like it +31 Vote: I do not like it

              Want to add something: some hard tasks require to try a dozen of different approaches before solving the task. This is common not only for constructive and maths, but for interactive problems, graphs or even data structures.

              And solving those "just guess" tasks improve your thinking skills and allow you to recognize some patterns in future tasks.

              So, dear contestants! Instead of just "problem was too bad", answer the question: was it hard or just difficult? Many people claim that the task is "bad" if they weren't able to solve it in time and got negative delta.

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

                I had to tinker around with some randomly put together constructions till I came across the solution.
                Proving it seemed easy once it was clear.
                Definitely not appropriate for problem B, but it's an edu round and technically the order doesn't matter, so whatever, ig.

            • »
              »
              »
              »
              »
              »
              »
              3 weeks ago, # ^ |
              Rev. 2   Vote: I like it +1 Vote: I do not like it

              My opinion on the quality of Problem B has changed after reading this comment

              Thanks

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

          what's math in that?

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

            Well it was not total math problem, but yes there was a quite neet observation, that is the maximum ans is always n^2 — 1, from there you can make the matrix multiple ways.

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

              I got that observation but still it felt like massive hit and trial to me

        • »
          »
          »
          »
          »
          3 weeks ago, # ^ |
            Vote: I like it +8 Vote: I do not like it

          But I think, here intended solution was random guessing!:(

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

    Thats how you solve it, xD

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

After failing to submit E in the last 10 seconds the last time(Jan 6), this time I found the solution of E in the last 5 minutes and got AC just 5 minutes after the contest ended... [Sad]

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

B spoily my mood and I gave up after 20 minutes

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

Hi there! I try to help people by upsolving contest problems and post them after the contest on my channel — https://www.youtube.com/@grindcoding . I have been trying hard to help people by solving daily challenges across platforms and also the contest problems. Please provide me suggestions on what I can improve. Have uploaded problem C of this round already and would upload others as required by anyone of you. Any advice is appreciated :).

P.S. not the channel who promote leaking solutions during live contests. I know it provides better growth with the huge amount of cheaters, but I understand it's detrimental and against the overall spirit :) happy coding :) Soon would be making a good data structures and algorithms course to help beginners (though not a pro myself but want to contribute as I grow).

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

A tough contest to me :(((

problem B needs a lot of observation :((((

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

Any hints to approach problem 'C'?

Really reject stopping solving problems regularly T_T

Spoiler
  • »
    »
    3 weeks ago, # ^ |
    Rev. 2   Vote: I like it +6 Vote: I do not like it

    Hint 1: Without considering your training, each other player has a unique amount of wins

    Hint 2: What 1 other player's ranking can you affect that could also improve your ranking?

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

    Hi! yes! there's one case you need to consider, can you defeat the person who has wins==wins_you_have+1, I have uploaded a editorial video on my channel you can check this here- https://www.youtube.com/@grindcoding

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

    Let's say I want to reach a specific position Xth, what's needed? Once you've figured that,

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

got stuck with b and no time left to think about c .. uff time to go back to green

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

Participate in post contest discussion

www.peer2peer.social

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

Wow, I really enjoyed the problemset! Problem F is just otherworldly *_*

Huge thanks to the developers of the contest! <3

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

Nowadays the problems in the contest are not properly sorted in the order of their difficulty. Sometimes the problem B is made very hard, whereas sometimes it is made as easy as A, and in this case the C problem is made very very Hard.

It would be nice if the difficulty order would be made moderately increasing.

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

    problem C isn't hard. it's just sorting and a simple observation.

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

Welp this was a waste of time.

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

was anyone able to get the solution to E with $$$n√n$$$ time complexity?

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

    O(n*log(n)) is enough. You just need to check for eack 1<=k<=n, if any multiple of k is in range [bi,ai-1] for some i which ai>bi.

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

    it was hard but yes 188516731

»
3 weeks ago, # |
Rev. 2   Vote: I like it +17 Vote: I do not like it

Tips for Python

In Python, you can put negative indices in a list (A[-1] means A[len(A)-1]). This makes it easy to implement dynamic programming with negative indices. When the index can take values from -L to L, prepare a dp array of length at least 2*L+1. In this array, information on positive indices can be placed in the first half of the list, and negative indices in the second half ([0, 1, 2, 3, ..., L, ... , -L, ..., -3,-2,-1]).

Source Code for D:

mod = 998244353

n = int(input())
a = list(map(int, input().split()))
dp = [0] * 2 * 10**5
dp[a[1]] = 1

for i in range(2, n):
    ndp = [0] * 2 * 10**5
    for j in range(-90010, 90010):
        ndp[j + a[i]] += dp[j]
        if j != 0:
            ndp[j - a[i]] += dp[j]
    dp = [j % mod for j in ndp]

print(sum(dp) % mod)
»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

188508171 Please show me a case where my submission for problem C get the wrong answer :((((

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

The hack channel for problem C is ridiculous. If I set t to 1 and n to 500000, it will show generator crashed, which means it is hard to hack it tle!!!!!!!!!!!!!!!

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

Quite an ambiguous definition+example of the side adjacency for problem B. In the 2x2 example almost any nonsense one may come up with yelds same answer. For example if you define side adjacent elements as "elements on the same matrix edge". After the clarification it gets better, but still there's a chance you keep solving the wrong task on impulse.

Any ideas how this "insanely misinterpreted" problem can be solved by the way?

Once again. Same task: find the most beautiful matrix, but the adjacency definition is:

Two different matrix elements $$$a[i_1][j_1]$$$ and $$$a[i_2][j_2]$$$ are adjacent iff ($$$i_1 = i_2 = 1$$$ or $$$i_1 = i_2 = n$$$ or $$$j_1 = j_2 = 1$$$ or $$$j_1 = j_2 = n$$$) ?

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

    1 n 2 (n-1) 3 (n-2) 4 (n-3)

    Look at this like and all will be clear(first row of matrix)

    • »
      »
      »
      3 weeks ago, # ^ |
      Rev. 3   Vote: I like it 0 Vote: I do not like it

      Thanks, but that's the solution to the original problem, but doesn't seem like a solution to the problem I mention.

      I'm interested in filling these so that the size of the set made of absolute difference of any two elements from first row or last row or last column or first column has max size.

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

can anyone tell me how to solve E?I Just know that for every a[i]>b[i],then check k is ok if and only if (a[i]+k-1)/k==(b[i]+k-1)/k (i.e. ceil(a[i]/k)==ceil(b[i]/k)). but this get TLE as expected. how to get a faster solution? i cant understand the solution in the front row

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    $$$\left \lceil{a[i]/k}\right \rceil \neq \left \lceil{b[i]/k}\right \rceil $$$ if and only if there exists a number divisible by $$$k$$$ in range $$$[b_{i}, a_{i}-1]$$$.

    Therefore, we can mark all numbers in this range (for example, by using a segtree) and for each $$$k$$$, check if there is a marked number divisible by $$$k$$$.

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

In problem C, does NlogN pass? I didn't want to take a risk and made an O(n+maxA) solution.

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

can anyone help me understand in problem C if the test is 8 6 2 2 2 2 2 2 2 2 so if I win against the 8 and 6 and 4 so 1 1 win 2 2 win 3 3 win 4 3 win 5 5 win 6 5 win 7 7 win 8 7 win I 3 win so I should rank 3 why is the answer 5 I don't understand I got stuck in this problem for that

  • »
    »
    3 weeks ago, # ^ |
    Rev. 3   Vote: I like it +2 Vote: I do not like it

    just because there are 4 people whose win count strictly larger than you (i.e.5,6,7,8),let the count called k. and the answer is k+1. I guess you misunderstood the computing method of the rank within this question.

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

      Ty I think so the solution is much easier than i think ಥ⁠‿⁠ಥ

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

      Brooooooooo, will re-read question 10 times now while solving.

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

    Because rank is the no. of people with more wins than you + 1. Your win count is $$$3$$$ but $$$8$$$ and $$$7$$$ both have won $$$7$$$ and $$$6$$$ and $$$5$$$ both have won $$$4$$$, hence the no. of people with more wins than you is $$$4$$$. Therefore, your rank is $$$5$$$

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

      Yeah i understand that they group people with the same win so that i should minimize the number of group

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

    It's optimal to beat the any 2 players and the 4th player which results in 3 wins.

    Bracketed players are the ones we beat.

    So 2 2 2 [2] 2 2 [2 2]
    

    And then if we count the number of wins and also consider the players we lose to we get our answer.

    1st player will have 0+1 wins
    2nd player will have 1+1 wins
    3rd player will have 2+1 wins...
    4th player will have 3 wins
    5th player will have 4+1 wins
    6th player will have 5+1 wins...
    7th player will have 6 wins
    8th player will have 7 wins...
    

    We ourselves have 3 wins. Order looks something like this then

    P(i) = 1 2 3 4 Us  5 6 7 8
    Wins:  1 2 3 3 [3] 5 6 6 7
    

    Our rank is 5.

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

BledDest Can anyone explain problem C?

For this test case

4 4

1 2 2 1

Since we have 4 minutes I can defeat Opponent 1,2. But why in the explanation it is mentioned we can win against only opponent 1 and we have no time to prepare

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

    That's the 5th test case.

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

    If $$$m = 4$$$ and we prepare and win against opponents 2 and 3 and lose against 1 and 4. Don't we get 2nd place? As our opponent 4 has $$$3 + 1 = 4$$$ wins against our 2 wins. I must be missing something obvious.

    Edit: ok my confusion was to fail to understand that "min place" actually means best ranking and not worst ranking.

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

      We can pick the following opponents. (Bracketed means picked)

      [1] 2 [2] [1]
      

      Which gives us 3 wins. Opponents will be ranked as follows:

      P(i) = 1 2 3 4 Us
      Wins:  0 2 2 3 [3]
      

      This results in first place.

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

I almost spent the same amount of time on B as I did on C and D combined.
Seemed like I was solving some weird newspaper puzzle.

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

    How is B an 'edu' problem?

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it +15 Vote: I do not like it

      I start to think that "edu" is not about learning, "edu" is about Harbour space, like , there are Pinely rounds, Polynomial Round, CodeTON Round etc.

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it +19 Vote: I do not like it

      It is rarely a difference between EDU and classic rounds. EDU were immature rounds initially, with no score distributions and possibilities for hacking, but later classic rounds overcome simplification and become similar to EDU, without hacking almost, but still with different costs of problems (except newer Div.>2, which are simplified further and have no difference with EDU).

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

      It's not a random guessing problem. Notice that the difference is between 1 and $$$n^2-1$$$, so naturally we first try to get them all. For $$$n^2-1$$$, $$$n^2$$$ and 1 need to be adjacent, then for $$$n^2-2$$$, either $$$n^2$$$ and $$$2$$$ or $$$n^2-1$$$ and $$$1$$$ need to be adjacent, .... It's quite easy to achieve that. If you know gray code, Z-order, or something like those, easier.

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

Solution of D(with explaination please)?

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

This was a perfectly good round, without any major errors. Why all the downvotes?

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

Though the binary search solution greatly simplified the task, was it actually required in C?
I mean, apart from the edge case of losing to the winner and changing the required score, it was all greedy and sequential, right?

»
3 weeks ago, # |
Rev. 4   Vote: I like it +8 Vote: I do not like it

There is interesting solution of E with Eratosphens sieve: It's a fact that upper bound of a[i] / k must be <= upper bound of b[i] / k for all i. So we need to check only pairs where a[i] > b[i]. You can increase every a[i] position by any big number (1e7 + 1 in my case) and decrease every b[i] position by 1. Then we get prefix sum of this array and iterate like in sieve. If any sum on prefix with length which divides k doesn't divide 1e7, it means that we found some b[i] with b[i] / k > a[i] / k. That's it: 188522674

UPD: nevermind lol, it's basic solution

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

For problem D, I submitted these 2 solutions after the contest:

Submission 1 gives a Wrong Answer verdict. 188541769

But when I submitted a new solution taking the answer modulo, I got a TLE verdict. 188542103

I don't think I changed much of my code. Does anyone know what the heck is going on?

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

    Modular operations are expensive. And even if they weren't, the first solution already took nearly 2s and adding more operations there inside the loop would yield TLE.

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

    If a,b are in [0,mod-1], you can use

    ans=a+b;
    if(ans>=mod) ans-=mod;
    

    instead of

    ans=(a+b)%mod;
    
  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Also you should check if(a[1]!=0) instead of if(a[2]!=0). Because of this mistake your answer will be hacked by some tests with a[2]==0, even if don't get TLE.

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

problems are good , but the implementation part is a bit complicated.

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

For D problem,can we use dfs and work it out?

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

    Use DFS with memorization,in fact it is nearly the same with DP solution.

    My good friend wrote it,though his code was not very easy to read.

    188473734

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

        As I said,you didn't use DFS with memorization.In other words,you could find that there will be many repeated search with the same $$$(i,ai)$$$.So you could record the answer of dfs(i,ai).It will cut lots of unnecessary search.

        Your TLE code is a $$$O(2^n)$$$ solution.If you use memorization,it will be $$$O(n^3)$$$ because you will find $$$|ai|$$$ will not exceed $$$90000$$$.

      • »
        »
        »
        »
        2 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        hey, why are you returning 2 here?

        if(i==n-1) { if(ai==0)return 1; else return 2; }

        • »
          »
          »
          »
          »
          2 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Because if i==n-2,there are two operations you can make:a[i+1]+a[i] or a[i+1]-a[i].But if,a[i]=0,then a[i+1]+0=a[i+1]-0,these two ways are the same way,we can just calculate 1

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

      There's a line of code that needs to be modularized. I think my time complexity may be the same to your friend's,why mine cannot pass through?Can you help me slightly modify it and make it work?

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

        I fixed your solution

        188553247

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

          I racked my brains last night, but I couldn't figure out how to cut the branches. It turns out that you can use space to exchange time and it increases my knowledge. Thank you very much!

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

          So it is Mnemonic search? It turns out that I can really use some simple knowledge that I am good at to pass this topic! Because the code of my friends around me is complicated, I hope my code can be changed and pass. It really turned out to be okay.

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

Apparently I crashed codeforces because of a hack submission I made. I don't even remember the testcase I did, but it was supposed to bug a code that was using random generator for the answer. Anyway, thought I would leave that here so someone would look through it and see why it's still waiting for about 10 hours now!!

Here is the link to the hack: https://codeforces.com/contest/1783/hacks?verdictName=TESTING&chosenProblemIndex=A

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

    I subitted my hack for someone's D problem last night,and it showed "generator crashed",which made me amazed,too.

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

      No that's normal. That happens when the code you made to generate the testcase had some bugs in it.

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

        Aha?It shows that: The hack uses generator Generator is not determinate [the verification run produces different output, cmd =cvp], [389171 bytes, '1

        100000 5731847

        175 801 492 274 740 3 22 624 98...850 521 474 390 847 127 534 896 874 535 704 834', sha1=0cc6f6ae5c8479c995b9dec28fcd7dc48de6b3fe] vs. [388952 bytes, '1

        100000 5731847

        181 530 685 865 602 856 479 769... 803 621 675 483 837 275 74 663 223 426 353 310', sha1=911ae7fb5a320770e460a2a3d1a2c49baa34c4c6]. My hack submission includes randmized integers,so I think it's naturally that the generator is not determinate. I've tried to submit code that generates random numbers before, but I've always succeeded before, but I don't know why I didn't succeed this time. I tried to write test to a file to make the value certain, but it said the file was too big and had too much text. So I think this is a bug in the cf mechanism.

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

          Could you send me your generator?

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

            You can search and see that the verdict of C problem in hacks is generator crashed

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

              You uses the time as the seed,may be $$$m \le \sum{a_i}$$$ won't be satisfied.You could use a number as seed instead of time.

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

              You shouldn't use system time to initialize the RNG, which causes value generated become indeterminate. Use fixed seed instead.

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

                Aha?So does the fixed seed have some constraints?

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

                  Any number is ok.Such as I always uses 10086001,an interesting prime number :p

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

            Could you check my hack too because it's preventing the update of the ratings

»
3 weeks ago, # |
Rev. 5   Vote: I like it +9 Vote: I do not like it

Will we see rating update and tutorial before next contest begins?

Why does "Educational round" mean slow rating update and slow tutorial?

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

    No this is because there is a hack submission that is still waiting till now. It's mine, and I don't know what's taking it so long. I hope they fix it

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

      lol

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

        To think I would crash codeforces xD

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

          I am wondering what you submitted that hacked the whole system XD

          • »
            »
            »
            »
            »
            »
            2 weeks ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            It's really nothing xD Just a long testcase to hack a solution that uses random generator. That's all xD

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

How to solve G ? Seems that the tutorial won't be soon :(

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

Wait for D's solution.DP is my weakness...

And there is still no tutorial yet?

  • »
    »
    3 weeks ago, # ^ |
    Rev. 2   Vote: I like it +11 Vote: I do not like it

    Small hint to you:

    • In any time,$$$|a_i| \le s$$$,where $$$s$$$ is the sum of the given array.

    • When you are going to operate $$$i$$$,you only care the value of $$$a_i$$$ now.Try to empress the dp state as $$$f(i,now(a_i))$$$.

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

I dont understand why this contest was downvoted, I felt like problems were good, specially C.

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

I'm wondering how 300*2*300*300 solutions were accepted for D. Thats like (10^8)/2. Aren't 10^8 solutions supposed to TLE?

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it +7 Vote: I do not like it

    It is very easy to pass in codeforces.In fact,many $$$10^9$$$ level codes could pass in 1 or 2 seconds in codeforces with their small constant.

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it +7 Vote: I do not like it

      Interesting, thanks. Wasn't really aware of it. It was a pretty straightforward dp question in that case. Will remember it for next time.

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

        It's like the worst case scenario strategy, because none of the authors consider 10^9 solutions

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it +7 Vote: I do not like it

    176169324

    Such as this code,it was a $$$O(n^3)$$$ solution and $$$n \le 1000$$$,but it was very fast,with a $$$\frac{1}{6}$$$ constant.

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

B is worst problem fck

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

This Bootcamp, is it meant only for students? Or can I join at the ripe age of 33?

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

Rating??

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

When is system testing going to happen?

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

    Oh! It didn't happen all this time ? Hacking phase is finished

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

      I was checking every while and I didn't see it happen

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

        Oh! I thought my solutions passed the systests already... Sad. There might be a chance for Failed systests :-(

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

Trush round!A is not perfect.Problem B is the worst problem I have ever seen.I wasted an hour on it.But C is very interesting.Hope more questions like C will appear in cf.

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

Why it's taking time to get the rating updated for this contest?

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

    Because there is a hack submission still waiting lol

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

Where the rating updates at?

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

When will the tutorial will be published ?

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

has this contest been declared unrated or what? why rating is not updated yet?

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    It takes so long in Educational Rounds

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it +6 Vote: I do not like it

      Yes, and 4 hacks are not tested yet. All that hacks are on this solution, it has random and easily gets TL. I dont know why testing solutions on hacks dont break after TL...

      • »
        »
        »
        »
        2 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        But in fact this code is expectly $$$O(Tn^2)$$$ in the worst cases,which is easy to pass.I didn't understand why it can be hacked(I submitted a same one and was hacked),could someone tell me?

        • »
          »
          »
          »
          »
          2 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          I don't know about TLE, but does random give 100% correct answers?

          • »
            »
            »
            »
            »
            »
            2 weeks ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            If it was checked that the array was not correct,it will repeat the random algorithm till it find a correct answer.

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

          If you have array [1, 1, 1, 1, ... , 2] you have 2 correct answers — [1, 2, 1, 1, ..., 1] or [2, 1, 1, 1, 1, ..., 1]. In this case you have n possible permutations of array, so in each random shuffle you have only 2 correct answers from n, where maximal n = 50.

          if you do K random shuffles, probability of your win would be correct positions / all positions. All positions = n ^ k, correct positions = all positions — bad positions = n^k — (n-2) ^ k. So if you do K random shuffles probability of finding correct answer is

          P = (n^k — (n-2)^k) / n^k.

          For n = 50:

          • if k = 5, P = 0.1846273024

          • if k = 10, P = 0.33516736

          • if k = 100, P = 0.98312968

          So on this testcase it does 100 shuffles for finding answer. So your code does t * n * K = 2000 * 50 * 100 = 1e8 operations, and you choosing random number 1e8 times for shuffling array, and this can take long time and maybe TL.

          If you would find testcase where is only one correct permutation:

          P = ((n^k) — (n-1)^ k) / (n^k)

          • if k = 5, P = 0.096079

          • if k = 10, P = 0.182927

          • if k = 50, P = 0.635830

          • if k = 100, P = 0.867380

          • if k = 200, P = 0.982412

          In this case your code does t * n * K = 2000 * 50 * 200 = 2e8 operations

          • »
            »
            »
            »
            »
            »
            2 weeks ago, # ^ |
            Rev. 2   Vote: I like it +3 Vote: I do not like it

            Yeah I thought just like you,but I tried to use $$$2000,50,1 1 1\cdots 2$$$ to hack it,but it ran very fast,just used 93ms!

            link

            And I just found the all the data hacked my submissions satisfied that $$$n$$$ is small(In fact,$$$n=4$$$). I'm a bit confused about it.

          • »
            »
            »
            »
            »
            »
            2 weeks ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            I just wrote a random algorithm as it.

            188610805

            I guess that randomize in the hacked code is the murderer of it.

            • »
              »
              »
              »
              »
              »
              »
              2 weeks ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              Yes, randomize function is bad and slow.

              When you tried to hack his solution it's not guaranteed that his random would use 100 operations — maybe if he would lucky he can find correct answer in 5 or 10 attempts.

              About test that hacked your code, i dont really understand why it failed, because for n = 4 and k = 5, P = 0.96, so you need on the average 5 attempts for shuffle, so I dont know why it got TL...

              I will try your solution in locale on testcase which hacked your solution, if I would find something interesting I will write you in messages.

        • »
          »
          »
          »
          »
          2 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          It was me who hacked it. Sorry xD

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

            I didn't care about it(And it wasn't my code in contest),I just wanted to know why it got TLE(And now I get it).And my submission above with shuffle seems to be correct.

            • »
              »
              »
              »
              »
              »
              »
              2 weeks ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              Yeah some types of shuffle will work. I saw someone use random_shuffle and when I looked at it in the documentry it looked like a very good way of shuffling, and a fast way too. It just two successive elements, which is really all what you might need for the answer

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

The contest is supposed to be rated right?

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

IMO Editorial should be provided shortly after the hacking phase finished.It's too long.

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

Can anyone explain how to solve problem F?

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

    We will post the official editorial in one or two hours. Here's an explanation of F copied from it.

    Спойлер
    • »
      »
      »
      2 weeks ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      So when will system testing phase start?

      • »
        »
        »
        »
        2 weeks ago, # ^ |
        Rev. 2   Vote: I like it +6 Vote: I do not like it

        I don't know. I don't understand what happened to those several hacks which can't be tested, and I am awaiting a response from Codeforces admins.

        Hopefully this will be fixed soon.

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

ratings not been updated MikeMirzayanov

»
2 weeks ago, # |
  Vote: I like it +13 Vote: I do not like it

Why do the ratings not still updated.Is any cheater caught or something else.Please update the ratings soon. Thankyou!!!

»
2 weeks ago, # |
Rev. 2   Vote: I like it +13 Vote: I do not like it

MikeMirzayanov Why am i not rated? Please update the ratings soon. Thankyou!!!

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

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

»
2 weeks ago, # |
  Vote: I like it +5 Vote: I do not like it

Thanks for the Editorial :) Can anyone say why ratings are still not updated?

»
2 weeks ago, # |
  Vote: I like it +5 Vote: I do not like it

When will the system testing is going to start?

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

why rating is still not updated?

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

Ratings have not been released yet!!!

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

Still no change in ratings :(

»
2 weeks ago, # |
  Vote: I like it +52 Vote: I do not like it

Sorry, this is my fault. I completely forgot about judging this round, I just somehow got distracted and flew out of my head. Is it old age? Soon the round will be re-judged taking into account hacks and then take care of the rating!

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

    The ratings are updated preliminarily. Tomorrow I will remove cheaters and update the ratings again!

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

      Thanks for first time I've been orange!

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

      there is no change in my rating and i see a lot of people got their rating updated. please look into this.

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

      MikeMirzayanov my rating is not updated till now and i see a lot of people getting their rating updated. please look into this.

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

        It's strange those who solved 2 problems with 50 penalty are ranked #2835 in "common standing" but ranked #2834 in "rating changes". Maybe this difference is caused by someone was omitted in rating calculation…

        • »
          »
          »
          »
          »
          2 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          No only some are eliminated before 3000 rank...I mean to say...their rank of contest is pretty good before hack period and copy cat searching dudes..

    • »
      »
      »
      2 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      30 minutes before the next contest. Hope for fast cheater removal

    • »
      »
      »
      2 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Now my rating is under 2100, if in the next div2 contest my rating is updated to 2100+, will I be rated in the next contest?

      • »
        »
        »
        »
        2 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Did you participate? Was it rated for you? Just curious

        • »
          »
          »
          »
          »
          2 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          I participated it. The rating has not been calculated yet.

»
2 weeks ago, # |
  Vote: I like it +2 Vote: I do not like it

Why rating update before next contest is important?

Some people are on boundaries of getting new color to profile...they becomes aware before their upcoming contests and prepare as per that situation....

Some might think to get good ranks in div3

Some might think that educational rounds are easy ...let's try for that and can skip some contest

Some might have got good rank and might be eager for announcements....

One of my friend won't eat food if contest not goes good....coding is turning someone emotion...❤️..

Wow that's fantastic to listen it and get ready for coding...!

We salute to efforts of all coding platforms...!! for making coding as emotion

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Haha, your words are like long, complicated, but sincere prayers.

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

help me. I am not able to figure out test case in which my code will fail. Your text to link here...

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

First time I “FSTed” with a later accepted time

»
2 weeks ago, # |
  Vote: I like it +5 Vote: I do not like it

is this round unrated?

»
2 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

Can anyone say why the given ratings are rolled out?

»
2 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

Why the Rating of this contest changes and suddenly changes back these days?

»
2 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

Why this contest is unrated?

or it's not unrated?

thanks!

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I think that it's rated because my rating changes this morning.