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

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

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

<almost-copy-pasted-part>

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

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

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

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

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

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

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

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

Удачи!

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

</almost-copy-pasted-part>

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

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

thank you for holding a div3 contest!!

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

I hope the statements will be short and clear and problems will be balanced. Good luck everyone :)

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

How to register unofficially ? I clicked on register, but it only allows for ratings less than 1600.

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

    I think he means by unofficially after the contest is over, for when it will not be rated.

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

    You get a big ugly warning message that you will be registering "out of competition" (i.e. unrated), but you should still be able to click past the agreement and then solve the problems during contest time

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

    solve question ...you will be registered unofficially !!

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

Imagine Vovuh were a super cool meme-lord...then these posts would have had dope memes after the closing bracket and everyone would have literally waited for every Div 3 announcement holding their breath...

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

I think Vovuh's round better than Pikmike's

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

after a long time div 3 will be held.

Thanks to Vovuh!

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

Nice time.

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

Let's hope for the best .-.

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

A person with a rating of 1599 can enter the competition but a person with a rating of 1600 cannot This makes the second person fall far behind

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

this is my first out of competition contest :)))

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

I had to wake up on my alarm clock on my day off so as not to oversleep the contest ( -_-)"

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

I am happy that we don't have to stay up ( qvq

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

Hope it to be like previous div2 597 round contest That was really amazing....

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

i need only 3 points to be pupil ..please

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

dislike it if yo wanna lose ur rating

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

When will the DDOS attack begin?;)

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

i hope this will be a great round

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

10 minutes delay returns

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

Delayed :/

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

Перенесли с 16:05 до 16:15?

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

I look forward to glory and honor. The competition may begin.

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

delay 10m?

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

Alright, let's do this. I hope to solve atleast 4 questions tonight.

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

Div.3! Great! Li Linjiang Tian Xia Di Yi!

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

this was unbalanced one ..

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

    no it was, you think like that only beacuse you did just two problems. Problems were really good!

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

    If you swap D and C it's actually relatively balanced, maybe the difficulty between A and B is a bit too wide though.

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

    In these type of contests you have to keep your mind cool constantly while implementation.

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

I like that contest.

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

here's no system testing?

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

    No, in div3 and educational contests tests aren't divided into pretests and tests and there are no hacks during the contest time, so your code runs on all the tests during the contest. After that there's a 12hr hacking phase before the final results are announced.

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

Does anyone know why a runtime error may occur on 15th test in problem D?

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

How to solve F?

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

    If the strings don't have the same letters, answer NO. If some letter appears at least twice, you can swap those two letters to be adjacent, then swap them in the first string and make an arbitrary swap in the second string, therefore we can answer YES. Now assume duplicate letters don't appear, and consider the strings as permutations.

    You can do any even number of swaps of adjacent elements to one string without changing the other. Also, every inversion of some intervals either doesn't change the parity of the permutations or changes the parity of both permutations. If the parities are equal, we can make the strings equal with an even amount of swaps, therefore we answer YES. If they are not equal, they cannot be made equal, and therefore we answer NO.

    Code: 64228071

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

      Do you calculate parity in O(n^2) ?

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

        You can do bubble sort and count how many swaps you make or check for every number how many numbers are higher to the left.

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

        parity function will check parity of strings if there is no repeated character. That means length of strings should be less than 26 .It is simple pigeonhole principal

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

        Number of adjacent swaps can also be calculated in O(NlogN). Although it is not needed here since in that case we have N<=26.

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

      "Every inversion of some intervals either doesn't change the parity of the permutations or changes the parity of both permutations."

      How to prove this ? Which permutation is being selected in both of the strings ?

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

        Consider any segment $$$T$$$ of a string $$$S$$$.

        There are $$$3$$$ types of inversions

        1. Both characters in $$$S$$$
        2. One in $$$S$$$ and one in $$$T$$$
        3. Both characters in $$$T$$$

        Only type $$$2$$$ is affected by reversing a segment.

        If the length of the segment is $$$L$$$ and there are $$$x$$$ inversions, the number of inversions becomes $$$L(L — 1)/2 — x$$$

        If the first term is even, the parity remains the same.

        Otherwise, the parity flips.

        Amazingly, the parity flips based on the length of the chosen segment and not at all on the permutation we use :).

        This is a mind-blowing fact :)

        Here are my solutions to this contest and here is my detailed editorial :)

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

