Rating changes for last rounds are temporarily rolled back. They will be returned soon. ×

By awoo, history, 9 days ago, translation, In English

Hello Codeforces!

On Aug/04/2022 17:35 (Moscow time) Educational Codeforces Round 133 (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

Harbour.Space's Front-end Development programme is where programming and creativity collide. Receive up to a 50% scholarship and take advantage of this opportunity to study in Barcelona and learn from industry experts while you become one yourself.

The programme is heavily geared towards developing students’ professional skills needed for employment while being able to adapt to rapidly changing technology.

So let's meet your programme leaders:

Harbour.Space

Hjörtur is the CEO of 14islands, a design and development studio from Stockholm in Sweden and Floripa in Brazil. He co-founded the studio in 2011 and since then they've done work with companies such as Google, Adidas, Disney, Facebook, HBO, Shopify, Ericsson and many innovative startups in the world.

Marco Barbosa is the Managing Director of 14islands, a design and development studio from Stockholm in Sweden and Floripa in Brazil. Their projects have won multiple awards such as the FWA, Awwwards, CSS Design Awards, and European Design Awards.

Apply Now →

Good luck,

Harbour.Space University Team

UPD: Editorial is out

 
 
 
 
  • Vote: I like it
  • -242
  • Vote: I do not like it

»
9 days ago, # |
Rev. 2   Vote: I like it -9 Vote: I do not like it

Good luck everyone!! Hopefully everyone has fun!

»
9 days ago, # |
Rev. 2   Vote: I like it -96 Vote: I do not like it

Stop downvoting my comment, please XD

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

    Why do you want unrated round when there are so many virtual contests already?

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

    Why do you want unrated? The whole point of rating is to see if you are improving or not, and unrated rounds would also be not fun. If you want unrated just do virtual participation

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

    Unrated rounds are already technically in codeforces (virtual rounds).

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

    Oh I will downvote your comment buddy.

»
9 days ago, # |
  Vote: I like it +7 Vote: I do not like it

You can do anything, just don't give up!

»
9 days ago, # |
Rev. 2   Vote: I like it +36 Vote: I do not like it

1 point away from expert. Hope this will seal the deal!

Edit: Sorry for jinxing it guys :(

  • »
    »
    9 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    all the best

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

    Good luck! But don't get too focused on this, or you will become nervous and won't solve problems that well. Remember, it's just a round and you should try to enjoy it no matter what your rating now is:)

  • »
    »
    8 hours ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You made it congrats.

»
9 days ago, # |
  Vote: I like it 0 Vote: I do not like it

You should aim for questions rated for X+200 where X is your rating to make improvement.

Do u agree with this ?

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

    I try to aim for X + 400, I think it doesn't matter much

  • »
    »
    8 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I agree

  • »
    »
    7 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I prefer segment rather than single rating. I train on problems rated from x to x+500 where x is my rating.

  • »
    »
    7 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Start with problem rating range 800-1000 and after every solve, increase the lower bound and upper bound by 300. In this way, you can practice fast solve and hard solve both.

»
9 days ago, # |
  Vote: I like it 0 Vote: I do not like it

I am competing red coders in parallel universe.

»
9 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Hope i solve ABC

»
9 days ago, # |
  Vote: I like it +7 Vote: I do not like it

Here's a hint: prefix sum and binary search.

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

    It's called educational for a reason

»
8 days ago, # |
  Vote: I like it -14 Vote: I do not like it

If you play with me, you will have a lot of fun

»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

I hope to get a chance to be on the blue for this game, good luck to you guys and good luck to myself

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

    Thanks, good luck to you too

    • »
      »
      »
      8 days ago, # ^ |
      Rev. 2   Vote: I like it -29 Vote: I do not like it

      wuwu

      • »
        »
        »
        »
        7 days ago, # ^ |
          Vote: I like it -9 Vote: I do not like it

        She should be as lovely as you are, little beauty

        • »
          »
          »
          »
          »
          7 days ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          get off the internet you fucking disgusting pedophile

          • »
            »
            »
            »
            »
            »
            7 days ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            You are sick, just in the girl to girl compliments

            • »
              »
              »
              »
              »
              »
              »
              7 days ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              you make no sense you absolute idiot
              actual pedo out in the wild, how can you like these 5 year old looking anime drawings, you're absolutely disgusting you scum

»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Good Luck to everyone.☆(✧'ᗢ'✧)ฅ

»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Hope everyone has good luck.

»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

look forward to solve ABC. Ah, it is enough to me

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

Hope the questions are EASY :)

»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Good luck everyone I hope to solve ABC

»
8 days ago, # |
  Vote: I like it -38 Vote: I do not like it

as usual segregation on codeforces ... the community wants unrated so everyone can participate but you always seek to separate "your league" from "the rest". typical russians but what can you do i guess

»
8 days ago, # |
  Vote: I like it +16 Vote: I do not like it

Hope I will get higher rating this time,it's really terrible to get lower rating for many times……

»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

I hope the editorial will be posted right after the contest this time.

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

Hope, I will become Expert Again today !!!

»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

feel excited to make myself green again (mmga) hope things don't turn against me

»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

I'm stuck on Expert for too long. Hope I can be candidate master this round

»
8 days ago, # |
  Vote: I like it +22 Vote: I do not like it

seems like B and C difficulty difference is high

»
8 days ago, # |
  Vote: I like it +33 Vote: I do not like it
Well :')
»
8 days ago, # |
  Vote: I like it +43 Vote: I do not like it

Bros made a div 1 contest, added 2 easy problems for A and B, and named it div 2.

»
8 days ago, # |
  Vote: I like it +19 Vote: I do not like it

The difficulty gap between B and C is too big……

  • »
    »
    7 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Agree, but again C was harder than D... and gap between B and D isn't big.

»
8 days ago, # |
Rev. 2   Vote: I like it +5 Vote: I do not like it

Toughest educational round ever ?? :)

