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

Автор Vladosiya, история, 9 месяцев назад, По-русски

Привет! В 13.02.2024 17:35 (Московское время) начнётся Codeforces Round 925 (Div. 3) — очередной Codeforces раунд для третьего дивизиона. В этом раунде будет 6-8 задач, которые подобраны по сложности так, чтобы составить интересное соревнование для участников с рейтингами до 1600. Однако все желающие, чей рейтинг 1600 и выше могут зарегистрироваться на раунд вне конкурса.

Раунд пройдет по правилам образовательных раундов. Таким образом, во время раунда задачи будут тестироваться на предварительных тестах, а после раунда будет 12-ти часовая фаза открытых взломов. Мы постарались сделать приличные тесты — так же как и вы, мы будем расстроены, если у многих будут падать решения после окончания контеста.

Вам будет предложено 7 задач и 2 часа 15 минут на их решение.

Штраф за неверную попытку в этом раунде будет равняться 10 минутам.

Напоминаем, что в таблицу официальных результатов попадут только достоверные участники третьего дивизиона. Как написано по ссылке — это вынужденная мера для борьбы с неспортивным поведением. Для квалификации в качестве достоверного участника третьего дивизиона надо:

  • принять участие не менее чем в пяти рейтинговых раундах (и решить в каждом из них хотя бы одну задачу)
  • не иметь в рейтинге точку 1900 или выше.

Независимо от того являетесь вы достоверными участниками третьего дивизиона или нет, если ваш рейтинг менее 1600, то раунд для вас будет рейтинговым.

Задачи были придуманы и написаны нашей командой: myav, Gornak40, senjougaharin и Vladosiya.

Также большое спасибо:

  1. MikeMirzayanov за помощь с идеями и системы Polygon и Codeforces.

  2. nigus за красное тестирование раунда.

  3. vladmart, Gheal, KseniaShk за жёлтое тестирование раунда.

  4. htetgm за фиолетовое тестирование раунда.

  5. natalina, SashaT9, lockdown, bma20006 за синее тестирование раунда.

  6. RedDreams за бирюзовое тестирование раунда.

  7. the_Incharge, Aurora__, Longqiang за зелёное тестирование раунда.

Всем удачи!

P.S. С наступающим днём святого Валентина!

UPD: Давайте продолжим серию анонсов с фотографией авторов :)

UPD2: Разбор

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

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

Wow, you put a lot of effort to make a lot of quality div3. Thanks for a lot good div3 round to help beginner to advances in CP.

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

$$$\mathtt{Thanks \ for \ Legendary \ Div.3 \ Rounds , Looking \ forward \ to \ join \ the \ authoring \ forces}$$$

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

Yeahhhh!!! Div 3 Letsssss Gooooo

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

Div 3 are my favourite. Lots to learn.

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

the round number and date is wrong please fix

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

the round and date are wrong

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

speedforces let's go

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

Thursday, October 12, 2023?

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

I hope this is my last round before cyan

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

Thank WHO for red testing 😳

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

My first unrated Div3 I mog everyone

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

Excited!! Hoping to reach pupil this time :)

UPD : FINALLY REACHED :)

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

Hi, The penalty will be applied for only solved problems? Lets say, I have 2 wrong answers for a problem but I fail to solve it. So, will the penalty be applied? Thank you

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

don't make your gf sad, prepare gift after contest

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

    cp and gf? nah man something doesn't feel right. Just don't touch grass and stay home I guess

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

отличные фотки, а как насчёт подождать 2 года в очереди, как все остальные?

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

I had no idea authors could be so pretty. I'm blushing (,,>﹏<,,)

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

    mmm, why?

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

      I was hoping the authors would see it and feel happy.

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

        No, I mean why you thought that authors couldn't look pretty. As far as I'm concerned they're all human beings, just like the rest of us

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

          If I became an author, I would be a good counter-example :)

          But you are correct. Everyone is beautiful. That's why its great to have pictures of the authors in the announcement.

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

so sweet post. Happy Valentine's Day. Do spend time with ur loved ones, instead of attending contests

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

Can you pin social media handle (Instagram) of girls in image, i need tips for CP from them :)

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

I am the one in the button right on Valentine's day :⁠,⁠-⁠)

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

