Автор awoo, история, 2 года назад, По-русски

Привет, Codeforces!

В 04.08.2022 17:35 (Московское время) состоится Educational Codeforces Round 133 (рейтинговый для Div. 2).

Продолжается серия образовательных раундов в рамках инициативы Harbour.Space University! Подробности о сотрудничестве Harbour.Space University и Codeforces можно прочитать в посте.

Этот раунд будет рейтинговым для участников с рейтингом менее 2100. Соревнование будет проводиться по немного расширенным правилам ICPC. Штраф за каждую неверную посылку до посылки, являющейся полным решением, равен 10 минутам. После окончания раунда будет период времени длительностью в 12 часов, в течение которого вы можете попробовать взломать абсолютно любое решение (в том числе свое). Причем исходный код будет предоставлен не только для чтения, но и для копирования.

Вам будет предложено 6 или 7 задач на 2 часа. Мы надеемся, что вам они покажутся интересными.

Задачи вместе со мной придумывали и готовили Адилбек adedalic Далабаев, Владимир vovuh Петров, Иван BledDest Андросов и Максим Neon Мещеряков. Также большое спасибо Михаилу MikeMirzayanov Мирзаянову за системы Polygon и Codeforces.

Удачи в раунде! Успешных решений!

Также от наших друзей и партнёров из Harbour.Space есть сообщение для вас:

Harbour.Space

Программа Front-end Development от Harbour.Space — это место, где сталкиваются программирование и креативность. Получите стипендию до 50% и воспользуйтесь этой возможностью, чтобы учиться в Барселоне у отраслевых экспертов, пока вы сами становитесь таковым.

Программа в значительной степени ориентирована на развитие профессиональных навыков, необходимых для трудоустройства, и в то же время на развитие умения адаптироваться к быстро меняющимся технологиям.

Итак, давайте познакомимся с руководителями программы:

Harbour.Space

Hjörtur является генеральным директором 14islands, студии дизайна и развития из Стокгольма в Швеции и Флорипа в Бразилии. Он был соучредителем студии в 2011 году, и с тех пор они работали с такими компаниями, как Google, Adidas, Disney, Facebook, HBO, Shopify, Ericsson и многими инновационными стартапами в мире.

Marco Barbosa является управляющим директором 14islands, студии дизайна и развития из Стокгольма в Швеции и Флорипа в Бразилии. Их проекты получили множество наград, таких как FWA, Awwwards, CSS Design Awards и European Design Awards.

Подать заявку →

Удачи в раунде,

Harbour.Space University Team

UPD: Разбор опубликован

  • Проголосовать: нравится
  • -250
  • Проголосовать: не нравится

»
2 года назад, # |
Rev. 2   Проголосовать: нравится -9 Проголосовать: не нравится

Good luck everyone!! Hopefully everyone has fun!

»
2 года назад, # |
Rev. 2   Проголосовать: нравится -96 Проголосовать: не нравится

Stop downvoting my comment, please XD

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится +54 Проголосовать: не нравится

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

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится +36 Проголосовать: не нравится

    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

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится -42 Проголосовать: не нравится

    Oh I will downvote your comment buddy.

»
2 года назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится

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

»
2 года назад, # |
Rev. 2   Проголосовать: нравится +36 Проголосовать: не нравится

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

Edit: Sorry for jinxing it guys :(

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится +20 Проголосовать: не нравится

    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:)

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

Do u agree with this ?

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I am competing red coders in parallel universe.

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Hope i solve ABC

»
2 года назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

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

»
2 года назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится

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

»
2 года назад, # |
  Проголосовать: нравится -14 Проголосовать: не нравится

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

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Hope everyone has good luck.

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
2 года назад, # |
  Проголосовать: нравится +16 Проголосовать: не нравится

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

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
2 года назад, # |
  Проголосовать: нравится -8 Проголосовать: не нравится

Hope, I will become Expert Again today !!!

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
2 года назад, # |
  Проголосовать: нравится +22 Проголосовать: не нравится

seems like B and C difficulty difference is high

»
2 года назад, # |
  Проголосовать: нравится +33 Проголосовать: не нравится
Well :')
»
2 года назад, # |
  Проголосовать: нравится +43 Проголосовать: не нравится

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

