Educational Codeforces Round 141 [Rated for Div. 2]
By awoo, history, 23 months 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

Comments Comments (253)
| Write comment?
»
23 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Good luck everyone. Hope i can solve problem C

→ Reply
  • »
    »
    22 months ago, # ^ |
      Vote: I like it +39 Vote: I do not like it

    I didn't solve the problem C

    → Reply
    • »
      »
      »
      22 months ago, # ^ |
        Vote: I like it -6 Vote: I do not like it

      did you solve b?

      → Reply
      • »
        »
        »
        »
        22 months 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.

        → Reply
        • »
          »
          »
          »
          »
          22 months 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.

          → Reply
»
23 months 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

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

i still remember awoo's favourite problem

→ Reply
»
23 months 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 :>)

→ Reply
»
22 months 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.

→ Reply
»
22 months ago, # |
  Vote: I like it +26 Vote: I do not like it

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

→ Reply
»
22 months ago, # |
  Vote: I like it +65 Vote: I do not like it

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

good luck have fun

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

Classic Mathforces

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

    not mathforces, just constructiveforces

    → Reply
»
22 months 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

→ Reply
  • »
    »
    22 months 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

    → Reply
»
22 months ago, # |
  Vote: I like it +7 Vote: I do not like it

Any proof for B?

→ Reply
  • »
    »
    22 months 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

    → Reply
    • »
      »
      »
      22 months 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

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

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

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

      lol i did a snail

      → Reply
  • »
    »
    22 months 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.

    → Reply
  • »
    »
    22 months 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.

    → Reply
»
22 months 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?

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

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

    → Reply
  • »
    »
    22 months 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.

    → Reply
»
22 months 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|$$$.

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

    how did you solved B?

    → Reply
    • »
      »
      »
      22 months 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.

      → Reply
»
22 months 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.me/contest/1783/submission/188487469

→ Reply
»
22 months 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

→ Reply
  • »
    »
    22 months 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

    → Reply
  • »
    »
    22 months ago, # ^ |
      Vote: I like it +23 Vote: I do not like it
    Спойлер
    → Reply
    • »
      »
      »
      22 months 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)

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

      how to solve c?

      → Reply
      • »
        »
        »
        »
        22 months ago, # ^ |
          Vote: I like it +13 Vote: I do not like it
        Спойлер
        → Reply
  • »
    »
    22 months 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

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

Problem B was annoying :(

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

How to solve B?

→ Reply
  • »
    »
    22 months 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

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

      how to solve c?

      → Reply
      • »
        »
        »
        »
        22 months 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

        → Reply
»
22 months ago, # |
  Vote: I like it +42 Vote: I do not like it

As always Educational rounds are worst.

→ Reply
  • »
    »
    22 months 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.

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

      what does one learn from B?

      → Reply
      • »
        »
        »
        »
        22 months 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.

        → Reply
»
22 months 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 ?

→ Reply
  • »
    »
    22 months 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

    → Reply
  • »
    »
    22 months 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

    → Reply
»
22 months ago, # |
  Vote: I like it +21 Vote: I do not like it

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

→ Reply
»
22 months 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???

→ Reply
»
22 months 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...

→ Reply
  • »
    »
    22 months 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$$$.

    → Reply
    • »
      »
      »
      22 months 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?

      → Reply
    • »
      »
      »
      22 months 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

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

        I would suggest doing it iterative instead of recursive. Moreover, you have an extra dimension that you can skip (see the explanation of Saul)

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

Can we solve C using Binary search?

→ Reply
  • »
    »
    22 months 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.

    → Reply
  • »
    »
    22 months 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

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

    Yes.You can see my submission.

    → Reply
»
22 months 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)

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

Is D even DP ? 💀

→ Reply
»
22 months 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)).

→ Reply
  • »
    »
    22 months 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.

    → Reply
    • »
      »
      »
      22 months 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

      → Reply
  • »
    »
    22 months 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?

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

      Original

      → Reply
      • »
        »
        »
        »
        22 months 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.

        → Reply
        • »
          »
          »
          »
          »
          22 months 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.

          → Reply
»
22 months 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.

→ Reply
»
22 months 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

→ Reply
»
22 months ago, # |
  Vote: I like it -6 Vote: I do not like it

Worst B ever. Period.

→ Reply
  • »
    »
    22 months 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.

    → Reply
  • »
    »
    22 months 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.

    → Reply
