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

Автор vovuh, история, 5 лет назад, По-русски

Обратите внимание на необычное время старта раунда.

UPD: Мы не можем хорошо оценить сложность некоторых задач, поэтому рекомендуем вам прочитать все задачи и подумать над каждой из них.

<almost-copy-pasted-part>

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

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

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

Штраф за неверную попытку в этом раунде (и последующих Div. 3 раундах) будет равняться 10 минутам.

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

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

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

Спасибо MikeMirzayanov за платформы, помощь с идеями для задач и координацию моей работы. Спасибо моим очень хорошим друзьям Дарье nooinenoojno Степановой, Михаилу awoo Пикляеву, Максиму Neon Мещерякову и Ивану BledDest Андросову за помощь в подготовке и тестирование раунда.

Удачи!

Также хочу сказать, что участники, намеренно отправляющие неверные решения и взламывающие их после окончания соревнования (пример), не будут показаны в таблице лидеров по взломам.

</almost-copy-pasted-part>

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

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

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

![ ](mem2)

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

Three back to back contests today — AGC 041, Codechef December Lunchtime, CF Round 611. GLHF!

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

When I registered for this round my rating was less than 1600. But will this round be rated for me if my rating become 1600+ before starting the round (after updating rating based on Educational round 79)?

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

??????THE BEST HAKER?????

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

Funny magic!

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

Huh, really friendly time for us:

For Chinese users.

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

Before yesterday's contest, I had a rate of 1599 and it was planned to have 0 rate change so that I could participate in today's div3 contest, and yes I am 1599 again :D

My plane now is to get +100 rate change, Can I achieve my goal again? :3 I hope sooooo

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

vovuh always have good contests so I hope it will be one of them. good luck everyone :D

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

![ ](cf)

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

Some experts are listed as official participant. Please fix it.

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

    Checkout the magic option at your profile page. You can change your color from there (I am not an LGM :3). This feature gets activated around each new year. Maybe they are not experts, they just changed their color :3

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

What does the post mean by "Note that the penalty for the wrong submission in this round (and the following Div. 3 rounds) is 10 minutes." Does this mean 10 minutes is taken off your clock for a wrong submission?

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

    yes (A wrong submission adds to your time penalty).

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

      I took part in a competition yesterday that also had this penalty and nothing happened to my time when I submitted a wrong solution, what was happening there?

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

        I checked your results in the last contest, your total time without counting the penalty for wrong submissions is 39 + 15 = 54. You had 3 wrong submissions -> 3 x 10 = 30. Therefore your total time penalty is 54 + 30 = 84 (This number is shown under penalty in the standings).

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

    No! This mean that your penalty is increasing by 10.

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

0h5 — 2h5 AM I'm here :(( but i will try participate.

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

UPD: We cannot determine difficulty of some problems thus we recommend you to read all problems and think about each of them.

Hmm, something's fishy.

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

    At last the fishy thing was Task-C. Weak pretests and some solutions don't make sense

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

Today's leaderboard will be colorful :)

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

The announcement for E was very late Costed me 2 wrong submissions Pls look into it

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

    "For example, let the initial positions be x=[1,2,4,4]. The final ones then can be [1,3,3,4], [0,2,3,3], [2,2,5,5], [2,1,3,5] and so on. The number of occupied houses is the number of distinct positions among the final ones."

    You could infer it from the statement.

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

Nice F, thanks)

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

numberline forces

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

I couldn't understand problem F completely. Can someone clarify it more ?

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

Difficulty : A < B < C << D,E << F

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

    I think E was a lot easier than D in Implementation. Though getting the idea was the main thing.

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

what is the 4th/7th/11th test case in problem E? or what can it be?

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

    Yes I was also geting WA on tc 4 with my without DP approach I dont know what is wrong

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

    try these cases:

    5
    2 3 3 3 4
    

    ans: 1 5

    9
    1 1 2 3 4 6 7 8 9
    

    ans: 3 9

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

Great Contest. Managed to solve 4 problems.

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

