SashaT9's blog

By SashaT9, 6 months ago, In English

Hello everyone,

FBI and SashaT9 are very exited to invite you to Codeforces Round 943 (Div. 3)! It starts on May/02/2024 17:45 (Moscow time).

The format of the event will be like any Div. 3 rounds:

  • 6-8 tasks;
  • ICPC rules with a penalty of 10 minutes for an incorrect submission;
  • 12-hour phase of open hacks after the end of the round (hacks do not give additional points);
  • after the end of the open hacking phase, all solutions will be tested on the updated set of tests.

Only trusted participants of the third division will be included in the official standings table. This is a forced measure for combating unsporting behavior. To qualify as a trusted participant of the third division, you must:

  • take part in at least five rated rounds (and solve at least one problem in each of them),
  • do not have a point of 1900 or higher in the rating.

Regardless of whether you are a trusted participant of the third division or not, if your rating is less than 1600 (or you are a newcomer/unrated), then the round will be rated for you.

We would like to thank:

Good luck and have fun!

UPD: Editorial.

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

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

I hope everyone have a great time with this Div.3!!!

And I wish my positive delta. I'm 1599 now...

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

    Interesting. 0 rating change last round, and since rating update delayed,

    I think this div3 is gonna be a clash of experts and ex-experts.

    Update : I don't know why heavy downvote. I noticed codeforces converted all experts, even those who registered as specialist/pupil to unofficial participation

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

      But they updated the ratings?

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

        delayed != didn't happen. But people who became expert last contest, had a chance to register for div3 for a good amount of time before ratings were updated

        Update : Thanks to admins. I noticed codeforces converted all experts, even those who registered as specialist/pupil to unofficial participation

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

          wouldn't they be considered out of the competition still?

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

            That's my point. Since, rating delayed so they had been specialist and could click register, so they registered as specialist or pupil and now are experts and hence a clash of experts and ex-experts xD

            Update : I don't know why heavy downvote. I noticed codeforces converted all experts, even those who registered as specialist/pupil to unofficial participation

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

    All luck for you.

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

As a tester, the problems are cool!

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

Good luck to everyone! Enjoy thi Div3 :) Hope to have a good time in this round.

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

I wish you all good rankings!

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

I hope I can solve ABCDE after having exam in the morning. Good luck to everyone!

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

    Good luck in your exam and in the round!

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

    Good luck with the exam! (Actually Ill also have one in the morning so Im supposed to be studying)

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

      I overslept.

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

        so you skipped the exam or what?

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

          Basically yeah.... I think I'll be able to rewrite it.

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

            lol. i accidently wrote that my exam is today as i thought contest is on 3rd but its tomorrow morning. so no contest for me :sob

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

    It is a sarcastic comment!!!

    As a tester, I can already discuss the problems. So you can start your stream rn and don't waste any time.

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

As a tester I don’t know what to say.

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

Yeey another round!

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

Wish you Rating+=♾️

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

I'm out of competition

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

    I forgot the name of this meme what’s the name??

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

Time to reclaim my title as specialist.

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

    Summon Mahoraga and get him to adapt to all the problems.

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

      Oh I wish. But first he's gonna have to adapt to my massive skill issue , and that will kill him like a 200% hollow purple.

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

        Nah You'd win

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

          Always bet on ABC.

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

            you'll need more than only ABC in div 3 to reach specialist.

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

              Oh yeah I forgot its Div 3 , either way it doesnt matter , I wasnt able to participate.

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

Hope to the best div3 ever

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