»
22 months 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.

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

    Have you ever solved tasks from mathematical olympiads?

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

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

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

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

        → Reply
        • »
          »
          »
          »
          »
          22 months ago, # ^ |
            Vote: I like it +15 Vote: I do not like it

          how exactly do you approach B mathematically?

          → Reply
          • »
            »
            »
            »
            »
            »
            22 months 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".

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              22 months 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.

              → Reply
              • »
                »
                »
                »
                »
                »
                »
                »
                22 months 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

                → Reply
          • »
            »
            »
            »
            »
            »
            22 months 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.

            Спойлер

            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.

            Спойлер

            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.

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              22 months 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.

              → Reply
              • »
                »
                »
                »
                »
                »
                »
                »
                22 months 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.

                → Reply
            • »
              »
              »
              »
              »
              »
              »
              22 months 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

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

          what's math in that?

          → Reply
          • »
            »
            »
            »
            »
            »
            22 months 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.

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              22 months 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

              → Reply
        • »
          »
          »
          »
          »
          22 months ago, # ^ |
            Vote: I like it +8 Vote: I do not like it

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

          → Reply
»
22 months 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]

→ Reply
»
22 months ago, # |
  Vote: I like it -22 Vote: I do not like it

B spoily my mood and I gave up after 20 minutes

→ Reply
»
22 months 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).

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

A tough contest to me :(((

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

→ Reply
»
22 months 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
→ Reply
  • »
    »
    22 months 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?

    → Reply
  • »
    »
    22 months 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

    → Reply
  • »
    »
    22 months 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
    → Reply
»
22 months 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

→ Reply
»
22 months ago, # |
  Vote: I like it -19 Vote: I do not like it

Participate in post contest discussion

www.peer2peer.social

→ Reply
»
22 months 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

→ Reply
»
22 months 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.

→ Reply
  • »
    »
    22 months 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.

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

Welp this was a waste of time.

→ Reply
»
22 months 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?

→ Reply
  • »
    »
    22 months 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.

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

    it was hard but yes 188516731

    → Reply
»
22 months 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)
→ Reply
»
22 months 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 :((((

→ Reply
»
22 months 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！！！！！！！！！！！！！！！

→ Reply
»
22 months 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$$$) ?

→ Reply
  • »
    »
    22 months 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)

    → Reply
    • »
      »
      »
      22 months 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.

      * * * * * * * 
*           *
*           *
*           *
*           *
*           *
* * * * * * *
      → Reply
»
22 months 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

→ Reply
  • »
    »
    22 months 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$$$.

    → Reply
»
22 months 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.

→ Reply
»
22 months 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

→ Reply
  • »
    »
    22 months 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.

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

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

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

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

      → Reply
  • »
    »
    22 months 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$$$

    → Reply
    • »
      »
      »
      22 months 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

      → Reply
  • »
    »
    22 months 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.

    → Reply
»
22 months 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

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

    That's the 5th test case.

    → Reply
  • »
    »
    22 months 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.

    → Reply
    • »
      »
      »
      22 months 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.

      → Reply
»
22 months 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.

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

    How is B an 'edu' problem?

    → Reply
    • »
      »
      »
      22 months 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.

      → Reply
    • »
      »
      »
      22 months 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).

      → Reply
    • »
      »
      »
      22 months 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.

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

Solution of D(with explaination please)?

→ Reply
»
22 months 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?

→ Reply
»
22 months 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?

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

    That's how I solved it. For loop

    → Reply
»
22 months 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

→ Reply
»
22 months 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?

→ Reply
  • »
    »
    22 months 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.

    → Reply
  • »
    »
    22 months 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;
    → Reply
  • »
    »
    22 months 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.

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

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

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

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

→ Reply
  • »
    »
    22 months 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

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

      188471652

      → Reply
      • »
        »
        »
        »
        22 months 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$$$.

        → Reply
      • »
        »
        »
        »
        22 months 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; }

        → Reply
        • »
          »
          »
          »
          »
          22 months 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

          → Reply
    • »
      »
      »
      22 months 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?

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

        I fixed your solution

        188553247

        → Reply
        • »
          »
          »
          »
          »
          22 months 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!

          → Reply
        • »
          »
          »
          »
          »
          22 months 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.

          → Reply
»
22 months 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.me/contest/1783/hacks?verdictName=TESTING&chosenProblemIndex=A

→ Reply
  • »
    »
    22 months 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.

    → Reply
    • »
      »
      »
      22 months 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.

      → Reply
      • »
        »
        »
        »
        22 months 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.

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

          Could you send me your generator?

          → Reply
          • »
            »
            »
            »
            »
            »
            22 months 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

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

            https://codeforces.me/contest/1783/hacks/879737/test

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              22 months 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.

              → Reply
            • »
              »
              »
              »
              »
              »
              »
              22 months 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.

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

                Aha?So does the fixed seed have some constraints?

                → Reply
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  22 months 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

                  → Reply
          • »
            »
            »
            »
            »
            »
            22 months 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

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

              Sorry,this question is beyond my ability,may be you need to ask Mike for it XD

              → Reply
»
22 months 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?

→ Reply
  • »
    »
    22 months 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

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

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

→ Reply
»
22 months 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?

→ Reply
  • »
    »
    22 months 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))$$$.

    → Reply