Hello div2! Is that you ?

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

B, C & D are easy to come up with the idea, but the implementation is not trivial, I don't like these kind of problems.

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

I submitted problem C with MS Visual 2017 compiler (I use Visual Studio 2017), and it gave me WA on the 2nd test case while it's working on my computer and on GNU compiler, I got AC with the same code after the contest.

with MS C++ 2017

with GNU C++ 2017

So I think something is wrong with MS C++ 2017 compiler.

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

    You might be doing something that's undefined behavior

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

    Yep, undefined behavior

    Clang++17 Diagnostics says: p71.cpp:12:7: runtime error: index -1 out of bounds for type 'int [1001]' SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior p71.cpp:12:7

    In a[qan - 1] when qan is 0

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

Is a solvable with binary search?

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

How to solve B?

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

    use greedy and keep array of positions where you swapped.

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

      I did exactly this and somehow messed up lol.

      LOL I should've just added check if I actually need to swap elements

  • »
    »
    13 дней назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    1. Set range_begin to be the beginning of the vector.
    2. Endless loop 2.1. Find the minimum number (mn) and its index (mn_i) in a range [range_begin, vector_end) 2.2. Print the mn 2.3. If mn_i is in the end of the vector (i.e. vector_end - 1), then loop is done 2.4. Else if mn_i is equal to range_begin, then range_begin++, since you've just printed this number 2.5. Else print all the numbers in vector in range [range_begin, mn_i - 1), swap numbers at positions mn_i and mn_i - 1, set range_begin to mn_i

    The idea behind this is that since you can only perform 1 swap for each index, it means you can carry to the first position the minimum number in the list, and then you'll have only swaps in range [mn_i, vector_end], thus find the minimum in this range and use some swaps to carry this miminum as much as you can. Repeat until you've no swaps.

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

MikeMirzayanov Just a little suggestion from me, could you add contest timer in m1 / m2 site during the contest?
I know that you can estimate the remaining time yourself, but it could be more convenience (at least for me) to see the timer directly. Thank you.

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

If you hack something, will this give you points?

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

Great Contest. Thanks for this round. Clear Statements! Keep up the good work.

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

I couldn't access codeforces last 20 minutes. Did anyone have a same problem? I confirmed some of Japanese contestant couldn't.

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

    use lightweight sites (m1.codeforces.com) (m1/m2/m3)

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

    yeah. I faced this for half an hour.

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

    Yeah, my fellow Indian contestants and I were also not able to access the contest, but it was accessible using m2.codeforces.com

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

      I accessed with m1.codeforces.com. But, you can't say the current standings.

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

      Actually, I couldn't reach codeforces even the contest is end. but, I found that some of discussion was posted when we couldn't access codeforces. whats going on!?

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

    I had same problem and I thought this contest would be unrated. I tried to access another web site but unfortunately I forget my password. Zzz