»
2 года назад, # |
  Проголосовать: нравится +19 Проголосовать: не нравится

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

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

»
2 года назад, # |
Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

Toughest educational round ever ?? :)

»
2 года назад, # |
  Проголосовать: нравится +28 Проголосовать: не нравится

Problem C is much more difficult than normal C problems

»
2 года назад, # |
Rev. 2   Проголосовать: нравится +13 Проголосовать: не нравится

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

»
2 года назад, # |
  Проголосовать: нравится +18 Проголосовать: не нравится

Worst Edu round ever .

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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)

»
2 года назад, # |
  Проголосовать: нравится +44 Проголосовать: не нравится
meme
»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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 :(

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Такого несбалансированного раунда я не видел никогда. D и C — это очень сложные задачи, B и А слишком просты. Я думаю D и C будут сложности 2000+, а A и B 800 или 900. Это очень плохо. Автору дизлайк.

»
2 года назад, # |
Rev. 2   Проголосовать: нравится +23 Проголосовать: не нравится

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.

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

»
2 года назад, # |
  Проголосовать: нравится +32 Проголосовать: не нравится

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

»
2 года назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

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

»
2 года назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

What are c and d of this contest.

»
2 года назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

What's speedforces?

  • »
    »
    2 года назад, # ^ |
    Rev. 2   Проголосовать: нравится +11 Проголосовать: не нравится

    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.

»
2 года назад, # |
Rev. 2   Проголосовать: нравится +2 Проголосовать: не нравится

speedforces

»
2 года назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

Meme 1

  • B AC > 12000
  • C AC < 1000

Meme 2

  • D easier than C.

Meme 3

  • F easier than B.
»
2 года назад, # |
  Проголосовать: нравится -12 Проголосовать: не нравится

It is really a bad contest :/

»
2 года назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

SpeedforcesAB

»
2 года назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

disgusting speedforces :(

»
2 года назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится

Not SPEEDFORCES, but HACKFORCES!!!

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

»
2 года назад, # |
Rev. 2   Проголосовать: нравится +4 Проголосовать: не нравится

.

»
2 года назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

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

I suck at iterative dp.

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Yeah, I tried dp but it was too slow.

  • »
    »
    2 года назад, # ^ |
    Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

    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.

    • »
      »
      »
      2 года назад, # ^ |
        Проголосовать: нравится +1 Проголосовать: не нравится

      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.

  • »
    »
    2 года назад, # ^ |
    Rev. 7   Проголосовать: нравится +20 Проголосовать: не нравится

    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

    • »
      »
      »
      2 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Meme
    • »
      »
      »
      2 года назад, # ^ |
      Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

      "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

      • »
        »
        »
        »
        2 года назад, # ^ |
        Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

        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

»
2 года назад, # |
  Проголосовать: нравится +18 Проголосовать: не нравится

i hate edu rounds always the same fucking story.

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    bro im so agree with you

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится +4 Проголосовать: не нравится

    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

    • »
      »
      »
      2 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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.

      • »
        »
        »
        »
        2 года назад, # ^ |
        Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

        If some other people can do it,why don't you? The Edu rounds will be always the same,if you improve your knowledge you are gonna say i like Edu Rounds haha. A bad contest is that one too easy or that one with classical problems or an unrated one, but Edu's are Ok

»
2 года назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

How to solve $$$C$$$?

  • »
    »
    2 года назад, # ^ |
    Rev. 3   Проголосовать: нравится +3 Проголосовать: не нравится

    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?

    • »
      »
      »
      2 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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

»
2 года назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

How to do D?

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

    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.

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится +20 Проголосовать: не нравится

    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.

    • »
      »
      »
      2 года назад, # ^ |
      Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

      Igor_Parfenov,can you please tell the 2nd term of DP recurrence written below i.e dp[i][j-i] :

      dp[i][j] = dp[i-1][j-i] + dp[i][j-i]; I somehow got the idea from steveonalex comment above but can you please tell me the intuition of the 2nd term it just isn't hitting me after so much attempts. In contest how we will get the 2nd term so fast , I have seen many submissions and they have written the term so easily but the biggest challenge for me is to get the 2nd term in above recurrence relation. Can you please tell the intuition.

      • »
        »
        »
        »
        2 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        $$$dp[i][j] = dp[i - 1][j - i] + dp[i - 1][j - 2i] + dp[i - 1][j - 3i] + \dots$$$

        $$$dp[i][j - i] = dp[i - 1][j - i - i] + dp[i - 1][j - i - 2i] + dp[i - 1][j - i - 3i] + \dots$$$

        The second sum is the same in first, except it doesn't contain $$$dp[i - 1][j - i]$$$. I don't know, how to explain, how to get to it during contest. I drawed a picture of array, looked, sum of which cells form the given cell, and just noticed it.

      • »
        »
        »
        »
        2 года назад, # ^ |
        Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

        I got you bro! Image. How did I found the formula? Well, I just derive the inefficient formula, then take a second look at the formula, then found out that you don't even have to calculate dp[i−1][j−2i] + dp[i−1][j−3i] + ..., since that is dp[i][j — i]. I guess if you are good enough at math, or if you have done way too much dp problem, you could spot that easily.

  • »
    »
    2 года назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    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).

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    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

»
2 года назад, # |
Rev. 3   Проголосовать: нравится +114 Проголосовать: не нравится

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!

»
2 года назад, # |
  Проголосовать: нравится -11 Проголосовать: не нравится

speedforces

»
2 года назад, # |
  Проголосовать: нравится -16 Проголосовать: не нравится

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.

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

D was stars and bars ? ??

  • »
    »
    2 года назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    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)).