»
22 months 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.

→ Reply
»
22 months 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?

→ Reply
  • »
    »
    22 months 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.

    → Reply
    • »
      »
      »
      22 months 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.

      → Reply
      • »
        »
        »
        »
        22 months 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

        → Reply
  • »
    »
    22 months 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.

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

B is worst problem fck

→ Reply
»
22 months ago, # |
  Vote: I like it +5 Vote: I do not like it

Rating??

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

When is system testing going to happen?

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

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

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

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

      → Reply
      • »
        »
        »
        »
        22 months 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 :-(

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

          Yeah I'm growing impatient

          → Reply
»
22 months 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.

→ Reply
»
22 months 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?

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

    Because there is a hack submission still waiting lol

    → Reply
»
22 months ago, # |
  Vote: I like it +14 Vote: I do not like it

Where the rating updates at?

→ Reply
»
22 months ago, # |
  Vote: I like it +7 Vote: I do not like it

When will the tutorial will be published ?

→ Reply
»
22 months 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?

→ Reply
  • »
    »
    22 months ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    It takes so long in Educational Rounds

    → Reply
    • »
      »
      »
      22 months 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...

      → Reply
      • »
        »
        »
        »
        22 months 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?

        → Reply
        • »
          »
          »
          »
          »
          22 months 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?

          → Reply
          • »
            »
            »
            »
            »
            »
            22 months 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.

            → Reply
        • »
          »
          »
          »
          »
          22 months 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

          → Reply
          • »
            »
            »
            »
            »
            »
            22 months 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.

            → Reply
          • »
            »
            »
            »
            »
            »
            22 months 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.

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              22 months 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.

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

          It was me who hacked it. Sorry xD

          → Reply
          • »
            »
            »
            »
            »
            »
            22 months 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.

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

The contest is supposed to be rated right?

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

Can anyone explain how to solve problem F?

→ Reply
  • »
    »
    22 months 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.

    Спойлер
    → Reply
    • »
      »
      »
      22 months ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      So when will system testing phase start?

      → Reply
      • »
        »
        »
        »
        22 months 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.

        → Reply
»
22 months 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!!!

→ Reply
»
22 months 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!!!

→ Reply
»
22 months 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).

→ Reply
»
22 months 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?

→ Reply
»
22 months ago, # |
  Vote: I like it +5 Vote: I do not like it

When will the system testing is going to start?

→ Reply
»
22 months 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!

→ Reply
  • »
    »
    22 months 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!

    → Reply
    • »
      »
      »
      22 months ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      Thanks for first time I've been orange!

      → Reply
    • »
      »
      »
      22 months 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.

      → Reply
    • »
      »
      »
      22 months 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.

      → Reply
      • »
        »
        »
        »
        22 months 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…

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

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

      → Reply
    • »
      »
      »
      22 months 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?

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

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

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

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

          → Reply
»
22 months 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

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

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

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

First time I “FSTed” with a later accepted time

→ Reply
»
22 months ago, # |
  Vote: I like it +5 Vote: I do not like it

is this round unrated?

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

Can anyone say why the given ratings are rolled out?

→ Reply
»
22 months 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?

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

Why this contest is unrated?

or it's not unrated?

thanks!

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

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

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

      My rating change at this morning, but now, it is rollback, anyone please explain for me?

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

        mike has said: "The ratings are updated preliminarily. Tomorrow I will remove cheaters and update the ratings again!"

        → Reply
»
22 months ago, # |
  Vote: I like it +7 Vote: I do not like it

Why my rating is not updated?

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

if someone is struggling with understanding problem-B, the key observation is there should be a number which can be completely absorbed into rest of the numbers. i.e. there is an a[i] whose set bits are [x1, x2, x3] and aj has set bits [x1, x3] and a[k] (k!=j && k!=i) has set bits [x2, x4, x5] then seq-a would be all elements in array and seq-b would be all elements in array except a[i] since those set bits already exist via rest of the elements

→ Reply