I don't get it,why are authors making a 'C' with their hand?

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

    May be because Mike also did the same on his picture (to hold the burger)?

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

    It's not the letter "C", it's half a heart (we tried, ahahah) We wish the community a happy Valentine's Day!

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

      Got it,that makes sense,i need to go out and meet some real people.

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

Thanks for the contest but why y'all throwing up gang signs?

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

Valentine's Day ? oh man,i'am CPer.

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

Valentine's Day ? Oh man, i am CPer

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

Wow, this is great.

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

Looking forward to it!

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

My first unrated contest

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

They are so similar

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

why are the names of the authors written in reverse

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

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

No tester comments this time?

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

I really hope to become Pupil in this contest.

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

Hopefully my last rated div3

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

Wish everyone will have a good score!

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

why the solution will be out 5 minutes before the contest ends?

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

Hope positve delta for all rated participant.

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

Finna reach 1000 elo ;))

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

I'm really looking forward to the Codeforces contest taking place tonight, on the fourth day of the Lunar New Year. It's an exciting opportunity to challenge myself and improve my problem-solving skills!

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

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

Fells like C

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

NOOOO THE CONTEST END 10 MINUTES AFTER MY OLYMPICS(school)

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

Good luck to everyone.I hope to become expert on this round.

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

Hoping to solve atleast 2 problems this contest

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

Iam ready to solve just one problem As usual

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

good luck for every one

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

Thank you

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

Hope to reach expert again

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

hope to be specialist,,if i could solve E, my day will be great otherwise it gonna worse,,,

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

I hope u turn blue today.

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

I give up more than an hour trying to figure out B and its just not working

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

    same here... i dont know what are the mistakes i am doing as A,B,C all the three questions are very easy

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

Disgusting problem F

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

I absolutely clutched problem E with 10sec remaining!!

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

C keeps giving me wrong ans in test case 2, is it that hard?

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

Got the right idea for F about an hour after the contest started but spent the next hour debugging double-hash. :(

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

please hint for C

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

    Try to fix equal element, either equal element can be first element of the array or last. Then find the range i and j

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

    You MUST choose x as the first OR the last element.

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

    three possible ranges you will select from k to n , from 0 to n-k , or from i+k to n-k. k is the index is where there's no more duplicates from the beginning or end from the array, like [1,1,1,2,3,4,5] k is at index were ai is equal 2 , so we can make the range we select [4,7] , same from the back. i+k to n-k is when the duplicated at front is the same from the back . sorry for bad explaining

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

    You can look for the longest segment of equal elements from the start, let's call it a, and the longest segment of equal elements from the end, call that b. Now, there are two cases:

    (1)If the first and last elements are equal, you can choose the contiguous segment of elements not in either a or b. (notice, if len(a) + len(b) > n, the answer is zero. Else the answer is n — len(a) — len(b))

    (2)If the first and last elements are not equal, you choose the equal element as the element that comes in the longer segment. (notice, the answer in this case is n — max(len(a), len(b)))

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

Maybe it's just me, BUT F seemed way easier than both D and E, although didn't spend much time on E. solved F in 10 mins. Overall very Fun contest. Great Problemset.

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

The CloudFlare feature is really a shit ,can't submit the solution even after doing it

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

i am annoyed i couldn't get F i didn't think it will be cycle detection at all.

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

Problem D is nice, thanks for the contest. But how to solve F?

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

I feel like idea of F was simple but the implementation was tedious. Also, loved G!

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

Any hints for G?

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

    Try reducing this problem to a stars and bars problem Try to think what are the prerequisites if we want to place the 4th block at any place same goes for the 3rd Think which blocks are the limiting factors and which we can take care of irrespective of their quantity Have a Great solve!!

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

Maybe it's just me, BUT F seemed way easier than both D and E, although didn't spend much time on E after I saw F, which I had just the right idea for. Overall very fun Contest.

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

Quick hints for all the problems before the Editorial comes out.

A: Just brute force on each index using 3 for loops.

B: As the water can't flow backward, therefore the amount of water in any prefix can only decrease or stay constant.

C: Check if all equal, else count prefix equal length and suffix equal length.

D: What if we store the remainders in pair<int, int>?

E: Replace each number by the count of its trailing zeroes, now play the game greedily.

F: We can easily create the order from the first 2 arrays given (if k = 1, then its YES). Just make sure to handle one edge case [1,2,3,5,4] and [2,1,3,5,4], basically those in which there are 2 possible orders)