»
2 года назад, # |
  Проголосовать: нравится -16 Проголосовать: не нравится

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

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How to solve C and D?

»
2 года назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

Контест для меня был сложным, но задачи очень интересные, за что авторам большое спасибо, жду разбора!

»
2 года назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

This educational contest seems too spartan for me...

»
2 года назад, # |
  Проголосовать: нравится -59 Проголосовать: не нравится

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

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится -27 Проголосовать: не нравится

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

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Speedforces :)

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

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

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    It can be zigzag, then a big turn.

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

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

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    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.

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

»
2 года назад, # |
  Проголосовать: нравится +149 Проголосовать: не нравится

wow

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Any pointers for D?

My potato brain can only think of the most naive solution

»
2 года назад, # |
  Проголосовать: нравится +75 Проголосовать: не нравится

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.

»
2 года назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

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.

»
2 года назад, # |
  Проголосовать: нравится +83 Проголосовать: не нравится

I think E is much harder than F.

»
2 года назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

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).

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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).

»
2 года назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

[Deleted]

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

»
2 года назад, # |
Rev. 6   Проголосовать: нравится +11 Проголосовать: не нравится

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.

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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?

»
2 года назад, # |
  Проголосовать: нравится +17 Проголосовать: не нравится

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

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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 ?

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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
»
2 года назад, # |
  Проголосовать: нравится +14 Проголосовать: не нравится

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

»
2 года назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

Literally the worst Edu round I ever gave :|

»
2 года назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

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

Am I the only one in this case ?

»
2 года назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

Hardforces

»
2 года назад, # |
  Проголосовать: нравится +56 Проголосовать: не нравится

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

»
2 года назад, # |
Rev. 4   Проголосовать: нравится +69 Проголосовать: не нравится

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.

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится +6 Проголосовать: не нравится

    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

    • »
      »
      »
      2 года назад, # ^ |
        Проголосовать: нравится +6 Проголосовать: не нравится

      Tight time limits. I got TLE for three times.

    • »
      »
      »
      2 года назад, # ^ |
        Проголосовать: нравится +17 Проголосовать: не нравится

      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.

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

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

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится +10 Проголосовать: не нравится
  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      2 года назад, # ^ |
      Rev. 2   Проголосовать: нравится +8 Проголосовать: не нравится

      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)

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

My worst performance in an edu round :/

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

DynamicForces

»
2 года назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

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

»
2 года назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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

»
2 года назад, # |
  Проголосовать: нравится +16 Проголосовать: не нравится

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...

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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)

    • »
      »
      »
      2 года назад, # ^ |
      Rev. 6   Проголосовать: нравится +1 Проголосовать: не нравится

      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.

»
2 года назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

C is too hard for div. 2

»
2 года назад, # |
  Проголосовать: нравится +68 Проголосовать: не нравится