»
8 days ago, # |
  Vote: I like it +28 Vote: I do not like it

Problem C is much more difficult than normal C problems

  • »
    »
    8 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    yes

  • »
    »
    8 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    c and d >= 1900 (acc to me)

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

      D <= 1600

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

        D <= 1600 is a little bit of a stretch bro. No 1600 question would get under 1000 solves in a contest. D is kind of annoying to implement and optimize for a 1600. I'd expect it to be around 1700-1900 to be honest.

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

        both are 2000 :)

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

          Hm, ok, but on my pov D was easier.

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

For the big part of contestants (including me) the only real challenge was to solve A and B as quick as possible.

»
8 days ago, # |
  Vote: I like it +18 Vote: I do not like it

Worst Edu round ever .

  • »
    »
    7 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yeah, if you solve just 3 problems you get in top-1000, C is very cringy, D is hard to optimise (had to use pragmas)

»
8 days ago, # |
  Vote: I like it +44 Vote: I do not like it
meme
  • »
    »
    7 days ago, # ^ |
      Vote: I like it -11 Vote: I do not like it

    It's called the exponential round, every two problems you loose one order of magnitude of the contestants :).

»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Thanks for speedforces, I am sure everybody likes this round! \s

»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

If anyone is new to codeforces today this type of contests happens once in a while and is referred as speedforces. Don't judge by this contest and leave codeforces :(

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

    Little clearer: Don't judge by this contest and don't leave codeforces

  • »
    »
    8 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    But every 1 in 4 contest is like this only.

»
8 days ago, # |
Rev. 2   Vote: I like it +23 Vote: I do not like it