G: Pieces 1 and 2 can only appear alternatively, and the pieces 3 and 4 will always fit in the between their occurences. Also, pieces 3 and 4 can be repeated, while 1 and 2 can't. Try fixing Piece 1 or 2 as the first piece in the chain, do you get some general pattern?


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

      Easier way to solve F without using graph

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

      Yeah this subproblem looks way more easy and familiar, I was just hasty and went with my first thought.

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

    In F, I think the simplest way to code is model it as a graph and use topo sort. I think that makes implementation really easy with template :)

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

    can up please tell what's wrong with this

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

    I did F after constructing the graph and checking if the number of SCC is equal to $$$n$$$:)

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

      can someone define the statement in a prettier manner? I can't understand that. I know how to do cycle detection but the statement itself is unclear.

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

F — "Detect cycle in a directed graph."

Submission- 246203312

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

can anyone share any hint for problem D?

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

How to combine pieces in the second test case of problem G (one sample way would be enough, please)?

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

    121212121244 or 121244121212

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

      Hmm, but there are only 2 pieces of type 2 and single piece of type 1: c = [1 2 5 10]

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

        Sorry I misread it as second last test case, for the 2nd tc, here is one,

        333332124444444444 or 333332444444444412

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

          Thanks! Now I see why I could not solve the problem :)

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