How to solve D within the time limit?

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

    Greedy problem using a priority queue (min heap) and a flag checker.

    you can keep minimum distances in the queue

    For example, n = 2, m = 3, x1= 1, x2 = 5 Then initially, you need to push (0, 1) and (0, 5) // (dist, position) and set(1) = visited and set(5) = visited

    If -pq,top.first != 0, then add this position to your answer array. and check whether you can insert position+1 and position-1 with your checker. If position+1 is possible, then push(-(dist+1), position+1)

    until you gather m position

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

      I did the same thing nearly but got wrong answer on test 3. Is it because of unordered map? It would be great if anyone can help me find my mistake!! my submission Thanks .

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

E was dp or greedy ?

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

    dp i maintained 3 states, first calculate frequency array for input from 0 to n+1 and if it is greater than 4 make it 3 States are as follow: 1) idx : index of location or houses 2) x : number of friends previous location is asking to me 3) y : number of friends i will give to next location

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

    Greedy af

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

Can we use bfs to solve problem D? i always get memory limit exceeded on test 12 :(

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

    I would say it is half-similar :) Btw I cannot understand how didn't I remembered this problem, lol.

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

    Except for the fact that we couldn't go from 1 to 0 in the old problem

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

Thanks for the contest!

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

I had an hour after solving C. I looked D and thought set+pq naive. But I thought it's not the model solution, and gave up. 10 minutes left, I started to code naive, and I've done it after contest. Submit it, AC.