»
2 недели назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
LOGIC OF A:- Check for largest multiple of n just below S and then check how many coins are required for it if(it is less than available coins then it is case 1:-
now 
m=((s/n)*n)/n;
    if(a>=m)
    {
       j=s-k;//final money left to pay after making payment with type n coins
    }
    else 
    {
        l=a*n;
        j=s-l;//final money left to pay after making payment with type n coins
    }
  Now final Answer is 
`    if(j>b)
       cout<<"NO\n";
       else 
       cout<<"YES\n";
    }`

Now for B the following is a big hint

Spoiler

Now FINAL D //C I DON'T TRIED

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

greedy and greedy. C and D would have been more classical.

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

Some swapping problems! I like problem D.

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

How to solve problem E. I can't get any idea.

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

    Okay, My approach is , first of all sort the array. Now we have to split the array into such sub-segments that each segment is consists of at least 3 numbers. Now, Let our answer be ans. At first we can say that ans = arr[n-1]-arr[0] . Now for each valid splits in position i, we can improve our answer by arr[i]-arr[i+1] . we have to find a set of such i, that summation of all arr[i]-arr[i+1] is as lowest as possible. Let it be Sum . So , our final answer will be , ans= arr[n-1] — arr[0] + Sum . How do we find such Sum ? Just used dp on every i where i>=2 && n-i<=3

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

    I did it like this-
    First sort the array
    Now the obervation is that each segment would of atleast length 3 and atmost length 5. It makes sense because if we have a segment of length 6 then we can split it into two segments of 3 and we are sure to get the smaller sum because the array is sorted.

    now we can use dp , here dp(i,j) is the min cost if we have a segment of length j ending on ith index. Of course only 3 values of j are possible.
    Since you could not get idea, I am not writing the complete equations and mentioning only the state. You can look at my solution if you want.

    ps: I hope this passes the sys tests too.

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

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

A very nice lexicographicallySmallestForces contest!

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

Codeforces was not opening for the last 45 mins, and I literally thought there has been a DDoS attack,for which I left doing the contest.

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

Anyone please tell me what's wrong with my code 64271656 for problem B?

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

can someone please explain problem E dp state and transition

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

    First, Sort array $$$a$$$ in increasing order. Each team contains at least 3 members and you want to minimize the total diversity of all teams. So, there is no reason to build a team more than 5 members because you always can split the teams (>5 members) into smaller teams and reduce the diversity. Now, you can solve problem with DP technique in linear time.
    Let $$$dp(i)$$$ be the minimal total diversity of the school which consists of first $$$i$$$ members.
    Transition:

    $$$dp(i) = max \begin{cases}dp(i-3) + a[i] - a[i-2] \\dp(i-4) + a[i] - a[i-3] \\ dp(i-5) + a[i] - a[i-4]\end{cases}$$$

    Base case:

    • $dp[1] = dp[2] = Infinity$
    • $$$dp[3] = a[3] - a[1]$$$
    • $$$dp[4] = a[4] - a[1]$$$
    • $$$dp[5] = a[5] - a[1]$$$

    Run transition to calculate $$$dp[i]$$$ with $$$6 \leq i \leq n$$$.
    The answer is $$$dp[n]$$$. You can construct the configuration by yourself.

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

Why is loading so slow??? It takes me ten minutes to load a problem

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

I can't find my mistake... where is "wrong answer each team should consist of at least three students"??? https://codeforces.com/contest/1256/submission/64279213

  • It was incorrect teamcount....
»
13 дней назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

In problem E, I came up with the solution using DP but I can't construct the configuration in time =)))

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

    you can construct the configuration after getting the answer, by checking all the state from dp[n] to dp[1],details can be referred to my code.

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

Waiting for system test to become blue again...

Edit:FST on C..weak pretests..to be more careful next time..

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

In problem C I wrote p+d<n instead of p+d<=n and passed the pretests... Why so weak pretests?

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

congrats. system testing is done

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

I solved 4 questions in contest and 2 of them failed system testing ! Why are the pretests so weak !!! And that too for a Div3 round this is not how it should be, I understand that while coding one should consider all cases but shouldn't that be tested in Div2 then?

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

It's the first time I become Expert, I'm so happy now =)))

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

How could a O(n^2) solution passed for F? I don’t get it. Please someone explain it to me. TIA.

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

why i receive a runtime error by using stl?

problem D (div3) https://paste.ubuntu.com/p/9rbHFmBcMP/

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

I have a doubt regarding the problem "Minimize the Permutation". My approach was that I iterate from 1 to n and try to bring the smaller elements(from 1 to n) forward, and do the same for next element if, I have either brought my current element(say i) to the 'i-1'th position or I could not swap it anymore(to bring to a lower index) for that I maintain a 'swapped' vector.

But, my solution didn't work because I didn't add the condition "arr[j-1]>arr[j]" for the while loop(i.e we have to swap only if the element on the left is bigger). And works fine if I add it. Can you please help me understand that why do we need to add this condition, is it not obvious? Can someone please explain to me with a small test case?

This doesn't work. This works.

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

    Yes bro , I have experienced same issue. Can anyone please explain the above with a small test case ?

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

    consider the case: 4 4 2 1 3

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

      But that is not a valid permutation according to the question. Read it again.

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

        the permutation is [4, 2, 1, 3]. The first 4 is the size, and my line-breaks were eaten. After the first iteration of the number 1 and number two, it is ok that the sequence turns to [1, 4, 2, 3]. In the second iteration, 2 will not be moved because there has been a swap in the first iteration. It gets into trouble when a new iteration of the number 3. 2 and 3 would be swapped if you do not compare them, and the result would be [1, 4, 3, 2].