I just wanna say thank you for making this contest, I was able to solve till F( can't believe I did this )

I think I have very unique solution for problem D: Problem D Solution

I used modular operations for storing single value in map

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

    I did not get the logic behind your code. int v = mod*a + b ; int fv = mod*fx + fy ; why did you do this?

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

      For pair $$$(a,b)$$$ we interested in pair $$$((x-a)\mod{x}, b)$$$

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

      this is a trick,

      for representing two number in single number,

      lets a , b are the numbers i want to encode it into one number, then i will choose mod > max( a , b )

      then encoded_number = mod*a + b

      when you want,

      to get b = encoded_number%mod ;

      to get a = encoded_number/mod ;

      so with one encoded_number i have stored two values

      EDIT: fixed formatting

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

just 3 again

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

Code editor is not working, keeps running and no result, makes the whole experience shit. Cant run test cases.

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

    you just calculating binomial coefficient, how is this related to solving G?

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

      Because the only thing that came to my mind was:

      • place a 3 on this group (between 1 and 2),
      • or move to the next group

      which led me to the formula: $$$dp[i][j] = dp[i - 1][j] + dp[i][j - 1]$$$, and I didn't realize that it was effectively just comb(i + j, j), so that's what ChatGPT told me.

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

Here is how you can choose the next type of element to add in problem G.

Two nice observations:

  • This condition must be satisfied: $$$\left|c_1 - c_2\right| \le 1$$$.
  • Think about the problem without elements of types $$$3$$$ and $$$4$$$, then try to insert them in the generated chains.
»
9 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

When I saw other's solutions,I found the problem E very easy. However,I think F is easier than E because I can get the idea to solve it without thinking.(if you know something about graph)

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

    I agree. I knew immediately I could use Khan's algorithm to solve F right after I read it. But the strategy for E took me some time. (and I solved F before E)

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

I was wondering whether this contest gives any rating? I am 401 rated. I have participated and solved 2 problems but haven't got any rating. Can anyone tell me if i'll get any rating?

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

Does the following work for F?

Rearranging any of the participants except the last one cannot change the last participant from the permutation. Therefore, we can find the real permutation by checking which one has the last participant only once. Now, that we have obtained the real permutation, we can compare all of the k inputs to the real one and check.

This doesn't work when k == 2 but in that case we can simply check subsequences ignoring the first two numbers.

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

    Better Idea:

    Simply Ignore the first Position of Every observation. Take an edge pointing from v[i] to v[i+1] (1 <= i <= n-2) for Every participant observation.

    Check for the cycle in the graph, If the cycle exists then NO else YES.

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

      How to check if a cycle exists? I tried doing it using DFS but it exceeded the time limit.

      246185460

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

          Thank you!

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

            TLE coz of MAX maybe, You are unnecessarily assigning 2e5+7 values to the array, even when N = 1.

            Just imagine for the test case where t = 10^4 and N for each case belongs to {1,2,3,4,......2e5}, even if k = 1.

            As this test case fits under the given constraints, You will be doing 2e5*(1e5)/2 roughly around 1e10. That's y.

            I think so, I can be wrong.

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

              Yeah, I think that was the problem. I just resubmitted resetting only n values and it got AC. Just missed it during the contest :(

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

    246262272 Maybe hashing was unnecessary, also who knows if this might get hacked.

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

Loved the beautiful Stars and Bars problem (G) Got to the solution but didn't submit earlier as I was unsure if it would be rated for me Nonetheless Here's my solution in case any one wants a reference: https://mirror.codeforces.com/contest/1931/submission/246256160 :)

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

As an expert I failed D: TLE on test 9. Here is my code: 246198274. Could anyone help me with debugging? I think this is O(nlogn).

Edit: This is O(y). Forget it

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

How to solve E? Didn't get any idea at all :(

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

    1) Ans "yes" if number of digits in the last number >= m + 1. Anna in each step tries to reverse number with maximum zeroes on the end. Sasha in each step does concatenation number with maximum zeroes on the end with any number without zeroes on the end (number without zeroes on the end is guaranteed to exist, since it either exists initially, or Anna will make it her first move)

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

    it is optimal for both of them to the choose the numbers which have most no. of zeros at the end

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

    multiset<pair<trailing_zeroes, digits>> and just model a game

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

    you can simulate it as follow: for anna reversing a numbers is equivalent to deleting the trailing zeros so she should take the number which have the most trailing zeros every turn for sasha she will also choose the number with most trailing zeros and concat it with any number (it doesn't matter but we can choose the second most number having trailing zeros for implementation purpose) by doing this it save the trailing zeros in the largest number so anna can't remove them by reversing the number thats it u can keep track of the numbers having most number of trailing zeros using a priority queue and update it each turn accordingly

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

This is my first AKed competition, and the problems were wonderful and quality, thanks! I like G best, it's an interesting counting problem.

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

FUN QUESTIONS, Extremely challenging but really good questions.

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

Can someone please help me in Problem C?

I am not getting why it gives me wrong answer on test case 2 (112th answer in tc2 is wrong it says, and I am not able to see what that case is because after certain lines the input of test case just shows "...")

Here is the submission —

246248784

Thanks!

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

    I dont know python so I apologize if I am wrong but if first and last element are equal then the ans should be 'n-(s+e)'

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

      yes so in python ".strip()" will remove all occurences of the passed argument from the front AND the back ONLY(not in the middle). So that part works alright.

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

I think you should reduce the time limit of this problem. this submission -> https://mirror.codeforces.com/contest/1931/submission/246247517 runs in 1 second. this submission should not get AC because # of testcase is 10000 and this submission is executing a for loop of 200005 every test case. that's more than 2e9 operations.

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

!What is this submission code
is he know the testcase?

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

How did the number of participants increase so much in Codeforces rounds? Yes, I agree that the number of programmers is increasing all over the world now, but how did it suddenly increase so much? Even 2 months ago, the participants in Div-3 were 10-15 thousand, now it has gone to 30 thousand.

Achieving double contestant status in such a short timeframe is remarkable.

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

After successfully wasting 1.5 hour on B i smashed binary search in B

can someone hack it?

246247536

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

    why would you even think of binary search . you already know that the good value is sum/n . that's the only way you can make tha array the same

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

      yeah i am dumb. do not know why that did not come into my mind

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

        same here I thought of every thing in this life except that the only possible number is sum/n by the way I wanted to do binary search but I didn't know how to handle the good function but I learnt that from you now I mean the 1 , -1 and 0

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

Video Editorial for problem B (Audio : Hindi) TUTORIAL VIDEO LINK

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

Is this hackable B ? 246258951

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

Submissions of e have increased due to heavy cheating You can have a look these code are exactly the same with minute changes in the function and use of template and also these two ids belong to the same team 1.https://mirror.codeforces.com/contest/1931/submission/246234546 2.https://mirror.codeforces.com/contest/1931/submission/246243950

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

Thanks to the authors for an interesting div 3 without clay and with tasks that are fun to solve. After this div and the Cognitive Technologies Olympiad, I realized that the name Gornak in the list of authors => good Olympiad/div.

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

Can G be solved using inclusion exclusion ?

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

May I ask why I passed 3 questions but didn't receive a rating in the end? Or who should I seek help from? I really want this rating, thank you.

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

    Rating appears after 1 to 24 hours from the end of a contest, and if there is a hacking phase, like this contest, then it may last up to 24 hours or less.

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

in Problem E , i wrote code which was absolutely right, the only thing i missed was, if number>=10^m then number of digits should be >=(m+1) not >=m (it was pretty close :) )

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

I submitted E in the last 10 seconds ... soon after the contest ended , it was as if my submission vanished...i submitted after 10 seconds and got an AC...which time is evaluated , time of submission or time when we get an AC ?

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

I submitted E when there were 10 seconds for the contest to finish and my submission got vanished...

why so ?

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

In Problem C anti hash test case can be created as many unordered map solutions have been accepted.

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

How to solve Problem G?

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

wow that was very cool

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

A different way to do F:

  • Each element (after the 0th element in the kth list) can only be it's current position or its current position+1

  • Store both possibilities in a vector

  • Remove possibilities for elements when they're no longer possible (i.e. the current element's position in the kth list conflicts with the elements position in a previous list)

  • The answer is no if an element has no possibilities, or if its only possibility conflicts with another elements only possibility

  • Otherwise the answer is yes