wtf

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

    this happened with me in E , i solved very late and forgot to memoize the dp.Till then i memoize it time was over :(

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

$$$F$$$ was cool. Here's a fun fact: You can prove that number of trees in $$$n$$$ vertices is $$$n^{n-2}$$$ if you have a working algorithm for $$$F$$$!

Your algorithm is deterministic, so it generates exactly one output for each input. Also, as each output corresponds to a unique ordering of edge importance, each output will correspond to exactly one input. But number of different inputs with $$$n$$$ vertices $$$= n^{n-1}$$$ and number of different outputs $$$= nT(n)$$$ where $$$T(n)$$$ is number of undirected simple graphs in $$$n$$$ vertices which are trees. (We are multiplying by $$$n$$$ because same graph with different roots are considered distinct in the output.) Thus, as inputs and outputs have a bijection, $$$n^{n-1} = nT(n)$$$. Thus, $$$T(n) = n^{n-2}$$$!

This is kinda similar to other proofs of Caylee's formula like Prufer Codes and proof of Caylee's formula by double counting.

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

Can someone help me figure out what is going wrong in my submission for Problem E 67835042. Thanks in advance.

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

HOW TO SOLVE E? PLS EXPLAIN IN BRIEF!

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

    Max can be computed by sorting the array and greedily shifting elements as left as possible to maximise the houses occupied. My logic is going wrong on min (So I don't know)

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

Why should C problem this submission 67826496 should be ac? Something wrong with the judge program?

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

What are the hacks for C ?

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

I really liked this Div $$$3$$$ contest because

  • The difficulty balance was decent. It was not too difficult, yet not too easy.
  • The problems were not very implementation based (like $$$598$$$ for example). After getting the basic idea, it was easy to implement it.
  • There were no subtasks

A great Div $$$3$$$ Contest to end the year !

mango_lassi I generally refer your solutions. How to solve $$$F$$$ ?

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

In C, can we also change the value which is not 0 ?

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

problem D I used unordered_map but I got TLE. I instead of map is AC??? why? I think umap is faster than map. please explain for me, thanks!

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

    I had the same issue!

    https://mirror.codeforces.com/contest/1283/submission/67820013. Here you can see my first implementation using unordered_set. This submission received TLE on test case 6.

    https://mirror.codeforces.com/contest/1283/submission/67838787. AC submission. In this submission I only changed the unordered_set to set.

    Initially, I thought that this discrepancy was due to unordered_set having a very large constant factor, but the strange thing is that it seems that in general, unordered_set performs better than set for this implementation. For example, in test cases 3, 4, and 5 (which all have very big n), the unordered_set implementation has about 1.5 to 2.5 improvement over set in runtime. It seems that test case 6 is an outlier where unordered_set performs at least 5x slower than set.

    I didn't know that unordered_set could be exploited. Is there a different reason that this may be happening?

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

    umap uses an inbuilt hash function to map the values and as you all know that hashes are collision prone hence that TLE you got.umap is O(1) as long as it doesn't face collisions but as collision increase its complexity turns O(n), it's basic knowledge.

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

      everything is basic for future LGMs

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

      Thanks, I had never gotten into this kind of situation before, so I was thinking the inbuilt hash functions are really efficient XD , I will be avoiding unordered stuff from now onwards XD

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

        There is a chilli hash which i dont remember but is known to be quite efficient so its recommended to use chilli hash when using unordered map. IDK if any hacks of it have been found yet though

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

    Yeah, because unordered_map can have a lot of collisions because it's implemented as a hash table...

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

For all who is surprised by why this was the accepted solution: I am surprised not less than you. Thank you badcw for noticing this.

I will try to explain why this happened: when I wrote the checker I forgot to check the stupidest thing — check that all $$$nf_i = f_i$$$ for such $$$i$$$ that $$$f_i \ne 0$$$. I don't understand how could I forgot to do this, but this happened. As you can understand, nobody noticed the mistake and during the round nobody informed me about such weird thing. The comment above is the first source where I found this issue.

I'm very sorry about my stupidity and I didn't want to ruin your fun from participating in this round. I apologize to everyone who was and will be affected by this mistake. I know that MikeMirzayanov who is the (usual) author of the whole problemset is upset by this fact and I understand that many of you are also upset by this fact. Now I cannot do anything with it and can only apologize.

We will make a decision to make or not make this round unrated a little bit later and will inform you as soon as possible.

P.S. I can't even imagine how many participants can be affected by this issue and I'm so scared to find out it :(

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

    Rated!

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

    It appears the person who you linked got hacked. Did anyone else get affected by this error?

    If not, even if there was an error in the checker, nobody really got affected. I don't think the round should be unrated in this case.

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

      In fact, all my checker does is check if the printed array is a permutation without fixed points. So any solution that prints any permutation without fixed points can be accepted. And, as I can see, we already had 400+ hacked solutions and... further — more.

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

        Just out of curiosity, are most of the hacks occurring because of incorrect checker, or just because there was some case that people failed to check/some wrong idea that would have failed even with correct checker?

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

          I cannot check all 550+ hacked solutions (wow, 150 hacks during several minutes) by hand but I think that there are not so many people who wrote absolutely incorrect solution on purpose. I think many hacks are because of some special cases, but because of incorrect checker it can happen that these cases appear in the test data but checker just didn't checked them.

          And the second issue I forgot about (but compared to the incorrect checker this is a small issue): almost all 15 tests I add are useful, but this is not enough to cut off all incorrect ideas and possible bugs. I forgot to add test cases to this problem. But because of the checker it does not matter now.

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

            So the issue is that the incorrect checker just made pretests weaker?

            Because people who passed weak pretests still ended up getting hacked, so the checker didn't make incorrect solutions become correct.

            In that case, no round should be unrated because of weak pretests. If that was true, CodeCraft should be unrated every year.

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

              Yes, the mistake of the checker was false negative (correct me if I'm wrong in the terminology) (accept some incorrect solutions, but not vice versa).

              But I don't sure we can say that this issue can be reduced to "bad pretests" because at least the solution I linked above cannot even pass the first example.

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

                So this is the reason of so many hacks going on, thanks for confirming that anyways

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

                Nope it's false positive. falsely label wrong solutions as right.

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

                That's fair.

                I still don't believe it should be unrated, because at least people could check sample, but it would definitely make sense if it was.

                Thank you for confirming the issue.

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

            We cannot even see the test case on which our solution failed. I even don't know the corrected checker is working fine or not.

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

              Resubmit your hacked solution and you will definitely see the error in the output (and in that way you can make sure that the checker works fine now).

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

                I didn't wrote wrong solution on purpose for problem c ! but if known during the contest I would have changed code ! submitted my code again and it shows WA on test 17 ! It's unfair. Please keep the round unrated !

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

                  @_@ your solution is WA :)) this case, you distribute into slot but don't check index == value :)) not relative!

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

                nvm

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

    I think you should make it unrated for only affected people, so every one wil be satisfied :D

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

      The total amount of rating changes should be zero if I get it right, so everybody will be affected.

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

        Rating is negative sum game, but your point still holds.

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

        No it's not necessary.

        The same thing happened in codeforces round 601 and they made a form for the affected people.

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

      i solved abcde at the time of the contest but i've got c hacked. Despite that, i don't want that the round be unrated for me.

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

    Will hacked solutions be rejudged?

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

      Read this comment. All solutions that which are hacked are already "rejudged" in some way (after the checker fix).

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

    Rated!! It isn't the checker's fault if people randomly submit without testing sample cases.

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

    vovuh you are a lucky guy! The round is rated!

    Only 15 official participants have been affected noticeably by the issue in the problem C checker: I reviewed all the verdicts after the final testing and found such submissions that failed on the examples (but didn't fail on them while the contest). Only 9 of them have non-positive rating changes. So I excluded all of them from the official participants. They are:

    Miracles happen! Happy New Year!

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

      Thank you! You can imagine how glad I am when I got the top 750 for the first time and it's rated @@

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

      I got stuck in C for about an hour and you just saved me from getting -100!
      Thank you so much MikeMirzayanov and Happy New Year!

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

My approach for problem C is to sort the array containing not_occupied position. Iterate from 1 to n and if at any i ar[i] is 0 and i!=maximum_not_occupied_position ar[i] = max_not_occupied_position else ar[i] = min_not_occupied_position.

Still my soln gets hacked what is the counter case please tell

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

in problem 3. if we print n 1 2 3 4 . . . n-1; for all n. will it be correct solution ??

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

    The probability that a random permutation is a derangement is approximately $$$1/e$$$, and that is dense enough for randomised solutions to work.

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

What is the correct way to solve C ?

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

    You can maintain two sets:

    The one which are bad positions set (i.e Index = unfilled element in array) and the other good positions set(i.e are missing from array but no problem as their value != unfilled_position in array)

    Now, you just need to handle the bad positions set first.

    I did it in the following way, there can be various other ways.

    for example, if my array was 3, 4, 6 of bad positions. I would circularly assign positions, example a[3] = 4, a[4] = 6, a[6] = 3;

    and for the remaining 0's positions, you can assign as you wish from good_position set.

    Here is my submission — https://mirror.codeforces.com/contest/1283/submission/67828215

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

    I listed all the ones who did not give gift and all the ones who did not receive gift. sorted these 2 lists.


    compare a[i] and b[i] if equal: swap a[i] and a[i+1] 5 2 1 0 0 0 a=[3,4,5] b=[3,4,5] i=0 a becomes [4,3,5] i=1 a stays the same i=2 a becomes [5,3,4]
  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Let s be the set of people who didn't give their gifts yet. Let t be the set of people who didn't receive their gifts yet.

    For every person in s, assign to him any person (different from him) in t. Note that this is possible for all people in s except the last one (If we assign greedily). However, it's guaranteed that at most 1 person will be assigned to himself. Assume this person p exists. To fix this issue, choose any person (!= p) in s (This is guaranteed since it's given that the size of s is at least 2) and swap his answer with the answer of p. Done :)

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

Hello everyone... I need help >_<. Can anybody check what's wrong with my solution of problem C if you don't mind. (Although it's already hacked xD, but I don't know how to see the test case) https://mirror.codeforces.com/contest/1283/submission/67820446

I'm trying to figure out the correct way to solve this. Thank you!

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

    Already found my mistake. :"D

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

      Can you tell me on which testcase your code is going wrong as my solution for problem C is also been hacked but still I'm not getting my mistake. Thank You!

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

Very nice contest with interesting problems. Thank you vovuh.

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

Can anyone here tell why using unordered_set is giving me TLE on D , where as using only set is passing the tests?

unordered set solution,
set solution

the unordered set soln was working fine until test case 5, which is of same order as test case 6, but giving TLE in test case 6;

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

The procedure in F defines a bijection between set of all trees with labeled $$$n$$$ vertices with one vertex picked and set of sequences of length $$$n - 1$$$ with entries from $$$[1, n]$$$, which proves, that there are $$$n^{n - 2}$$$ labeled trees with $$$n$$$ vertices. Really nice :).

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