Me After Solving A & B :')

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
2 года назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

How to solve D?

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    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).

»
2 года назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

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 .

»
2 года назад, # |
  Проголосовать: нравится +17 Проголосовать: не нравится

Problems were really good but the round was extremely unbalanced

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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

    • »
      »
      »
      2 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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

»
2 года назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

time limit for D should be higher

»
2 года назад, # |
  Проголосовать: нравится +38 Проголосовать: не нравится

»
2 года назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

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

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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).

    • »
      »
      »
      2 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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.

»
2 года назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

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

»
2 года назад, # |
  Проголосовать: нравится +47 Проголосовать: не нравится

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.

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится +43 Проголосовать: не нравится

    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.

»
2 года назад, # |
  Проголосовать: нравится +20 Проголосовать: не нравится

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.

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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) :<<

»
2 года назад, # |
  Проголосовать: нравится +29 Проголосовать: не нравится

Problem setters in a nutshell:

meme

»
2 года назад, # |
Rev. 2   Проголосовать: нравится -14 Проголосовать: не нравится

I should skip edu rounds. :(

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
2 года назад, # |
  Проголосовать: нравится +56 Проголосовать: не нравится

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

problem c :

baa

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

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

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится +4 Проголосовать: не нравится

    That's wrong for n = 1, right?

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.net/contest/1716/submission/166940767

    • »
      »
      »
      2 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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.

      • »
        »
        »
        »
        2 года назад, # ^ |
        Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

        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)

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

»
2 года назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

in problem D, TLE on test 6, Submission link: https://codeforces.net/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?

  • »
    »
    2 года назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    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.

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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?

»
2 года назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

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

»
2 года назад, # |
  Проголосовать: нравится +18 Проголосовать: не нравится

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.

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
2 года назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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?

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

»
2 года назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится

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

»
2 года назад, # |
  Проголосовать: нравится -15 Проголосовать: не нравится

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.

»
2 года назад, # |
Rev. 3   Проголосовать: нравится +6 Проголосовать: не нравится

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

»
2 года назад, # |
  Проголосовать: нравится +118 Проголосовать: не нравится
»
2 года назад, # |
  Проголосовать: нравится +51 Проголосовать: не нравится
»
2 года назад, # |
  Проголосовать: нравится +14 Проголосовать: не нравится

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

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

https://codeforces.net/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.

»
2 года назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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.

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

tfw you solved D but not C

»
2 года назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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?

»
2 года назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

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

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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})$$$.

»
2 года назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится

F is the same as 1278F.

»
2 года назад, # |
  Проголосовать: нравится +20 Проголосовать: не нравится

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...

»
2 года назад, # |
  Проголосовать: нравится +12 Проголосовать: не нравится

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

C:Thinking what?

»
2 года назад, # |
  Проголосовать: нравится +26 Проголосовать: не нравится

D be like

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
2 года назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Educational Codeforces Round 133 (Rated for Div. 1)

»
2 года назад, # |
Rev. 2   Проголосовать: нравится +39 Проголосовать: не нравится

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

»
2 года назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

Yeah, they are good problems but i'm retired.

problem C is easy to think but not easy to write(maybe tedious), so i think it's the reason that this blogpost get so many downvotes.(There is almost no difference between participants at different levels, so downvotes are justified)

