Блог пользователя shishyando

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

Привет, Codeforces!

Мы приглашаем вас принять участие в контесте, который пройдет в 19.05.2022 17:35 (Московское время). У вас будет 2 часа на решение 8 задач. Раунд рейтинговый для участников обоих дивизионов.

Я бы хотел поблагодарить тех, благодаря кому этот раунд состоится:

Также мы бы хотели поблагодарить компанию NEAR, при поддержке которой проходит этот раунд. Компанию основал бывший участник соревнований AlexSkidanov. Также в команде, разрабатывающей NEAR, работают многие известные участники сообщества, например, дважды чемпион мира ICPC eatmore и победитель GCJ и TCO Egor.

  • В раунде предусмотрены призы в NEAR коинах для участников, которые займут первые 255 мест. Победитель раунда получит Ⓝ128, участники на втором и третьем месте по Ⓝ64, участники на следующих четырех позициях по Ⓝ32, и так далее.

  • Кроме того мы рады сообщить, что достоверные участники (уже участвовавшие хотя бы 5 рейтинговых раундах), занявшие одно из первых 255 мест, также получат приглашения в проект CrowdForces! Этот проект запущен на NEAR уже как полгода и позволяет участникам получать Ⓝ за решение задач на CrowdScript с разных платформ: Codeforces, SPOJ, E-Olymp, AtCoder, UVa Online Judge.

Именно с этим проектом связаны легенды в условиях на русском языке. Они идут курсивом в первом абзаце каждой задачи.

Разбалловка задач:

500750125015001750200025003250

Мы надеемся, что вам понравятся задачи! Удачи на контесте!

Разбор: ссылка

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

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