The difficult gap between B and C is too big :( Perhaps this is the most difficult C in Div. 2 that I have ever participated in.

  • »
    »
    7 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    it may be not. Actually when you check the solution you won't find it so difficult :)

»
8 days ago, # |
  Vote: I like it +32 Vote: I do not like it

When I finished A & B and read C & D, I realized that the contest for me was over.

»
8 days ago, # |
  Vote: I like it +5 Vote: I do not like it

Оne gets the impression that this contest was made specifically for advertising. Completely unbalanced quests posted (in my opinion)

»
8 days ago, # |
  Vote: I like it +8 Vote: I do not like it

What are c and d of this contest.

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

What's speedforces?

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

    It's a contest where there's a large gap between two adjacent problems (In this case B and C). This leads to a bottleneck where a lot of people can't get past that one question, meaning the rankings for them are solely determined by the SPEED in which they solved the other problems.

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

      Thanks a lot!(●'◡'●)

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

      And the performance of contestants who are able to solve problems in the range 1400-1600 becomes comparable to that of contestants who are able to solve problems till 1300 only.

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

speedforces

»
8 days ago, # |
  Vote: I like it +8 Vote: I do not like it

SpeedforcesAB

»
8 days ago, # |
  Vote: I like it +6 Vote: I do not like it

disgusting speedforces :(

»
8 days ago, # |
  Vote: I like it +7 Vote: I do not like it

Not SPEEDFORCES, but HACKFORCES!!!

I want to predict that, the hacking will be crowded, especially for the AB participants.

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

    but literally how do you hack A or B

    like, how the heck

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

.

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

    Glad to see that greys are well-acquainted with what Div. 1 is like.

»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

The contest Is not bad but problem C is tricky a lot. I think It will be an 1800 rating or higher.

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

Please tell me that 4th problem is not a space optimization dp problem.

I suck at iterative dp.

  • »
    »
    8 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yeah, I tried dp but it was too slow.

    • »
      »
      »
      8 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I thought it was dp, but I can't find the optimization to it.

  • »
    »
    8 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Hint:Use prefix sum to speed the dp up!

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

    Not entirely sure what you mean by space optimization, but I used DP with $$$n$$$ columns and 2 rows (representing many more rows, but only the previous row is needed for filling the current row), along with keeping track of when the first non-zero element of the column will be (so I don't waste time iterating over the elements before it).

    This does sound like I'm saving space, so it might fall under space optimization DP (again, idk what you actually mean by it), but my main objective was to save time.

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

      My aim is to solve this problem with recursive dp.

      The thing you did is space optimization which cannot be done in recursive dp i guess.

  • »
    »
    7 days ago, # ^ |
    Rev. 7   Vote: I like it +20 Vote: I do not like it

    It's not very hard (it just suck that I didn't implement this on time).

    Hint
    The barebone of the solution
    Implementing the naive solution
    Speed optimization
    Space optimization

    Edit: When the test cases got updated, I got TLE, then I resubmitted the code, then got AC. I guess because the constraint was so tight that it just comes down to being lucky :<< (My solution ran in 1949ms, very close to the constraint of 2000ms).

    Code (failed): 167051557. Code (passed): 167085973

    • »
      »
      »
      7 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      Meme
    • »
      »
      »
      7 days ago, # ^ |
      Rev. 2   Vote: I like it +1 Vote: I do not like it

      "We have drastically reduced the complexity down to O(n∗n−−√), which would run comfortably with the stated constraint"

      Your submission also got TLE! But really good mini editorial other than that

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

        It's kinda random. I resubmitted the code and it got Accepted. The run time was like 1949ms, very close, so I must admit, not very comfortable lol (I don't really know why, $$$O(n * \sqrt{n})$$$ complexity usually run in 300ms, so seeing my solution getting up to 1900ms is kinda strange).

        Btw I got green yay.

        Code: 167085973

»
8 days ago, # |
  Vote: I like it +18 Vote: I do not like it

i hate edu rounds always the same fucking story.

  • »
    »
    8 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    bro im so agree with you

    • »
      »
      »
      8 days ago, # ^ |
      Rev. 2   Vote: I like it -7 Vote: I do not like it

      ofc bro....this is real waste of contest...i have stopped giving edu rounds from my main account. It is such a waste of rating and time.

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

    No contest is "too difficult" everyone is in the same conditions than you, so if you are better than then, no matter how difficult the contest is you are gonna raise your rating

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

      Being a Candidate Master it becomes easy say it.....but if you see C and D were 2000 many pupils , Specilaists , experts suffer from this type of contest as they were too difficult for people on these ratings.

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

How to solve $$$C$$$?

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

    There is only a fairly simple pattern of movement possible, because each cell must not be entered more than once.

    This is, we go right covering both rows until some col, then got right in the current row to the end, then left back to the col in the other row.

    All of this can be precalculated with prefix sums, and min/max operations.

    Of course all of this is very off-by-one error prone. And actually, I am still not sure about the meaning of:

    "The robot can only move into a cell (i,j) if at least ai,j seconds have passed before the move."

    If a[i][j]==x, can we enter at x, or at x+1?

    • »
      »
      »
      8 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      why the ans of this is 5 3 0 5 0 0 0 0

      And the ans of this is 17? dose it means robot can only go to another position until 11 seconds past? 4 0 10 10 10 10 10 10 10

      • »
        »
        »
        »
        8 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        The robot enters cell[0][0] at time 0, and each other cell earliest at a[i][j]+1.

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

How to do D?

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

    First I wrote a $$$O(\sqrt{n} \cdot n \cdot \log n)$$$ DP, thinking it may pass, but it's TLE. Then I realized there is an optimization to get rid of the $$$\log n$$$ part.

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

      I made the same mistake at first :) "Naive" dp is actually $$$O(n^2 \log n)$$$.

    • »
      »
      »
      8 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      same, but i fucked up in prefix sums speed-up probably due to pressure

    • »
      »
      »
      7 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I also wrote the same DP and hope it passes :(

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

    We can calculate $$$dp[i][j]$$$ — number of way to get $$$j$$$ in $$$i$$$ moves. Then for $$$x = 1$$$ $$$dp[1][j] = 1, dp[2][j] = dp[1][j - 2] + dp[1][j - 4] + dp[1][j - 6] + \dots, dp[i][j] = dp[i - 1][j - i] + dp[i - 1][j - 2i] + \dots, dp[i][j] = dp[i - 1][j - i] + dp[i][j - i]$$$ (try to understand, why last correct). This is a quadratic dp. But look: if we done $$$i$$$ move, our answer is at least $$$1 + 2 + \dots + i = O(i^2)$$$. This means, that the first dimension of array is $$$O(\sqrt{n})$$$. I brough 800. Also, if you try to declare the whole array, you will get $$$MLE$$$. Instead, declare only two rows, calculate next, and delete previous.

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

    I used DP, where $$$dp[i][j]$$$ represents the number of ways to reach $$$j$$$ while using at least one $$$(k + i)$$$ step, but no larger steps. Then $$$dp[i][j] = dp[i][j - (k + i)] + dp[i - 1][j - (k + i)]$$$.

    To save space, I only maintained two rows, since each row only depends on the previous row. To save time, I also kept track of what the first non-zero element of each column will be, so I don't iterate over the elements on the left (which I know are 0).

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

    Use dp.

    It is easy to see the steps must be not big,about $$$\sqrt{n}$$$.

    Set $$$f_{i,j}$$$ as the answer of $$$i$$$ steps reach $$$j$$$.

    $$$f_{i,j}=\sum_{l=1}^{j-1} f_l*[(j-l) \mod (k+i-1) == 0]$$$

    Then we can use rolling arrays to optimize the memory and use prefix sum to optimize the time.

    Then it is a $$$O(n\sqrt{n})$$$ solution.

    Code: 166958668

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

What I did in the contest:

  • read A

  • A done

  • read B

  • B done

  • read C

  • read D

  • read E

  • welcome to osu!

  • Click the circle!

»
8 days ago, # |
  Vote: I like it -11 Vote: I do not like it

speedforces

  • »
    »
    8 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    With respect, will you please explain what does 'speedforces' mean? I see this term a lot. But I don't know what it means.

    • »
      »
      »
      8 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      This comment explains it.

    • »
      »
      »
      8 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      it means, the first x problems were too easy and the last x problems(usually 2<=x<=4) were too hard leading to a lot of people having to get separated in rankings by total penalty taken to solve x problems. This is really annoying for people who are stronger but solve problems slower but very nice for weaker speed-solvers.

»
8 days ago, # |
  Vote: I like it -16 Vote: I do not like it

This is why i hate speedforce i got a wrong submission on A than due to this i complete A and B in 24 minutes due to this currently my rank is over 7K.

»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

D was stars and bars ? ??

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

    I solved it using dp. DPij means the number of sets such that the last number is i and the last permormed operation was with k' = k + j. Then ans[i] is the sum of DPij over all j. But if you do this naively the solution will run in O(n^2). Think how to optimize this dp to run in O(n * sqrt(n)).

»
8 days ago, # |
  Vote: I like it -16 Vote: I do not like it

You know the contest is trash when you even tried to attempt F during the round

»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve C and D?

»
8 days ago, # |
  Vote: I like it +4 Vote: I do not like it

This educational contest seems too spartan for me...

»
8 days ago, # |
  Vote: I like it -59 Vote: I do not like it

i think awoo , adedalic ,BledDest are out of ideas. They should probably rest and give problem setting and testing to some other guys.

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

    That's what I was thinkiiinng! Great to finally find some support <3

»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Speedforces :)