problem E is a bit difficult but i can solve it myself(i'm retired) i think my solution to E is unique.(maybe i gave a NAIVE solution?) share to everyone:https://codeforces.net/contest/1716/submission/167000638

i hope you can learn some methods in this code(i think it's interesting)

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can anyone tell me what's wrong here?
when I submitted the same code on GNU C++17, it showed a runtime error but was accepted when submitted on GNU C++20 during the contest.
runtime error: 166964477
accepted: 166971156

  • »
    »
    2 года назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    idk why did it get accepted, but i can easily explain why it RTEd — on the nth iteration of your cycle you swap v[n — 1] and v[n], which is out of bounds, you should have do smtg like swap(v[i], v[(i + 1) % n])

»
2 года назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

I failed to solve D because I didn't clear the scroll array 167007748 . This means I will drop nearly 100rating but I believe I can get it back in the next DIV2 game.

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Is it possible to solve D with generating function?

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    Yes you can by changing times into plus and exp and ln. But you don't need to solve it in such a difficult way.

»
2 года назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

Who know when rating change

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I managed to find a solution for C but I was thinking if there was a DP solution. I couldn't find anything about it because I couldn't find a clear base case so did anyone find a DP solution even if it doesn't work on the problem constraints? Thanks in advance

»
2 года назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

Start system testing

»
2 года назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

When rating will be updated ?

»
2 года назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

so where is my rating???

»
2 года назад, # |
Rev. 2   Проголосовать: нравится +41 Проголосовать: не нравится

My code for problem D had the correct time complexity, but in the final system test, it exceeded the time limit. But submitting the same code again gets an Accept result. I didn't even realize when I was racing that my code was running out of time. That's too bad! Can the system re-evaluate my code?

And my submission number is 166977295.

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится +19 Проголосовать: не нравится

    I think it's important to give code that runs out of time in the final system test. In many cases, due to the fluctuation of the evaluation speed, the code with correct time complexity cannot get the accept result.

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится +13 Проголосовать: не нравится

    What a pity!

»
2 года назад, # |
Rev. 4   Проголосовать: нравится +29 Проголосовать: не нравится

Hi MikeMirzayanov BledDest awoo, My submission 166991524 for problem D got TLE during the final system test while the exact same code submission 167084670 passes after the system test. Please do the needful . Thank YOu

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится +20 Проголосовать: не нравится

    I have a friend who had the same problem. It's really a pity that you can't get the result of Accept because of this!

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится +14 Проголосовать: не нравится

    I also faced the same problem, the Same submission is passed later on.

    I explicitly checked that in the pretests 20000 1 passed and now while sys testing it failed.

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    I'm in the same boat. Submission 167002114 was my final contest submission. It was marked "Accepted" by the time the contest ended and was still marked "Accepted" by the time the hacking phase finished. However, now it is now TLE.

    I submitted the exact same code in Submission 167128290 after the contest and I got AC.

»
2 года назад, # |
  Проголосовать: нравится +25 Проголосовать: не нравится

My code for problem D got TLE in the system test(166974979),but I submitted the same code after system testing,it ACed(167087492).Can someone retest my code?Thanks!

»
2 года назад, # |
  Проголосовать: нравится +36 Проголосовать: не нравится

Hi! I have same problem as a lot of users. My code on D got TL on system tests (https://codeforces.net/contest/1716/submission/167004235), but then I tried to send it again (with adding enters in code ^_^, since codeforces do not able you to send the same code twice) and on all submitions i got AC ( https://codeforces.net/contest/1716/submission/167088073 , https://codeforces.net/contest/1716/submission/167088034 , https://codeforces.net/contest/1716/submission/167087989 , https://codeforces.net/contest/1716/submission/167087971 , https://codeforces.net/contest/1716/submission/167087910 , https://codeforces.net/contest/1716/submission/167087871 and all other submitions see in my profile). I think that's really unfair.

»
2 года назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится

Why rating change late?????????????

»
2 года назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится

Still waiting for rating change.

»
2 года назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

166947093 this submission get accepted during test but shows runtime error in system testing at test 2. 167102391 submitted the same solution which is accepted. Now showing heavy minus in rating.

»
2 года назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

Still waiting for become master...

»
2 года назад, # |
  Проголосовать: нравится +19 Проголосовать: не нравится

Still wating for become master...

»
2 года назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

加油

»
2 года назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Some codes which got Accepted for problem D in contest are getting TLE now on test 6? Why?

»
2 года назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

Hello I am cool-dude. I have just received a warning mail about rules violation stating that my solutions for problems 1716A and 1716B match with those of joebor. I deny using any unethical means of submission during the contest and also having any source of contact with joebor hence I hereby demand that any accusation against me be revoked. I suspect that as I have been using a public IDE my program was susceptible to being copied by other users of the ide. It is also evident that I have made my submissions prior to joebor. Kindly consider my request and my contest rank for evaluation.

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
2 года назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

stupid contest

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Codeforces Language Picker -- chrome extension to fix codeforces language picker.

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Codeforces Language Picker -- chrome extension to fix codeforces language picker.

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Help in problem c