As a tester, I really loved the round. One of my favorites in recent years, I'd vote at least two tasks for candidates to 'best of 2022'. Please participate!

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

    As per history of codeforces, whenever a tester says the round will be very good, the contest turns out to be bad.

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

    fucking clickbait

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

    I'm sorry that these two tasks had to be replaced, I hope that we'll see them in the future.

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

      Don't get me wrong, the problems were ok and interesting, but Kacper is always fascinated by so-so problems.

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

        You know people don't have to like the same thing, right? You're around 3400, I'm around 2400 — we're not the same xD

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

          Yeah, ofc. I can be mistaken too, so I'm all ears, which problems deserve to be the best ones in 2022 and why?

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

            BTW. I tested quite a long time ago, and have learnt only recently about some issues like extremely weak pretests in C or short contest duration. I wouldn't support any of these decisions...

            In my opinion, D is an exceptionally good easy problem that has everything: nice, natural and simple statement which almost makes you wonder why is this not a well-known task. The solution was far from obvious to me, yet very simple and elegant. Although I guess perception changes if someone is as high rated as you, Mateusz. Most people wouldn't nominate easy problems to 'best of ...' because 'it is all obvious anyway'. But overall I don't remember any task of similar difficulty or easier having a 'wow-factor' for me in 2022. Simple and good algorithm problems are so rare nowadays...

            My other favourite task was G. I just loved solving this problem, as I was unravelling new layers of inference-based observations without doing bullshit guessing like "oh I can't prove this but it has to work this way, otherwise unsolvable". Plus, of course, somewhat natural statement about algorithms and reduction to something standard in the end. You know, I like when the task is not just about some formulas...

            I tried to give some justification. Of course you may not agree with it. Oh, and also, it's mid-May so it's comparatively easier to be best in 2022 :)

            I hope you've at least somewhat enjoyed the round despite my tiny bit of clickbait

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

              But I think the solution for problem D is very obvious if you are familiar with the thought of splitting answer into each position's contribution.

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

          Then I'll give my opinion as someone much closer to 2400 than 3400: among A-G, I liked D but it's not like super amazing. In CEF, I mostly put effort into not messing up my implementation since I immediately knew roughly what I needed.

          G is a combo of avoiding mistakes in reading, reducing GCD to the simplest possible form (the construction) and avoiding mistakes in typing since the construction says to find matching. I suppose the construction part's nice, at least it doesn't feel like divine revelation like most constructions, but I'm just not a huge fan of construction problems in general.

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

            G is the type of problem I hate the most. It teases your appetite by giving a problem which in general is NP-complete but you're told it can be solved due to some special property of the sets involved, but then it turns out thats it's the dullest property possible. Moreover if you look at those gcd sequences they feel soooo random the property in question just has to be some nonsense like

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

              what is the general NP-complete version of G? (the only thing i can think of is removing the $$$\leq m$$$ constraint on the output, but that's certainly not NP-complete.)

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

    Maybe one task is best of 2011.

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

    This comment didn't age well.

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

I think having 2 hours and 15 minutes in a 8-problem contest is better.

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

I hope the contest is good

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

As a tester, I missed the final rated round of my teenage.

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

I hope the problems are interesting and easy. Good luck for my first contest , and for everyone too!

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

I don't think 2 hours is really enough to solve 8 problems.Maybe 2 and a quarter or two and a half is better?

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

    Don't judge without seeing the problems. Coordinators,testers,setters know the problems and according to that they would have set the duration. So probably 2 hours would be appropriate.

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

    It's funny that such a things are proposed by a participants who anyway will not solve all of them :)

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

    Thanks for being considerate of the very small fraction of the LGMs who has the ability to AK the round, but may get into time trouble.

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

      Well, AKing and LGMs are one thing but even for me 8 problems in 2 hours usually means a bad contest experience. Yeah, I won't solve them all but the experience still generally looks like "implement, implement, implement, implement, implement, contest ends" rather than "implement, think, implement, think, implement" in a round with less problems.

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

    don't worry for tourist.

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

    Agreed

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

Удачи всем вы все всё сможете но я постараюсь решить хотя бы задачи A и B.

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

As a tester, I want to say participate in this round!

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

Earlier there was a separate Div1 and Div2 round, but now it's a combined round. What was the reason?

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

As a tester, I'm a bit jealous that you all get to compete for prizes lol

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

Why is it combined?

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

As a tester, I get to mention _Vanilla_ for no reason.

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

I have also registered to round with id 1683 (that is, round #792 div 1), while it was visible. Can't wait to see where I will get redirected when the contest starts.

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

NEAR coins in this round worth a lot less than NEAR coins in that previous round. :(

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

Can't wait for the contest. Hopefuly I'll be able to solve at least 2 questions.

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

looking forward strong pretest !

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

Good luck!

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

You will have 2 hours to solve 8 problems.

Gonna have to dance with pen now

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

I really love the coins distribution.

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

I am not able to register now

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

Hopefully, I pass system test for all questions for which my pretests are passed. Last two times it didn't :(

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

operationforces

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

Weak pretests for C I guess. My $$$O(N^3)$$$ passed lol.

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

Problem H was here. Unfortunately, I wasted most of my time on the contest on H because the solutions posted there are wrong.

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

tourist gets back to rank 1 through 1 hack!

»
2 года назад, # |
  Проголосовать: нравится +183 Проголосовать: не нравится
Trying to hack B
»
2 года назад, # |
  Проголосовать: нравится +31 Проголосовать: не нравится

Tougher B: Link

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

greedy forces!

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

Most of the problems were nice, I liked the contest as a whole. Though unfortunately F just felt like tedious implementation (30+ mins) with not much thinking involved.

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

some one pls tell that how to solve C :*

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

    find any wrong positions of any two elements and replace their columns then check your solution is correct or not. wrong positions means that an array element such that it doesn't exist in allowed position in a sorted array .

    for example : in this array [1,2,3,3,4], the allowed positions for 3 is 3 or 4 only and for 2 is 2 only .

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

    Find the first index i such that a[i] > a[i+1]. Now, all elements at index less than equal to i will be sorted, so you can't swap a[i+1] with some a[j], j < i. Also a[i] can't be swapped with a[j], j < i. So you can only swap a[i] with some a[j], j > i. So find j such that a[j] <= a[i+1] and (j+1 == n || a[j+1] >= a[i]). Swap columns i and j

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

Hmm, where did I see that plot twist happen before?

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

Can anyone tell me whats wrong in my D solution here

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

    Consider this test

    1
    3 1
    2 1 1
    

    your solution says that the answer is 4, but you can achieve a score of 3 by jumping over the third trap.

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

      OMG, What are the odds that my tool (which uses a random seed) generated the same testcase Ticket 7275 as you (and we replied within seconds of each other xD).

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

        Do you yourself create test cases by stress testing after every contest on your website or is it created automatically?

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

          It's semi automatic. (There's some definitely some code involved, but I've created library, utility functions and macros that help me to create generators (and reuse existing ones) in an efficient manner.

          The customization part is automatic though.

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

    Failing testcase: Ticket 7275

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

Amazing contest, I love it!

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

I think you should use Bold words to tell us following operation exactly once in problem C, It wasted me 1h!

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

C was dirty case-work. and the mex=0 case of E(WA pretest 6) should have been in the samples.

However, D and F were cool.

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

    how was C casework?

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

    It took me forever to figure out WA pretest 6 lol.

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

    On the topic of samples, the samples of D are so weak that if you mistakenly sort by $$$a_i - i$$$ (or even just $$$a_i$$$) instead of $$$a_i + i$$$ you will still pass the samples.

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

      Why exactly is that bad? If someone was guessing the current samples would make it harder to guess.

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

    For F I have the same opinion with you, But does the person who didn't put case n = 1 and m = 1 in this problem have the permission to say this thing?

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

      I dont think they are comparable. that would be like that problem A didnt have a 2-digit sample lol.

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

    My solution to C require no casework (though I don't know if I will FST)

    Sort each row and check if there are at most 2 columns that differ. And if there are such 2 columns we try swapping them.

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

      I did the same. Find the leftmost and the rightmost columns that doesn't match and swap them. Not certainly sure how to prove the correctness. Update: My solution FST'd

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

    dirty case-work, AND the pretests were among the weakest in recent history. In a problem with multiple test cases per input, so there is no excuse for this. Disgusting.

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

    what dirty case work? just sort the columns lexicographically and find the number of non-equal columns what kind of case work is that?

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

Is D a DP solution?? if yes then how do i optimise it from O(n^2) complexity

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

Made a clutch solution on E at 1:59:46 and it passed pretests. :)

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

I feel like F was slightly easier than D,E. At least D required an idea, F was just juggling claims about segments.

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

    For me both D and E were instant, F required some thinking. Should have thought a bit more though, almost TLEd in system tests, with 1949ms / 2000ms >_>

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

      Seems like you overcomplicated it. Check my solution, it just looks at all pairs of indices with the same value (efficiently, not bruteforce) and gets the best left endpoint for each right endpoint from there.

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

spent too much time on different DP strategies for D but then realized it can be done by greedy

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

B is not a programming problem.

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

    Based on the previous comments of yours, I feel like ranting about math problems in a contest is a recurring theme of yours lol.

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

      That's actually my core competence ;)

      Edit: lol, I was fairly close

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

    That's how I felt, too :)

    After wasting 20+ minutes on paper trying to do math and coming up empty handed, I started trying to guess the formula. Guess I should do less math and more guessing from now on...

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

is E solvable without implicit treap? my idea was to find answer for mex(0), mex(1), ..., mex(n). each would take log^x (n) time. for each mex(i), you do the following:

  • if you have i currently in the array, decrease it's frequency by one, otherwise find the element with smallest frequency and change it to i

  • (update the change frequency in the implicit treap, erase the previous frequency and insert the new one, if it is > 0)

  • now you have k-i-1 operations left, you use them to decrease DIFF as much as possible. you decrease DIFF as much as possible by changing the numbers with smallest frequencies to the number with biggest frequency until you can. you don't have to actually change them, just find how many of the smallest frequencies sum up to <= k. that's doable with binary search in implicit treap with sum queries.

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

    You can do it with two segment trees, one for sum and one for count of distinct numbers.

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

    I binary search the largest possible MEX, then remove group of numbers more than MEX greedily.

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

      thats sounds easier, didn't know you have to maximize mex

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

        If you change a number to increase the MEX it will either won't change the answer or increase it, but never decrease it. So, maximing the MEX is a greedy choice

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

      I have the same idea, but I found the largest MEX greedily.

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

Please give a hint about D

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

    First drop the first k traps and then start from k + 1 and check if there is a better drop than the worst drop from the previous k drops.

    I used a Heap for this.

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

Hello, How to solve C? I understood the statement and I can't implement the solution. any help?

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

    find any wrong positions of any two elements and replace their columns then check your solution is correct or not. wrong positions means that an array element such that it doesn't exist in allowed position in a sorted array .

    for example : in this array [1,2,3,3,4], the allowed positions for 3 is 3 or 4 only and for 2 is 2 only .

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

    You can refer to mine. 157703045 I just checked if there exists any such row where the (j+1)th element is smaller than the jth element, if it exists then I simply marked that row and and searched for two indices in that particular row where the numbers should be swapped. Then simply for that two indices i swapped the values for every row. After that simply traversed the matrix and checked whether the conditions are violated or not. If any such case found then print -1. else print those two indices.

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

    First of all if $$$m = 1$$$, then the answer is $$$1$$$ $$$1$$$ otherwise :

    We consider a number in an array $$$bad$$$ if it is not in it's correct place in sorted form of the main array, So if the number of $$$bad$$$ numbers in any row was more than $$$2$$$ then the answer is $$$-1$$$, In other cases, Store the index of one of the rows that has exactly $$$2$$$ $$$bad$$$ numbers, then find the indices of two $$$bad$$$ numbers in that row, For example they're at indices $$$i$$$ and $$$j$$$, then swap all the pairs at indices $$$i$$$ and $$$j$$$ for each row or better to say is swap column's $$$i$$$ and $$$j$$$, Then after all if you found any row unsorted, the answer will be $$$-1$$$ otherwise the answer will be $$$i$$$ and $$$j$$$.
    157737517

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

How to solve E?

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

I hope there won't be 700 systests in H which will disappear later like some time ago.

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

    26 were enough :P

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

      Yeah, during the contest my solution passed them twice (with different parameters), but after the contest it failed (I guess due to time-dependent seed).

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

FSTforces. Wait and see how many people will FST on C.(including me :( )

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

this was the best speed forces. what is happening there?

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

Why is pretests for C so weak?!

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

    How do you know it as of now? AFAIK, system testing has not yet begun.

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

      Well, I discovered an error in my program after I first passed these tests, and I fixed it, thinking it would be fine now and locked the problem, then I got myself hacked with another test...

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

      Here's a test that I and probably some other ones will FST on:(

      1
      1 3
      2 1 1
      

      I thought we just need to try swapping columns with $$$a_{i,j}<a_{i,j-1}$$$.

      FST for me again!

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

nice round hope not to turn on depression mode after system tests

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

Question B appeared on codeforces not long ago

https://codeforces.me/gym/103415/problem/H

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

    But in this round there was a constrain , i.e a<b<c. Which makes the problem in this contest easier

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

nice problems...In D I sorted in non-increasing order as {value-(n-index),index} then took the first k pairs and set their indexes as the traps to be jumped over,I thought this would be optimal and it passed, but any proof why it's optimal??

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

    Consider the amount of damage you prevent by picking each trap. Say the first trap you pick is index $$$i$$$. You save $$$a_i - (n - i)$$$ damage because you no longer take $$$a_i$$$ damage from the $$$i$$$th trap, but all $$$n - i$$$ traps after index $$$i$$$ take bonus damage. After picking the first trap, ALL remaining values increase by $$$1$$$. Traps before index $$$i$$$ increase by $$$1$$$ because there is one less trap after it that takes bonus damage. Traps after index $$$i$$$ also increase by $$$1$$$ because you save the $$$+1$$$ bonus damage dealt by index $$$i$$$ by choosing that trap. So all values change by the same amount, and it is correct to still sort by $$$a_i - (n - i)$$$ for future decisions.

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

    There is an easy proof by changing the problem to an equivalent one.

    Note that we always jump exactly k times. Change the problem, such that we DO take the bonus damage when jumping over a trap (we still don't take the trap's base damage). Note that the answer to the changed problem is always $$$k (k - 1) / 2$$$ larger than the answer to the original, so subtract this from your answer to get an equivalent problem.

    But now, the damage we avoid by jumping over trap $$$i$$$ (zero-indexed) with damage $$$a[i]$$$ is exactly $$$a[i] - (n - 1 - i)$$$, as desired.

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

FSTForces..

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

So many system test failure in C

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

Wow very strong pretests. Good bye codeforces shifting to Atcoder and Codechef

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

I only solved A, I hope next contest I will solve 3 problems.

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

When the test-case setters confuse a Codeforces Div. (1 + 2) with a TopCoder SRM.

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

Thank's for this brilliant pretests

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

Poor pretest hurts more than wa, thanks to problem setters for giving me a bad day

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

The wonderful pretest made me go through the worse 520.

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

Thanks for the amazing pretests :(

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

What is there in D's Test Case 77?
FSTs in both C and D, hope the edge cases that I've apparently missed are outrageous enough...

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

    Test case #77 for D:

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

    I also got WA 77. The mistake I made in my code is that k * (k-1) / 2 in line 64 should be i * (i-1) / 2. How did it passed the pretest??

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

      My mistake was this simple single line condition that was unnecessary ig:
      if((*ptr).first >= 0)

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

f*** the pretests of C

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

Other than problem C, I liked this round a lot. Problems D, F and G were nice, and for an easy problem, B was very good.

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

Finally algo tasks and systests, thank you!

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

Weak pretests hurt :'(

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

PRETESTS SUCKS Especially for D, how can wrong code even pass systests? (If test case 77 wasn't added by the hack, many wrong code might be passed!)

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

The problems were not bad, but the pretests were extremely weak. How did my D pass the pretest even though I mistook i * (i-1) / 2 for k * (k-1) / 2?

After getting -200 delta, now I have to go back to candidate master and participate Div.2-only rounds again.

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

As a tester, you all guys did shitty job

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

 pretest

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

Can somebody give me any stress test for E?

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

Thank you for the contest.

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

Despite the pretests for B and C, the system tests for problem G are also weak. Some greedy solutions without any type of matching algorithm can easily pass them. Some Accepted codes even wrote a case wrong(big + 2 * small > m instead of 2 * big + small > m). See 157733355, 157719356, 157726787.

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

    I feel the need to identify myself as one of the big + 2*small jokers because I just find it so incredibly funny that you can pass systests with such a mistake

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

      I passed systests in 1684F - Diverse Segments with a completely wrong solution: 157733083

      (fun fact: I finished writing the code $$$1$$$ minute after the end of the round, I was mad because I missed a huge delta, and only now I've realized that I wouldn't have deserved the AC)

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

There were 22 tests in problem C, and Mine had to fail on the last one :) lucky me

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

1300 (before sys test) -> 900 (after sys test) lol

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

I'm thinking about why Codeforces divide test cases to pretests and system tests, and there might be two reasons.

  1. Using pretests instead of full tests during the contest can sometimes avoid the server being overwhelmed by too many judging tasks.

  2. If someone come up with corner cases which are not initially included in the system tests, those cases will be added to system tests and a rejudging is needed. But a rejudging is almost the same as pretests / system tests.

In the ideal case where the server is very powerful and the original system tests already cover all corner cases, I think we probably don't need pretests / system tests.

See also this discussion.

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

Cheaters copying each other code for C need to stfu and stop crying. Try to learn and get good, then you wouldn't cry about failing test.

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

At least the rating of this announcement behaves like crypto prices.

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

Was it the following distribution of problems today?

Div2 A
Div2 B 
Div2 C / Div1 A
Div2 D / Div1 B
Div2 E / Div1 C
Div2 F / Div1 D
         Div1 E
         Div1 F

Or it’s slightly different?

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

https://codeforces.me/contest/1684/submission/157739291 can anyone please help i am not able to understand where i am going wrong

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

https://codeforces.me/contest/1684/submission/157739291 can anyone help me in getting where i am going wrong

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

To not keep you waiting, the ratings are updated preliminarily. In a few days, I will remove cheaters and update the ratings again!

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

How did this () contest get NEAR's support?

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

    Well they don't get to look through the problems before sponsoring a round, they just decide to sponsor a round that's likely to have a lot of attention, and then sponsor it.

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

Why so many downvotes?

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

Good contest , but f**king pretests !

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

weak pretests on C

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

i am loser that can not have a green color, wuwuwuwu,cry...

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

Although I don't perform well in this contest, I appreciate the quality of the problems, especially the problem D. I didn't realize that the reduced scores of jump can firstly be ignored and finally be calculated by k*(k-1)/2 after all jumps. According to this property, the reduced cost of each jump in index i can be calculated by a[i]-(n-i-1). Then I can sort the reduced costs and simply use greedy strategy by choosing the first k large reduced costs to solve the problem D.

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

Any idea why this solution is getting TLE?

The complexity (as I calculated) is O(m*n), where m*n<=2*10^5

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

    This happens beacuse in some case you don't input all the numbers for this testcase and then your programme input them in the next test case so all numeration of the input numbers breaks.

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

      Cheers, man! I was only calculating complexity and etc, never checked the logical part before.

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

good contest and good problems.

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

Do we need to sort the columns in C? I thought it could be done faster than O(m * nlog(n)) time. My O(m * n) solution was accepted. My idea behind it is as follows:

  • I check how many pairs of columns violate the rules of a good grid. If there are no such columns, we don't need to do anything. Swap any column with itself. If there are more than two such pairs of columns, the grid cannot be fixed with a single swap. Now we're left with non-trivial cases.
  • Else, if there are two such pairs of columns, I swap the larger column of the first pair with the smaller column of the second pair. For example, with one single row [1 5 3 4 2 6], the pairs of columns that violate the rule are the 2nd and 3rd ([5 3]) and the 4th and 5th ([4 2]) columns. Hence, I swap column 2 with 5, and the row becomes [1 2 3 4 5 6].
  • Else, if there is only one such pair of columns, I swap the larger column that comes first with the smaller column that comes last. As in, with one single row [1 2 2 1 3], I swap column 2 and 4 and the row becomes [1 1 2 2 3], and [1 2 1 1 3] becomes [1 1 1 2 3].
  • After those swaps, I check if the grid satisfies the conditions. If it still violates them, the grid must be unfixable.

Is my complexity analysis wrong? Can anyone hack my solution?

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

Please help ;(. I don’t know how to get my crypto.

P.s. My email is unavailable. Maybe I should restore my email?

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

How can I get my near? I got place 128 but I didn't receive an email.

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

Where is the prize?

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

Regarding getting the prize, if I submitted public key from my old account, then my money for this round is gone? The bot does not seem to create new accounts even with new public keys.

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

Can anyone recommend where I can exchange this NEAR nonsense for USD or any real currency?

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

After sending the public key, I accidentally refreshed the web page and I lost my passphrase. What should I do?

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

great round bro enjoyed reading problems