»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

For question C, aren't there only 3 possible paths? One is clockwise, one is counterclockwise, one is zigzag. I tried all three paths but it didn't work? Please help

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

    Zig-zag too consists of some other paths like when you choose to complete all columns of a row first!

    • »
      »
      »
      8 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      That would be a difficult implementation

      • »
        »
        »
        »
        7 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        This problem is about finding out when you need to switch from zig zag to another pattern.

  • »
    »
    8 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It can be zigzag, then a big turn.

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

    You can do a little bit of zigzag at the beginning and then clockwise or counterclockwise

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

    There's more than 3. You have a prefix of zigzag moves, and then remaining clockwise or counterclockwise. The choice is where you stop zigzagging.

  • »
    »
    8 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    zigzag + clock or counter?

  • »
    »
    8 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    you should check all possible ways like that:

    start and go clockwise
    X---|
    <--|

    down and counterclockwise
    X<--|
    X --|

    again up and clockwise
    XX -|
    XX<-|

    and so on

  • »
    »
    8 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I also thought that. But the number of solves is to little for it to be that easy.

  • »
    »
    8 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    During the zigzag, you can start a clockwise or counterclockwise path at any point.

  • »
    »
    8 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    To be completely honest, I don't possibly see how they would think this is a Div2C. In my opinion, it would at least be a Div2D, or even a E for an educational round.

  • »
    »
    8 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I also thought this way and wrote kinda naive approach and with lot of lines of code..

    Your text to link here...

  • »
    »
    8 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Maybe Zigzag till some index and later either cw or acw. I couldn't implement it tho :(

»
8 days ago, # |
  Vote: I like it +149 Vote: I do not like it

wow

»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Any pointers for D?

My potato brain can only think of the most naive solution

»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

I thought I will start from problem C and do backword. contest got over even then i was not able to solve c. why they give such unbalance questions in a contest??

»
8 days ago, # |
  Vote: I like it +75 Vote: I do not like it

F is a VERY VERY VERY standard stirling problem and has occurred in codeforces before. And I don't know the point in the strict time limit that $$$O(Tklog(998244353))$$$ can't pass. And as a master, I don't know how to solve C. C is too difficult.

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

So it's called speedforces because for most of the contestants the ratings depend on how fast they solve the first few questions, right?

First time taking part in such an unusual round. I failed to solve D but I find it very interesting, though.

»
8 days ago, # |
  Vote: I like it +83 Vote: I do not like it

I think E is much harder than F.

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

If they made D have lower constraints and then swap C and D, the contest could have been more balanced. The idea for D wasn't too difficult but everyone was getting TLE because it was so hard to optimize past O(N^2).

»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

I think that would be a good contest if authors had split problems C and D into 2 parts with better restrictions. Optimizing C and D by time + memory to get AC for 2 hours is not fun (and I still was not able to get AC on either of them).

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

[Deleted]

  • »
    »
    8 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Not true, your path consists of a prefix of zigzags, followed by a suffix of the 2 straight lines. So there are more than 3 possible paths.

  • »
    »
    8 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    The robot can zigzag for a few columns and then go clockwise/anticlockwise.

»
8 days ago, # |
Rev. 6   Vote: I like it +11 Vote: I do not like it

Why couldn't the Memory Limit for D be 512 mb?
Seemed like a deliberate attempt to force the participants to ONLY come up with some specific obscure logic.

»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

I did have some thoughts on C. I think we should go zigzag column by column on a prefix then do a round trip on suffix. But i don't know how to calculate the time needed for the suffix efficiently.

»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone find a counter test for this WA 5 solution for E? Thanks. 167008625

I clam that the order in which swaps are performed doesn't matter, so I calculate the solution for all the combinations of first 10 bits, then I bruteforce update the remaining ones. Is this ok approach?

»
8 days ago, # |
  Vote: I like it +17 Vote: I do not like it

D was absolute best!. Couldn't solve it but enjoyed thinking about it. Same for C.

»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Any one though of solving C using DFS where every time we choose the minimum neighbor and add the just visited neighbor + 1 to the answer ?

  • »
    »
    8 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Anytime you decide to pick the neighbour on the right, you'll have to traverse the grid either clockwise or counter-clockwise in order to visit all indexes in the grid. Seems like more of a DP problem.

    1. Zig-Zag till a certain index
    2. Clockwise / Counter-Clockwise
  • »
    »
    7 days ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    Dfs backtracks, whereas in the problem you are not allowed to visit any cell twice or more.