Code: https://mirror.codeforces.com/contest/1931/submission/246250979

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

I am getting wrong on test case 3 for problem E. The approach is " The first set contains numbers with leading zeros, while the second set comprises numbers without leading zeros. Within a while loop, the first element of the first set is removed, and its length is added to the second set. Additionally, the first value of both sets is combined and inserted into the second set. The game iterates until the first set is empty. Afterward, the sum of the lengths in the second set is calculated. If this value exceeds a specified threshold, Sasha wins; otherwise, Anna wins ". Can someone help me with this, please? Solution link := (https://mirror.codeforces.com/contest/1931/submission/246279314)

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

I am getting wrong on test case 3 for problem E

My approach is " The first set contains numbers with leading zeros, while the second set comprises numbers without leading zeros. Within a while loop, the first element of the first set is removed, and its length is added to the second set. Additionally, the first value of both sets is combined and inserted into the second set. The game iterates until the first set is empty. Afterward, the sum of the lengths in the second set is calculated. If this value exceeds a specified threshold, Sasha wins; otherwise, Anna wins.

can anyone help me find what's wrong in this?Solution link

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

really enjoyed this contest, particularly problem D. start to see some common patterns on int-mod problem..

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

my respect to Aleksander Gornak

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

I was getting runtime error (STATUS_ACCESS_VIOLATION) in E, during contest , but after contest when i submitted same solution it got accepted . runtime error during contest code link.
accepted code after contest. Thanks

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

    The problem is this for loop here: for(ll i=vect.size()-1;i>=0;i-=2).

    In C++, the return type of std::vector::size is an unsigned integer. When vect is empty, then vect.size() - 1 becomes 0 - 1 which then overflows to UINT_MAX. This causes out of bounds error which is why your program got runtime error. (It seems that this is changed in C++20, which is why your other code got accepted)

    To fix this, you just have to convert vect.size() into any signed integer type. For example for(ll i=(ll)vect.size()-1;i>=0;i-=2). New code

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

One of the best rounds I've ever participated. Thanks to all the writers and testers for offering us such a round.

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

The best div3 round contest I've ever participated!Thank you!

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

when will the rating come out?

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

    you need to wait that the system testing ends first (is around 80% right now). after that eventually the rating will be updated.

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

      Oh,Thank you.This is my first time to attend CF.(I find out my G turned out to WA,It used to be AC)

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

        I saw it as a AC, when the system testing is running and your AC code is still on queue, if you had a WA before the AC, you will see as if you get a WA. So congrats on your first contest participation in CF was really good!

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

        First CF got G AC,congratulations!

        I'm waiting the rating, too.

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

        Thank you for your encourages!

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

Can anyone tell me where have I made a mistake in these two codes? Only difference I have made from my side is making the capital N,small n? Basically I had initialised all visited array elements to zero in reset function. Thankyou in advance.

1st submission 246198873

2nd submission 246233252

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

    I don't understand why exactly gives you another answer (actually I'm more curious of how didn't get you RTE hahaha weird stuff)

    But the reason why the change works is because in the WA submission, you have the following code:

    vi g[N];
    void reset(){
    	fr(i,0,N){
    		g[i].clear();
    		vis[i]=0;
    		vis1[i]=0;
    	}
    }
    

    and fr is #define fr(i,a,b) for(int (i) = (a); i <= (b); (i)++)

    So, the cycle in reset() will access to the position $$$N$$$. But the arrays g, vis and vis1 are of size $$$N$$$, I change you code putting a -1 and now it gets TLE, that makes a lot of sense, because $$$t = 10^4$$$ and $$$N=2e5+69$$$, so you will do around of $$$2\cdot 10^9$$$ operations just to reset.

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

Hello

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

In Question 4 this code exceeds time limit on test case 33 cant understand why its o(n) approach can someone please help me?

include<bits/stdc++.h>

using namespace std;

define ll long long

int main() {

int t;
cin >> t;
while(t--)
{
    ll n, x, y;
    cin >> n >> x >> y;
    unordered_map<ll, ll> dp;
    ll a[n];
    ll ans = 0;
    for(int i = 0; i < n; i++)
    {
        cin >> a[i];
        ll f = (x - a[i] % x) % x;
        ll l = a[i] % y;
        ans += dp[f*y+l];
        dp[(a[i] % x)*y+a[i] % y] += 1;
    }
    cout << ans << '\n';
}
return 0;

}

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

But may I ask why I still haven't received a rating? It should have been a long time since the hack phase ended. I really want the rating for div3 this time, thanks.

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

Why there is no rating change? My rating is less than 1600

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

    It takes a while after the system test for codeforces to remove cheaters and recalculate the rating changes.

    By the way, have we met somehow before?

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

can anyone just tell me which are valid patterns in G? I can't find any for 1 2 5 10

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

when it will be rated?

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

All my submissions have been blocked due to one answer(246237190) for question 1931F being very similar to the ones given by two other people.

One of them is from another guy studying in my institute who happens to study from the same materials and has given similar contests, hence the answers are very similar. Please review it and I hope my submissions are considered.

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

    This clearly is a very repeated question, since many people have the same solution Please review it once.

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

      It is very clear that You have copied this code 246237190 from somewhere, you didn't even put the effort to indent it properly. I think it is justifiable to get blocked.

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

        So your justification of me getting blocked is the code not being indented

        i was in a hurry, thats it

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

        You know what Leave it, you and I both know how much ever I fight there isn’t going to be any change I better focus on future contests, even if they unjustly block me again I will create new account and start again

»
9 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Key observation of problem E!
»
9 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I am new to code forces this is my first contest, I have solved two questions still didn't get any rating. Did I miss anything?

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

hi, i think there have been a coincidence and have got the code matched with some unknown user at problem d i think this is clearly a coincidence as we don't know each other and we are also not friends with each other i will be making it sure to use the more unique variables

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

Независимо от того являетесь вы достоверными участниками третьего дивизиона или нет, если ваш рейтинг менее 1600, то раунд для вас будет рейтинговым.

Мой рейтинг сильно меньше 1600, однако это соревнование стало для меня не рейтинговым. Пытаюсь разобраться почему так, подскажет кто?

Update: О, похожая проблема как и у HarinRamesh. Запись об участие у него есть, но отображается как "нерейтинговое".

Т.е. нужно просто подождать?

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

Hi, I participated in 925 and it wasn't rated for me, does anyone know why? I am < 1600 (878).

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

Give me my rating pls((

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

Finally blue. Was a great experience.

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

Hi I attended this contest and I solved problems A & B and got D wrong. And i'm not able to find the constest under my contests and my rating afterwards didn't although I am under 1900. Can you please explain why my rating did not improve?

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

Become a pupil from this contest.

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

I am sorry for using a code snippet that is used by lot of other people. This made me into this trouble of making code solution identical to other users. I regret using this snippet now. I shall prevent myself from further using this snippet anymore. Sorry CF ...

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

why aren't the ratings changing ? Its been 2 days

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

Hello respected judges,

My code was accidentally matched with the other participants. I have no idea about this rule of the CodeForces of contests. I didn't know this before. I had no selfish intention to do this cheat of any type. That participant is my college friend, and we discussed not exactly but similar type question before this about how to solve it. But I didn't know how we both accidentally write up the same code.

So, please can you give me my rating back, in future I will take care of it and not publish my code publicly anywhere.