I hope to be a good div3. <3 But,I wonder how can i solve at least 3 problems? Consider that I practise continuously about div3.

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

    The problems from Div.3 rounds and Educational rounds are classical (= common) and useful. It means that you can always easily utilize the skills and techniques you learned from these rounds, and there are numerous problems are just derived by such classical problems. In contrast, there are creative and mathematics-required problems in those non-educational rounds and Div.1 rounds from time to time, so I believe that it is hard to earn higher rating since 2100.

    So what you need to do is just to try your best to learn more techiniques (including how to analyse the problem and how to bug-free code). The amount of those traditional techiniques is limited, you can eventually complete that in 30 days if you try to solve the first 4-5 problems in one Div.3 Round everyday.

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

      Thanks for your usefull feedback Im so grateful for ur comment <3 <3 . I actually do that I'm trying everyday to solve atleast 2-3 problems div3 but I think that the progress is very slow and I see my friends are climbing so fast and that makes me disappointed. I have a question : "Is there any yt channel that give tips how to be faster and how to be better at greedy problems . I consider your tip to solve 4 problems every day <33

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

        if you want to be your friend I'm grateful for that :DD(In general, for ur great character <3)

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

        To be honest, I learned how to solve greedy problems by reading some textbooks written in Chinese. Maybe I can give you some keywords to help you to search for those materials.

        1. Observe which is constant: after doing some operation, some numbers/relationships remain unchanged. For example, to minimize the amount of pair (i, j) that satisfies certain condition (e.g. i < j and a_i > a_j). You can switch the adjacent elements, and only the relationship between the two elements will change. It means that you can do the swap operation to optimize each pair of adjacent elements to reach the goal. This thinking method may also be called as "Swapping adjacent"?

        2. Do it first, and regret in the future: You can do the operation first, and record the operations you have done in some data structures (e.g. a heap/priority_queue), when you meet a better choice to do a operation, you just delete the worst operation recorded by the data structures (e.g. priority_queue.top()) and replace the old operation with the new and better one.

        3. Try to predict whether can make a greed operation: Just like a lot of binary-search-liked methods (e.g. to find the k-th element in a data structure) which are common-used in data structures like SegmentTree or BBST. You can also learn the skill in 01-Trie (to greed from the most significant bit, check that whether can take a 0 or an 1 in the next, until the lowest bit)

        The aboving are the common idea in greedy solutions. Besides you can also just improve your mathematical skills and instinct.

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

          I think that skills come with just practice and consistency (I will focus on your tips that are really new for me)

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

Looks like its time for another Speedforces round.

»
6 months ago, # |
Rev. 2   Vote: I like it +23 Vote: I do not like it
Meme
»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

hoping to return back the blue handle

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