»
8 days ago, # |
  Vote: I like it +14 Vote: I do not like it

can someone tell me why n * sqrt(n) in D doesn't pass? I made linear memory solution (or almost..) but it TLEs.. how...

  • »
    »
    8 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It should pass, but with proper realisation

  • »
    »
    8 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It has to pass, but yes, the limits are very strict.

    Also, it seems, that the whole array is bigger, than memory limit. I instead used only two rows.

    • »
      »
      »
      8 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      at least i came up with the idea, though it isn't too hard...

  • »
    »
    8 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    probably because of the log factor of the std::map.

    • »
      »
      »
      8 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      i tried everything: unordered_map with custom hash function, simple vector (but it caused MLE)...

  • »
    »
    8 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I'm in the same situation as you.The time limit is too tight. 167005425

»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Speedforces

»
8 days ago, # |
  Vote: I like it +6 Vote: I do not like it

I had major connection problems during the contest, which only affected codeforces.

Am I the only one in this case ?

»
8 days ago, # |
  Vote: I like it +5 Vote: I do not like it

Hardforces

»
8 days ago, # |
  Vote: I like it +56 Vote: I do not like it

in C a[0][0] = -1 removes all chaos in mind

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

My opinions on the problemset:
A: Involved a bit of thinking, but alright
B: Easier than A imo
C: Very annoying for C, but if you see the zigzag pattern and a bit of suffix maximums (clockwise, counterclockwise), it's doable
D: Easier than C. $$$O(N\sqrt{N})$$$ DP knowing that the maximum number of steps is bounded to $$$O(\sqrt{N})$$$ from $$$1+2+3+...+k = \frac{k(k+1)}{2}$$$
E: I like this problem. A bit of thinking made me realize it is similar to a segment tree and in each node we store $$$2^i$$$ values for each bitmask when the height of the node is i. Solid.
F: Didn't solve it, but I came up with a $$$O(k^2)$$$ using the fact that the sum of $$$F^k$$$ is equivalent to the number of $$$k$$$-tuples. I will try to upsolve it soon.