Press F for vovuh :(

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

For C task, were we aloud to change spots that weren't 0 or not? Cause the task says we need to fill in spots that have 0s in them, but during hacking phase I saw a solution that just printed sequence 2 3 4 5 ... n 1 (which was accepted).

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

Can someone help me find the reason why my submission for problem D get TLE on 12, and it's memory is too large, it works pretty fast before test 12.

67830125

Thanks in advance :)

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

What is the probability tag for c?

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

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

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

Problem D is a beautiful application of all-sources BFS.

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

How to solve F?

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

Code Can Someone help I am getting WA on testcase-19 of Problem E

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

How to find the first answer in problem E?

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

Can someone provide an explanation to the greedy solution for task E. I am able to calculate the max value ; however I am slightly missing something while calculating the min value

Why Am I saying SLIGHTLY MISSING can be found looking at my answer and jury's answer to the failing test case

I think there is maybe some more ways to merge than I have taken into account. A deeper insight on the greedy approach to the problem would be appreciated. Thanks in advance.

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

      well first of all thanks for the reply. But isn't it invalid input as numbers need to be less than or equal to n ( Mentioned in input format )!

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

        Yeah. I didn't notice it. But it doesn't matter.

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

          Oh thanks now I get it. Basically I am seeing 2 and 4 first ; dragging them to mid 3 ; and thus we will be left with 1 5 and lots of 10s.

          Then that 1 5 increases the answer. The first thing that is coming to my mind is switching the order in which I wrote down the conditions. I don't know whether that will work or not... but I am going to try that.

          Update : Oh ; that also fails. Now I need to do something clever I guess...

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

          Could you give me some hints on :

          1 : How could I correct that. 2 : How did you come up with that test case. I mean your thought process while test case design !

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

    well i was stuck on max so i used your idea and got AC. here is what I did for min:

    sort array and remove duplicates in array



    last = -2 for( i=1;i<array.size();i++) if x[i]-last >1 : x[i] += 1 last = x[i] else: if x[i] - last ==1: x[i]-=1 last = x[i]

    then you count all unique numbers

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

    Update : Done ! Code : https://mirror.codeforces.com/contest/1283/submission/67847724

    Special Thanks to stefdasca and tribute_to_Ukraine_2022 for providing valuable inputs whether related to test cases or the code/approach itself !

    I think stefdasca's idea to find min is really really simple ; both to think and prove ; those benefitting from this discussion should really look into his code https://mirror.codeforces.com/contest/1283/submission/67847914

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

I see too many hacks for C...wonder why??

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

Code

Could anyone tell me what problem is in my code? (min part)

I merged 3 consecutive values to center one. (I marked flags)

And then I merged 2 consecutive values to right one. (I marked flags to avoid a wrong move)

Finally, I merged possible (exist none exist) cases to the center(none).

Thank you for helping me!.

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

Here is my solution for problem C. It is been hacked but still I'm not getting any testcase where it is going wrong. Can anyone please look into my code and say where will it go wrong!

67816712

Thanking you in advance for your help

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

Is the round rated?

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

Really weak pretests :(

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

So what's the result after about 12 hours of discussions. Is it rated?

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

My first 1700+ !!

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

I hacked 7 people in open hacking phase but still didn't get any positive response on my rating or my total score, isn't it weird ??[user:vovuh][user:MikeMirzayanov]

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

Nice contest, especially F problem))))

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

    I understand that there are n lamps and n-1 wire And you need to chooce a root lamp and every lamp can connect max 2 other lamps.

    What is the required, can you clearfiy it a bit ?