Does anyone have guesses what kind of round it would be? I mean what kind of problem is contained in the problem set?

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

    problems will be all solvable in a programming language. I can bet on that if you want.

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

      Yeah there is always a solution that will be accepted. This if there won't be a problem that is mission impossible :)

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

    It is a sarcasm!!!

    As a tester, I would say that there will 10 output only tasks, and it will be a heuristic contest.

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

    Sure, I think that my guesses are correct, but we`ll see.

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

      You can never be sure for 100%

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

        Yeah,like that time when I got ill because we couldn't choose a place where to eat,lol.

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

Both Setters: Expert, Both Max: Candidate Master, Both From: Ukraine, Both Authored: 891 Div-3, All Setters(891): Expert, Rated till: !Expert;

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

    Both setters: UOI medalists. One of the setters: codechef 2198. Both setters: UJGOI problemsetters.

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

Hope for high-quality problems! ^_~

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

Hope I can reach 1550

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

last round organized by SashaT9 i turned from gray to green I wish I can turn from cyan to blue today !

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

Hoping for a colour change ( to green)

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

ICPC rules with a penalty of 10 minutes for an incorrect submission;

what does this mean? Do i get time deducted if i submit an incorrect solution? and after i solve it do i get my minutes back.

Sorry im not really familiar on how the contests work here

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

    So basically your final rank is based on comparing the number of problems you solved with everyone else. Now among the people who've solved the same number of problems as you, the ties are broken based on the sum of the submission times for each of your problems. Now if you submit say three incorrect solutions, but later submit the correct one for a particular problem then 10 * 3 mins are added to your total submission time for that problem.

    Hope this clears things!

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

      Yep it does, thank you for the clarification!!!

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

Do not be afraid, but be careful.

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

Hopefully this competition will be able to break through

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

Hope to solve A-E.

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

I hope to reach at least 1450 in the contest

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

one refresh costed me 10 mins ._.

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

delayforces...

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

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

Ten-minute delay in start time?

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

Why the time was delayed?

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

    could be some server issues due to a lot of requests!

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

I just hope this round does not come out as mathforces.

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

weak samples of B, literally passed it while misunderstanding statement of problem

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

    not a chance. your solution was correct.

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

Hope there will be plagiarism checking for this round

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

Unexpectedly solved A — F. Still don't know how i did, but i did. I am very proud of myself.

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

    E needs pre knowledge or it can be solved even if you know nothing about Manhattan distance ?

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

      It is just observational problem. I spent quite a time to find the arrangment that will always work.

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

        Same here. Had to visualize potential arrangements for n up to 6 to spot a pattern.

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

      I saw that [1, 1] [1, 3] [1, 4] ... [1, n-1] [2, 1] [n, n] was an answer, and I have no idea what Manhattan distance is.

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

        Maybe you can do better in the next time since that you already know what is Manhattan distance now.

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

what's testcase 2 for problem F.

spent almost an hour debugging it, still not able to find the mistake.

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

Thanks for the contest! Problems were quite good!

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

After solving D for like 20 minutes, I realized that I was solving the wrong problem since I did not notice that the player may also stay in the current position and not move to p[i].

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

I will now try to understand why my solution for E works haha. Thanks for the great problem set authors!

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

    I tried multiple random things still nothing worked

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

last minute i couldn't submit F, i am tilt :(

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

    I submitted problem F on the last second. The server were very laggy

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

E is very nice

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

    Yes, I agree with you. The task is very interesting. I really like this kind of task. Unfortunately, I was unable to solve this problem during the competition, if you solve this problem, can you explain your solution?

    Thanks!

    • »
      »
      »
      6 months ago, # ^ |
      Rev. 7   Vote: I like it 0 Vote: I do not like it
      explanation
      code
»
6 months ago, # |
Rev. 2   Vote: I like it +1 Vote: I do not like it

I spent an hour while coding wrong codes on D :(

seriously code once Think twice

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

LOL. Why E was not an A problem? I read the task at the end of contest.

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

    How to do it?

    • »
      »
      »
      6 months ago, # ^ |
      Rev. 2   Vote: I like it +18 Vote: I do not like it
      Solution spoiler
      • »
        »
        »
        »
        6 months ago, # ^ |
          Vote: I like it +2 Vote: I do not like it

        There are solutions and there are beautiful solutions.

    • »
      »
      »
      6 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      Another Valid Construction
  • »
    »
    6 months ago, # ^ |
      Vote: I like it +7 Vote: I do not like it

    As a tester I reckon problem E is 1700-1900, because my solution to E is so complex. I believe that a 1700 problem can be placed on problem E. (Well, to be honest problem E is harder than G2 for me)

    I used the Manhattan distance list to construct:

    n = 1, [], [0, 0] // n = 1, Manhattan list is [] (empty), can represent all integers in range [0, 0] n = 2, [1], [0, 1] n = 3, [1, 2], [0, 3] n = 4, [1, 3, 2], [0, 6] n = 5, [1, 3, 2, 2], [0, 8] n = 6, [1, 3, 2, 2, 2], [0, 10]

    I discovered this solution using 40 minutes, so I give it an 1700-1900 estimation. Why I used so much time because that I tried to represent the range [0, 2*n-2] by using the classical list [1, 2, 4, 8, 16, ...]. So I was far away from the right solution at the beginning.

    The constructive problems require a really high-level math instinct. Maybe you are talented. I believe that some skillful competitors will also struggle with solving it.

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

      Ye, I very much like constructive and pattern problems :)

      P.S. A has also very simple solution, so I was wrong about difficulty comparison.

      BTW E was nice problem.

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

Managed to solve D after wracking my brain for 1hr
Feeling Good :)

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

I wish I could downvote this contest multiple times. Pathetic problem statement for E

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

    welp, did you solve it? did you try to at least draw the matrices?)

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

    I couldn't solve it but I think statement was clear

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

any hints for E?

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

    Think about when you can have a set with all values from 1 to 2n — 2. When can you construct this? Is there a special case where you can't construct this?

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

    The maximum distinct distances will always be <= min(n(n-1)/2,2n-2) since the possible distances are 1,2,...., 2n-2. So, for n>=4 its enough to find a construction such that |H|= 2n-2. Select (1,1) and (n,n) first and try to find this construction.

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

      makes sense so I was thinking in the right direction after all. But wouldn't 0 also be a possible distance? so possible distance would be from 0 to 2n-2

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

May be its just me but the reloading of this site is too slow, I had 2 minutes and I wanted to submit E, but couldn't as it got stuck on reloading page. Please do the need full please.

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

Anyone did G1 with string hashing??

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

Why am I so bad at construction problems. I always get stuck at problems like E. Tips? Anyone??

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

    i cant prove it, but

    n = 1 => 1 1

    n = 2 => 1 1, 1 2

    n >= 3 => previous + (n, n)

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

      oh, no

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

      nice pfp with kings gambit)

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

      n = 3 => 1 1, 1 2, 3 1

      n >= 4 => previous + (n, n)

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

      Well, I didn't solve it in the contest but this is correct.

      The number of distinct possible distances in general is 2*n-1, you can generate Manhattan distances from 0 to 2*n-2, and for n = 4, you can get [0,1,2,3,4,5,6,7].

      So the solution increases by 2 numbers for each increase in n, 2*n-2, and 2*n-3, by adding n,n you add 2*n-2 since that is the Manhattan distance of 1,1 and n,n and you get 2*n-3 since that is the Manhattan distance of 1,2 and n,n.

      Retaining the previous solution you get Distances from 0 to 2*n-4 and by adding n,n you add 2*n-3 and 2*n-2.

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

      Proof:

      The goal is to get every possible path distance. This is possible for all n>3. All the path distances are the range [0:2n-2] (shortest: they are at the same position, longest: two opposite corners).

      Starting with (1,1) and (1,2) gets you the first 2 distances: d=0 and d=1.

      Say we have solved for n=3. (It is given that a solution is (1,1), (1,2), (3,3) Now, everytime n goes up by 1, we need to find two more distances, but with only one new position.

      Since we already have (1,1) and (1,2), we simply need to find a position that has manhattan distance 2n-3 and 2n-2 from these two points, at the same time.

      This new position is the bottom right corner, a.k.a. (n,n): manhattan distance from (1,1) to (n,n) is 2n-2 manhattan distance from (1,2) to (n,n) is 2n-3

      It is clear that we can simply repeat this process n-2 times, after having placed the original positions (1,1) and (1,2).

      Hope this helps :)

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

    Solve F.

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

    I totally agree with you! I got stuck at problem E when I tested it. And I even spend 40 minutes to solve it! Why I spent too much time on solving it, it was because that there is another classical problem: To express all the numbers in range [0, n], we can always choose [1, 2, 4, 8, ..., 2^(k-1)]. So I just tried this "solution" first. Well, I failed.

    After a while, I noticed that I don't need to minimize the elements I use. What I mean is that by using [1, 2, 4, 8, ..., 2^(k-1)] there is just O(log(n)) elements. But for this problem, we can use O(n) elements. Then I notice that I can just contrust the solution for n = 7 by adding one more elements in the solution for n = 6.

    That is the definite breakthrough, just add a new element in (n, n) is ok. This problem gave me the new idea that is not to solve the problem using the O(log(n)) thinking at first, just try to discover how to construct a new solution by the previous n. I think in constructive problem we should try to utilize different ways to analyse the same problem, and explore the protential solution by reading other users' code.

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

How does the 10minutes penalty work, does it only give penalty for problems that passed the first testcase cause I got a few wrong submissions but didnt get any penalty.

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

    if you failed on tc 1 then it will not give penalty . but thats bad that you are not checking your code locally.

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

    No penalty for wrong answer of testcase 1.

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

Why in problem e it was counting every cell with itself?

»
6 months ago, # |
Rev. 7   Vote: I like it -7 Vote: I do not like it

MY SUBMISSION

why I am getting garbage value in 1st sub TEST case of 1st ans? This is working on SUBLIME(The IDE I use) and also on CODECHEF IdE then why not in codeforces??

SINCE LAST 30 CONTEST trying to solve c and finally today its seems to happened but SEEMS UNlUCKY

"SashaT9" "FBI"

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

in Problem F, any idea why this code is giving idleness limit exceeded?

https://codeforces.net/contest/1968/submission/259209395

P.S. IDLENESS LIMIT EXCEEDED, NOT TIME LIMIT EXCEEDED

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

    Same happening with me... Time complexity is O(n*(4logn)) That is acceptable but still I'm getting TLE

    I have used segment tree to find the XOR of ranges

    my Submission Link

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

    i had the same problem its probably because of using a map and copying a long vector which is O(n) so when there are a lot of similar prefix xors (like in test 17 where there is a lot of 1s and 0s) each of those vectors is gonna be long and cost a lot my solution is using compression to store the vectors in an array of vectors instead so there is no need for copying them for each query but didn't have enough time to implement it, might try it later

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

      Got your point bro...copying a vector will take O(n) time in worst case.. So overall complexity will become O(n*n) in the query processing loop

      Taking it by reference will work !

      Thanks for pointing this out

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

    sarthakswarnkar, There is a version of your code that passes code.

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

FBI won't give me positive delta when he saw my pfp :sob:

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

    nice pfp. but i prefer Makise)

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

Hints For F , (when we have odd k ?(for even xor its 0))

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

    Let xor of block = Y, then pref[r] ^ pref[l-1] = Y. Look it inside l..r and check that after it comes even number of blocks.

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

      what comes even times? How will we know its good if y!=0?

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

    Ended up with the correct solution soon after the round ended.

    Take cumulative XORs at indices right before (p) and right after (q) the subarray. If equal, it can be split into 2 parts. If not, look for q and then p in between (sequence p...q...p...q). If found, it can be split into 3 parts.

    Now, iterating through the subarray to find the q and p in the middle is worst case (edit: O(n) per query, O(nq) in total, where q = # of queries) and ended up TLE'ing. Had to use a dictionary (cumulative XOR value -> list of indices) and BS through the lists. The time it took to get the index calculation right was why I couldn't submit on time.

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

Didn't read E until the last minute but between any pair of cells is confusing when reading the notes, probably need something like between any pair of cells (including each cell with itself)

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

    Even if we exclude pair containing a cell with itself, the answer stays the same. |H| will just be reduced by 1 for every n.

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

      Yeah but like if it doesn't even matter then I guess it's best to just not include each cell with itself in the notes lol.

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

    "...confusing when reading the notes..." Well, I don't recommend what I'm about to say, but maybe don't read the notes when the problem statement is pretty clear and has almost no room for ambiguity? And even if you do and discover some extremely weird ambiguity (which happened in this case, I agree with you), maybe gather yourself and cancel out that thought quickly, like "well it doesn't matter cause if I generate any answer it will have the distance 0 anyways so let's ignore this bullsh* and solve normally"?

    Also, the notes section of construction problems usually helps only to find any patterns. I "read" the notes, but only saw the figures and tried to understand what might a good strategy be. Really didn't look at the $$$\mathcal{H}$$$ set in the notes until I saw this comment.

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

      I mean I didn't complain because I didn't solve it

      I only mentioned it in this comment, because well it literally is a comment for the problem statement itself that it shouldn't be confusing

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

        Right, agreed. It shouldn't have been calculated or worded like this.

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

Problem C. Assembly via Remainders ***** this is my solution, it is correct i guess but the test case says failed . dunno why :

include

using namespace std;

void solve() { int n; cin >> n; int arr1[n-1]; for (int i = 0; i < n — 1; i++) { cin >> arr1[i]; }

int arr2[n];
arr2[0] =  arr1[0] + 1;

for (int i = 0; i < n - 1; i++) {
    arr2[i + 1] = arr2[i] + arr1[i];
}

for (int i = 0; i < n; i++) {
    cout << arr2[i] << " ";
}
cout << endl;

}

int main() { int t; cin >> t; while (t--) { solve(); } return 0; }

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

    example: 2 499 21

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

    you may try to fix your code by add another 505(for example), to make sure your arr2[i+1] is greater than arr[i+1]

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

    assuming arr2[0]=arr1[0] +1 might be causing the trouble here. What if arr1 has an element that is greater than greatest element while calculating arr2...let's say arr 2 while calculating got us 3 and arr1 has 5 in the next iteration? mod 3 has range 0-2 so getting 5 while be impossible.... best way to overcome this is to ensure arr2 has all elements greater than max element of arr1

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

Why is my G1 fails on test case 2

link: https://codeforces.net/contest/1968/submission/259244119

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

    s = "aaaaaabaaa"

    s1 = "aaaaabaaa"

    using your algorithm, s1 didn't exist as substring of s

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

E is awesome, costing most of my time on it but still, stuck:( Nice Round indeed, but sad negative delta for me:((

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

E Good Job. I live this.

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

tasks was nice

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

any hint for F??

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

    if subarray xor is even it is always possible
    for odd, if answer exists, then it is always possible to break subarray into exactly 3 segments , each one of them having the same xor as whole subarray

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

    You only need to split the subarray into either 2 or 3 subsegments, since you can compress any way of splitting into 4, 5, ... into just these two cases.

    If the subarray was to be split into 2, there must exist l<=i<r so that xor[l..i]==xor[i+1..r]. Doing some algebra magic, we get that xor[1..l-1]=xor[i..r]. So we just need to check the equivalence of these two prefix xors (O(1)), without any need for iterating!

    If the subarray was to be split into 3, similarly, there must exist l<=i<j<r so that xor[l..i]==xor[i+1..j]==xor[j+1..r]. Using a bit of rearranging, we get xor[1..l-1]==xor[1..j] and xor[1..i]==xor[1..r]. We can maintain a map/unordered_map of sets to keep track of the indexes where each value appears and greedily choose i and j so that the two conditions above hold in O(log(n)) time.

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

      Wow I was able to figure out we only need 2 / 3 splits but went nowhere from that. I am so stupid..

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

wasted 10 mins in D thinking that each player k/2 turns

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

could anyone please tell me a counter test case to my solution on G1, i could not find one by stress testing as well

https://codeforces.net/contest/1968/submission/259246021

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

    unrelated but by selecting all code and pressing shift+tab you can delete the spaces at the start of the lines

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

This was my first contest. I was able to solve only 2 questions. I am not running after rating but can someone tell me what rating will I get? I am really excited about it

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

Hope I will turn back green today. So bored of gray ..

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

Very nice contest with very nice problems :) Thanks a lot for the round FBI SashaT9 and all testers!

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

Weak tests again....

259139777

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

    $$$N^3$$$ for $$$N = 1000$$$ works well if it has a small constant. Your solution doesn't have a big constant. Worst case is test t = 1000 x = 1000, your solution works well there

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

      unbelievable. so corrupt constraints. and for what? to give c++ coders another advantage. in div 3 round...

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

    Wow.... Weak tests.... For the easiest problem of the round.... For the problem where there are at most 1000 different possible tests... Wow....

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

      Sure you guys did your best. But why it is 1000 but not 100 or not 10000 we will never know...

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

        because x values can be only up to 1000 (actually because x is only in range [2,1000] there are not 1000 but 999 possible tests)

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

What is the intended solution for G2? I used string hashing and set to solve it in worst case O(N * (log N)^2), but average case would be better than this.

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

    Do you have any proof for the upper bound when using hash? I did with zfunc worst case O(N* (logN)^2)

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

      Yes I have proven it. My algorithm is that for every length of prefix I have a set called candidate that stores the starting indices which have the same substring as the prefix for until the previous length.

      Now for the current length I can find the count in N log N/ len. So the complexity will be N log(N) ^ 2.

      You can check this submission: 259254423

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

        Ya got it, so you are removing the candidates which don't have prefix of length l same so they wont be checked ever again, and in the worst case if no candidate are removed then its the same as nlog^2n when all char are equal. Great!

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

          Yes perfect! You described it better than I could :)

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

problem E be like WA on pretest 1 🤡

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

For Problem G1 I wrote this code


bool ok(int len,string &s,int k) { int n = s.size(); string t = s.substr(0,len); int cnt = 1,idx = 0; for(int i=len;i<n;i++) { if(s[i] == t[idx]) idx++; else { idx = 0; if(s[i] == t[idx]) idx++; } if(idx == len) { idx = 0; cnt++; } } return cnt >= k; } void solve() { int n,a,b; cin>>n>>a>>b; string s; cin>>s; int l = 0, r = n+1; while(r - l > 1) { int mid = (r+l)/2; if(ok(mid,s,b)) l = mid; else r = mid; } cout<<l<<endl; }

Tried with many custom cases still couldn't figure what's wrong here. Can anyone please look and point out the mistake here.

Here i am just trying to find number of partitions where all partitions contains a string "t" (as declared in code) as prefix and check whether number of partitons is greater or equal to the asked partitions defined in question.

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

Thank you for tasty problems. I enjoyed.

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

today's contest as expected as this was div3 so solutions to problem A,B,C,D all soon were available by 21:00 , i tried very much in finding the cheated ones which many tried modifying: the cheated solution readily available for problem D from 21:00(UTC+5.5) https://ibb.co/Rph74Qd https://ibb.co/f2rx42K . please ban these cheaters : i already mention about some of them before. 259222711 259219713 259230136 259217156 259228528 259227463 259228698 in fact some of them also tried the later problem solutions from some sources. like for problem F i will share what i find later . MikeMirzayanov Vladosiya

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

    for E nothing can be told as that was very much same for most of them but for F some tried last moment cheated solutions acceptance to improve their rank . This was the cheated solution for problem F : https://ibb.co/wKPK3tH . in fact this user "jam_coder" tried submitting this cheated solution with some change in the variables exact same form of the solution : 259244079 luck was not in her/his side for this problem as her/his was run time errored Similarly user "kaminenisaisriram" cheated the G1 solution too but it got rte in last moment hurry if needed i can show the G1 cheated sol later. Similarly these too cheated submissions (for F) which got accepted: 259240705 259240389 259239867 259238933 259238439 MikeMirzayanov Vladosiya

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

Thanks for this round. enjoyed solving.

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

Superv Div3..it was exciting

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

please don't make problem like E again.

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

    Why? Because it forces you to think in a different way?

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

Enjoy the problems, thanks! Wondering what is the other solution for G2 other than the memoization with binary search approach. I feel like it had a different intended solution.

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

G1 should be banished to the shadow realm. 99.99% of test cases can be solved with a binary search + interation. So, I coded that up expected a full solve. I got WA on TC2 number 384. Brvh. Then I figured out my mistake after 1 hour of stoopid grinding out bullcrap testcases. Then, the implementation of this edge case fix became harder thaan the actual problem itself. So, basically thsi problem is so easy to fall into a stupid trap and it will take hours of your life to get out of it. For those of you that do this contest as practice. GIVE UP ON G1 if you get WA2, not worth the effort to try to fix.

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

    sorry for the rant. I am not saying that G1 was a bad problem per say but incredibly deceptive. DO NOT RECOMMEND IT.

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

For problem G1,

I use a binary serch for answer and brute force judging if there is so many substrings exist.I think my solution is O(nlogn),while it was hacked and turned to be TLE

My code is here.I'm really curious about why.259250187-

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

    Oh,I find that my brute force can be n*n,so I'm hacked.

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

I'm confused. Was G2 simply bruteforce with extra steps...?

I'm not sure if my solution is hackable or not, and if not, was it under intended complexity? (it seems like $$$\mathcal{O}(n \log^2{n})$$$, but I'm not too certain).

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

    It isn't brute force actually, the while loop runs for nlogn, it's the same pattern as n+n/2+n/3+..n/n, also the lower_bound call adds another factor of logn making it nlog^2n

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

      Thanks for the complexity analysis, it makes sense.

      For the brute force part, I meant for the whole problem, yet I think I mistakenly coined it. It's more like a provable greedy with lower_bound to speed up the probing :D

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

... I take part in only 4 rated contests, this is first contest where I solve more than 2 problems and this is without rating for me ..

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

    Regardless of whether you are a trusted participant of the third division or not, if your rating is less than 1600 (or you are a newcomer/unrated), then the round will be rated for you.

    It will be rated for you for sure

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

when will this contest rating be updated..........any idea ?

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

    After system testing ends.

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

      Hello Vladosiya may you please check my previous comment in this blog post ? No cheaters were caught at all from the list i shared above from the system testing .I hope so in later future rating roll backs those will get punished.(because some of them are consistent in not getting detected by plagiarism checker)

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

      123

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

        same to me, it shows me that this contest was unranked, witch makes no sense

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

very educational round! rk11 in official rank list ^_^

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

thx for very amazing contest. It was very cool!!!

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

Nice Problems

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

i am 912 and it shows me that i am not rated for this round :{

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

The problemset was nice !

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

G2:

I repalced the Z_function with Double Hash, but it's TLE, Can someone explain?

259385157

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

In problem G2 the input section is described as, "The first line of each test case contains two integers n, l, r (1≤l≤r≤n≤2⋅105) — the length of the string and the given range." Isn't there a issue here? I mean, two integers and then n, l, r!!! (Actually three integers// Same for G1 also). Could someone explain this, please?

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

.

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

.

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

    Perhaps, this contest has been marked as unrated now, don't know the reason

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

I LOVE DIV 3

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

Can anyone tell why simple binary search on the answer from 1 to n won't work ? Can anyone suggest any string which don't follow this. 265440846.

UPD : Got my mistake..