EDIT: I upsolved F. I solved it using stirling number of the second kind + counting ordered k-tuples. My solution runs in $$$O(Tk + MAXK^2)$$$, where the $$$MAXK^2$$$ is from pre-calculating the stirling numbers.

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

    how did you exactly solve D in O(n * sqrt(n))? I did also notice that maximum number of steps is 632, which is close to sqrt(n), but my solution tles, though i've optimized it a lot

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

      Tight time limits. I got TLE for three times.

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

      Oh I think for each step, you should disregard the $$$dp_i$$$ values for $$$i$$$ values that are below the possible minimum value that can be achieved.

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

    For A you wrote it like it shouldn't contain any thinking.

    • »
      »
      »
      8 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Sorry if I sounded like that, what I meant was I was kinda surprised how B felt easier than A

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

      I think it shouldn't.

  • »
    »
    8 days ago, # ^ |
      Vote: I like it +10 Vote: I do not like it
  • »
    »
    7 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    The stucking part was finding the values for suffix

  • »
    »
    7 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    How to solve F? What is the relationship between this problem and Stirling number?

    • »
      »
      »
      7 days ago, # ^ |
      Rev. 2   Vote: I like it +8 Vote: I do not like it

      Sum of F^k is essentially the number of occurrences of all possible ordered k-tuples of indices that have an odd-numbered ball (Errichto had a blog about this Link.

      So, this can be calculated by iterating over the number of distinct indices that show up in the k-tuples. We can think of the number of k-tuples with $$$j$$$ distinct indices as an ordered integer partition of 1..k (think of putting 1 to k in $$$j$$$ boxes labelled with the indices), so for a set of $$$j$$$ distinct indices, we have $$$S(k, j)*j!$$$ ways of doing it.

      Note that this does not address the rest of the problem, so now we have to consider the number of ways of selecting j indices from 1..n, and filling those $$$j$$$ balls with odd integers, and the rest $$$(m-j)$$$ with even integers. The formula we get is similar to binomial theorem:
      $$$\sum_{j=1}^{k} S(k,j)j! (\sum_{i=0}^{n}{n \choose i}{i \choose j}x^{i}(m-x)^{n-i})$$$ which can be rewritten as
      $$$\sum_{j=1}^{k} S(k,j) (\sum_{i=0}^{n}i(i-1)...(i-(j-1)){n \choose i}x^i(m-x)^{n-i})$$$

      We can differentiate a few times to derive the equations for the second summand (ex. $$$\sum_{i=0}^{n} i {n \choose i} x^{i}(m-x)^{n-i} = nm^{n-1}x$$$, where $$$x$$$ is the number of odd integers between $$$[1, m]$$$) This should give a nice clean $$$O(k)$$$ solution per testcase. (Don't do modulo division $$$k$$$ times as that would exceed TL)

»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

My worst performance in an edu round :/

»
8 days ago, # |
  Vote: I like it +4 Vote: I do not like it

C and D were too good for me. I cant solve too good questions.

»
8 days ago, # |
  Vote: I like it +1 Vote: I do not like it

the contest was of only 10 minutes for me :( , when I saw question C I closed tab

»
8 days ago, # |
  Vote: I like it +16 Vote: I do not like it

I Solve D in 20min, but could not solve C for the whole contest.

I think they should swap C and D, D is a too standard dp problem...

  • »
    »
    8 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I knew how to solve C two minutes after reading it, but did not find any idea how to solve D in less than O(n^2)

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

      uh, maybe you just forgot that you solution is not $$$O(n^2)$$$ but $$$O(n\sqrt{n})$$$

      let $$$dp(i,j)$$$ be the ways from $$$1$$$ to $$$i$$$ by using $$$j$$$ steps, you could find that $$$\sum\limits_{x = 1}^{k}x = \dfrac{k(k+1)}{2} \le n$$$, that means $$$k\le\sqrt{n}$$$, $$$k \not = n$$$, so your solution might be $$$O(nk) = O(n \sqrt{n})$$$.

      Initially, I was thinking about how to optimize my solution to $$$O(n \log n)$$$, but when I realize this fact, I started to write the $$$O(n\sqrt{n})$$$ solution.

      p.s. you can find that all $$$dp(...,j)$$$ are rely on $$$dp(...,j - 1)$$$, so you can use scrolling array to optimize the memory :)

      p.p.s : this is my simple implementation.

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

C is too hard for div. 2

»
8 days ago, # |
  Vote: I like it +68 Vote: I do not like it

Me After Solving A & B :')

»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

D is a great problem, I enjoyed it!

Happily I started solving it early enough

Although I wasted an attempt thinking 305*305 > 2*2e5... silly me

»
8 days ago, # |
  Vote: I like it +1 Vote: I do not like it

How to solve D?

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

    My solution:

    let's say that every time we add something, K increases by 1 and we have to add a number divisible by K next turn.

    at first notice that K can increase up to 2*(square root of N), since if it becomes a bigger number than this, the sum of added numbers to the coordinate will be >= 1 + 2 + ... + 2*(sqrt(n)) , which is bigger than N.

    So, for each number i from 1 to N and for all k <= x <= 2*sqrt(n) we can check if we can reach i when K will become x:

    for that for each k <= x <= k+ 2*sqrt(N) and for each 1 <= i <= n we will check how many sums of numbers from k to x can be equal i, this can be done by dp, let dp[i][x-k] be just that.

    Answer for each 1 <=i <=n is a sum of all dp[i][x-k] (k <= x <= k+ 2*sqrt(N) (mod 998244353).

»
8 days ago, # |
  Vote: I like it +10 Vote: I do not like it

It take multiple contest to regain rating and reach to certain point but just one ugly contests like this are enough to discard all your hardwork and progress . Super disappointed . Problem C sucks .

»
8 days ago, # |
  Vote: I like it +17 Vote: I do not like it

Problems were really good but the round was extremely unbalanced

»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

E seems like segment tree application,but how to get maximum sum of the subarray By segment tree?

  • »
    »
    8 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Store the prefix maximum, suffix maximum, total sum, and the maximum within the subarray for each node. Though you need to store more nodes than a normal segment tree

    • »
      »
      »
      8 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      That was what I thought,but I get stuck in tree update process, if k is zero, it means that at least half of the nodes of the tree need further update, and I thought it cost too much time

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

time limit for D should be higher

»
8 days ago, # |
  Vote: I like it +38 Vote: I do not like it

»
8 days ago, # |
  Vote: I like it +9 Vote: I do not like it

Anyone solved D with Python? I figured it out quickly but it seems O(N√N) is too much for Python. Good problem though.

  • »
    »
    8 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I didn't use Python, but I got 296ms with C++ (the limit is 2 seconds), so I very much doubt there is any language disadvantage.

    However, from what I gathered from other comments, filling up every element of every row in the DP would exceed the time limit (even in C++). Instead, you should keep track of what is the first non-zero column of each row (sum of each type of step so far), and don't waste time iterating over these known 0 values on the left.

    Also, it seems your verdict was actually memory limit exceeded. You only need to maintain two rows of DP, since each row depends only on the previous row (and the earlier elements of its own row).

    • »
      »
      »
      7 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks for your reply. I tried DP but it cost 40 seconds on case 200000 1 on my computer. Eventually, I found that it can pass the case using Pypy64 on CF.

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

        I rewrote your code in a way that is working: here.

        I don't know how I could write this in a pythonic way though.

»
8 days ago, # |
  Vote: I like it +10 Vote: I do not like it

Fool me once shame on you, lied to me two times I'm stupid

»
8 days ago, # |
  Vote: I like it +47 Vote: I do not like it

Why so many bad comments? I didn't have time to look at E and F at all, but problems A ~ D all had their own merits. It was a good Edu round as always.

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

    This tends to be the result of unbalanced problem sets rather than bad problems per se.

    In this case, if you were below the level required for problem C and/or D (an overwhelming majority of participants), then all that differentiates you is the combined time for A and B, which are trivial questions. Therefore the rankings from around 1500 below are more arbitrary than they should be, and people are upset that this adversely affects their ratings.

    I understand it perfectly well, although I'm quite sure that no problem setter ever sets out with the intention of upsetting people or to create an unbalanced problem set and it's also important to remember that.

»
8 days ago, # |
  Vote: I like it +20 Vote: I do not like it

The problems themselves were good individually, but I would really appreciate a problem between B and C. This C is probably like 1900 (judging by the number of solves during the contest), so we have like 700 gap between B and C.

  • »
    »
    8 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It was more like 2100 honestly. 1900 problems usually get 1500-2000 solves in a contest, not 1000

»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

The difficulty of the problems of this round was very unbalanced in my opinion. C and D is significantly harder than A and B :(( I can only complete problem A, B, and nearly done problem D (I'd be able to solve it if the contest was 5 minutes longer) :<<

»
8 days ago, # |
  Vote: I like it +29 Vote: I do not like it

Problem setters in a nutshell:

meme

»
8 days ago, # |
Rev. 2   Vote: I like it -14 Vote: I do not like it

I should skip edu rounds. :(

»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

with each educational round, I want to get out of codeforces and no longer comes lol)

»
8 days ago, # |
  Vote: I like it +56 Vote: I do not like it

in contest : oh i took so much time solving A & B , but its okay i have enough time to solve c

problem c :

baa

»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

how does the formula (n+2)/3 comes in problem A

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

    Try finding answers for n:(1 to 10) using pen and copy. You will get it.

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

    That's wrong for n = 1, right?

    • »
      »
      »
      8 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      The only corner case

    • »
      »
      »
      8 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yes. Usually for $$$n=1$$$ you will need to write something like:

      if(n==1) {
          printf("something\n");
          return;
      }
      
  • »
    »
    8 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    If we treat n is 1 as an exception (requires 2 moves for obvious reasons), then we can achieve any other number in ceil(n/3) operations*. ceil(n/3) = (n + 2)/3.

    *Proof: it is trivial that ceil(n/3) is a lower bound, since we can move at most 3 steps each time. Therefore it suffices to show that it is attainable. If n is a multiple of 3, then move entirely in blocks of 3. Otherwise, move in blocks of 3 except for one 2-move if n % 3 = 2 or two 2-moves if n % 3 = 1.

    • »
      »
      »
      8 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I wrote this function but got wrong answer

      int helper() {
        int n;
        cin >> n;
        if (n == 1)
          return 2;
        else
          return ceil(n * 1.0 / 3);
      }
      

      Can anyone please tell me .What is wrong in this. I have tested it locally with accepted solutions.It works fine.

      • »
        »
        »
        »
        8 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Got it now. Ceil return floating point number. I was printing ceil(n * 1.0 / 3).That's why got wrong answer

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

      For any number $$$n$$$ and any nonzero number $$$k$$$ this is true: $$$ceil(n÷k)=(n+k-1)÷k$$$.

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

    you have 4 cases in this problem

    1 : n % 3 == 0 then the optimal answer is using only 3s number of times = n / 3

    2: n % 3 == 2 then the optimal answer is using ( n / 3 ) 3s and just 1 two

    3: n % 3 == 1 the the optimal answer is removing 1 three from (n/3) 3s and use (2) 2s instead of it (3+1 = 4 = 2 + 2)

    4: if n == 1 so answer is 2

    so for case 2 and 3 the answer is n/3 + 1 , this formula = ceil( n / 3) (which include the answer for the first three cases)

  • »
    »
    8 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Actually you don't need this observation to solve this problem. Intuitively, it seems that for n <= 10, operations will be some strange. But for n > 10, we should extract 3 only until it is less than 10 then add the answer for remaining number. See my submission for more details: https://codeforces.com/contest/1716/submission/166940767

    • »
      »
      »
      8 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      The only 'strange' value is n = 1. Everything else conforms. You may not realise it but you're actually applying the same logic as everyone else for n > 10, and you've unnecessarily hand-solved for n <= 10. Obviously your method is perfectly valid, but it does nonetheless rely on the same critical observation of using 'mostly' 3-moves.

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

        using a number-theoretic approach, you could have used the fact that you can indeed construct any number $$$2$$$ and above with sums of $$$2$$$-s and $$$3$$$-s. (This is also provable by induction if any of you might wonder)

  • »
    »
    8 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Interesting, I came up with x/3 if x mod 3 is 0, x / 3 + 1 otherwise.

»
8 days ago, # |
  Vote: I like it +1 Vote: I do not like it

Educational Codeforces Round 133:last 13 minutes for me.:(

»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

in problem D, TLE on test 6, Submission link: https://codeforces.com/contest/1716/submission/167016276

since siz variable is <= 2*sqrt(n), size of freq would be O(N). Also for each i from 1 to N, i am iterating through 1 to siz. The time complexity would be O(N*sqrt(N)). Where am I wrong?

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

    Could just be strict time limits. siz can go up to 900 when n=200000, when only 650 is needed. Your loop also has a lot of modulo operations, which are known to slow runtime by several factors at times.

    • »
      »
      »
      8 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Even after changing it to 650, I am getting TLE. What changes should I make to get AC? submission link: https://codeforces.com/contest/1716/submission/167019605

      • »
        »
        »
        »
        8 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Your code is barely over 2s with C++20, I think with some optimizations it could probably pass. But the intended approach I believe is quite different from yours, which is able to skip a lot of states and doesn't need modulo. See the top scorer submissions for examples.

  • »
    »
    8 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You can run case"200000 1" locally.If it spends 3-8s,that's the reason if tight time limit. I'm in the same situation as you.167005425

»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

where can i find the link for editorials today's C was very hard i was not able to solve it can any one tell me the approach?

»
8 days ago, # |
  Vote: I like it +4 Vote: I do not like it

Only thing common between problem C and my crush is that they are both out of my league :)

»
8 days ago, # |
  Vote: I like it +18 Vote: I do not like it

After some more thinking about C I am somewhat disappointed.

Obviously this is an implementation problem with a lot of difficulties/traps for off-by-one errors, like every time we need to create several prefix sum/max arrays.

But here the definition "The robot can only move into a cell (i,j) if at least a[i][j] seconds have passed before the move." adds another level of trap, since that can be understood wrong. Now, an hour after the contest I am sure that we can enter cell[i][j] at a[i][j]+1 earliest, not at a[i][j].

Such inaccuracy in the text on an off-by-one problem is annoying.

»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

12k people looking at C & D be like: Its time for me to die

»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

What math knowledge was needed for F? It seemed pretty interesting.

»
8 days ago, # |
  Vote: I like it +1 Vote: I do not like it

The time limit is too tight! My O(n*sqrt(n)) method spends 6s locally in case"200000 1" and it gets TLE. 166994559 The implementation is a bit more complex than std but still O(n*sqrt(n)). Is anyone in the same situation as me?

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

    I got AC from an O(n*sqrt(n)) solution if you're interested

    166988623 (AC)

    166980959 (literally the exact same thing but TLE because mod operation is apparently a lot more costly than an if statement)

»
8 days ago, # |
  Vote: I like it +7 Vote: I do not like it

The contest got over for me in 8 minutes :")

»
8 days ago, # |
  Vote: I like it -15 Vote: I do not like it

You can now get the smallest counter example for your failing submissions on cfstress.com. Contest ID: 1716

Disclaimer: Content is behind a paywall. However, if you can't purchase a subscription, you can reply to my comment ( only till the next 24 hours ) with the problem index and link to your submission, and I'll share the failing test case.

  • »
    »
    8 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Please made cfstress free I can't afford it .

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

      Honestly just go watch Errichto's video on stress-testing and you don't have to pay for anything.

»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

I am just wondering Those who only know dp problem through Recursion . How to do d with recursive dp approach .

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

Who else also knew what to do for C, but either:

Didnt feel like impl, so went to D

Tried impl but realised it was impl heavy then went to D <- Me

Rage quit <- Also me

  • »
    »
    8 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Tried impl -> Error -> Tried impl -> Error -> Tried impl -> Error :)

»
8 days ago, # |
  Vote: I like it +118 Vote: I do not like it
»
8 days ago, # |
  Vote: I like it +51 Vote: I do not like it
»
8 days ago, # |
  Vote: I like it +14 Vote: I do not like it

I made a video Solutions for A-D in case people are interested.

»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

I like problem E. My approach comes from 1654F, which is also a nice problem.

»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

https://codeforces.com/contest/1706/problem/C

I found today's problem C like this problem. For some states we have two options, get one option in o(1) with pre-calculation and take the minimum of two options.

»
8 days ago, # |
  Vote: I like it +1 Vote: I do not like it

In problem C, how are present states of the clockwise and anti-clockwise traversals stored and updated as one incrementally moves along the zig-zag path?
I was able to get this far during the round, but still don't know how to implement it.

»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

tfw you solved D but not C

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

My O(n * sqrt(n)) dp solution for D got TLE during the contest, but the same code without any modification passes when I change the compiler from GNU C++17 to GNU C++20.

After some more submissions and testing, I've found out that GNU C++17 can run 2~3 times slower than GNU C++20. Is this something normal?

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

    It's not because of the C++ version. It's because you were using 32-bit C++17, and 64-bit C++20.

    It runs fine if you use 64-bit C++17: 167026428

    See: C++ 64-bit running almost 3s faster!

    • »
      »
      »
      8 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks! I shouldve care more about those things..

  • »
    »
    8 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yeah I was so shocked. I submitted SRSS_'s solution and it got TLE, but then I changed the compiler to the new version and it passed.

»
8 days ago, # |
  Vote: I like it +5 Vote: I do not like it

hi Everyone . Newbie question . Where can i find the editorial for this round

»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

I guess my submission for D is too slow just because of C#? I tried to optimised it as much as i can, should be $$$O(n\sqrt{n})$$$.

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

F is the same as 1278F.

»
7 days ago, # |
  Vote: I like it +20 Vote: I do not like it

Difficulty: C >> D > F

Everyone who knows Stirling number can work out F. It's almost the same as 932E/1278F.

But I'm stuck in C and haven't had a glimpse at F. Cheers! :(

C itself is excellent, but its position...

»
7 days ago, # |
  Vote: I like it +12 Vote: I do not like it

Me(Before the contest):Fine,let me try my best to become CM.Just 21 rating left.

C:Thinking what?

  • »
    »
    7 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    UPD:Finally I got +1 rating ! Yeah ! (But still 20 rating left . QAQ )

    Thanks to I_love_seele_forever for his 100+ successful hacking . ┏(≧▽≦)┛

    ( And sorry to these 100+ bro , too . )

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

    so strong. sro sro sro XING_ginkiha orz orz orz. Only 1120 to LGM, good luck!!

»
7 days ago, # |
  Vote: I like it 0 Vote: I do not like it

At least Speedforces gave me more time to relax
At least negative rating gave me more possibility for positive rating in next round
:(

»
7 days ago, # |
  Vote: I like it +26 Vote: I do not like it

D be like

»
7 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Educational Contest isn't so difficult until I participate in this contest :)

»
7 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Why so many downvotes? The problems themselves aren't bad, are they?

»
7 days ago, # |
  Vote: I like it +1 Vote: I do not like it

Educational Codeforces Round 133 (Rated for Div. 1)

»
7 days ago, # |
Rev. 2   Vote: I like it +39 Vote: I do not like it

Can you please provide sample explanations for all problems next time? The statements, especially C and F, are easy to misread.