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

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

<almost-copy-pasted-part>

Привет! В 26.03.2020 17:35 (Московское время) начнётся Codeforces Round 629 (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>

Спасибо Артему Rox Плоткину и Дмитрию _overrated_ Умнову за помощь с тестированием раунда!

UPD: Также спасибо Виталию kuviman Кудасову за тестирование раунда!

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

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

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

We want more contest in this "Corona" era .

Thanks a lot bro.

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

Due to Home Quarantine registration will exceed 22k for sure :)

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

Hope everybody uses Face Mask and keeps distance from others like The Codeforces logo :)

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

We want at least 2 contests per week in this time of pendemic Corona.

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

    Why ? be greedy ... I want at least 7 contests per weak ... (in the rest of the day Ill upsolve the contest)

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

      It's not an easy job to prepare contests and come up with 5-7 problems.

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

        I know ... but many contests are in queue ...

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

          You can attempt to come up with about 12 decent problems (and with 4 hard problems that can make for Div. 1) that people will not scream "shitty mathforces/bruteforces/dataforces/etc.", write a bunch of tests, stress-test that, ask a bunch of testers to test your problems, find corner cases and stress-test again, reject 6 out of said problems, etc.. Writing a contest is NOT easy, and if you are so insistent on having a contest, how about go write yourself one? We will see the quality of your problems.

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

One contest per 3 days will be good for us.

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

CodeForces is making our Quarantine interesting by hosting regular contests...

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

Thank God that coding does not transmit Corona infection :) Thank you very much *-)

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

What can be more interesting work to do in quarantine than solve some classical competitive programming questions set by vovuh and learn from our mistakes that we do in real time contest. Thanks Codeforces.

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

I'm still new on codeforces

Can someone explain what it means that the penalty is 10 minutes ?

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

    In the resulting scoreboard, participants are compared first by the number of solved problems, then by the total penalty time — for every solved problem, it is the time taken to solve it (in minutes) and 10 minutes for every unsuccessful submission on it.

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

      Thank you <3

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

        Just to make it clearer: you won't be penalized 10 minutes of solving time during the contest: you will have full 2 hours to solve the problems regardless of your submissions.

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

          So basically if we have a WA submission it will add up 10 mins to our submission time in the scoreboard right?

          We won't actually have to wait 10 mins to make a submission?

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

            Yes, penalty of 10 minutes is added to your submission time, you don't have to wait for 10 minutes to submit. Do note that TLE is also a rejected submission and is penalised with +10 minutes.

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

vovuh mean div3

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

How do I configure vim like tmwilliam in his YouTube videos? e.g:-font,keybindings,etc.I am a beginniner in vim.

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

Waiting for the moment when i'll be participating unofficially in these rounds :(

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

I just wait for div3 contests :(

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

We want more contest to pass our home quarantine time with coding.

stayhome

staysafe

staywithcoding

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

I think that this contest may turn out to be a Codeforces Server Pressure test (CSP)!

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

Contests these days are of much help to kill time.Many thanks to Codeforces!

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

regular contest with two days gap will be good in current situation...

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

I really love div.3 rounds

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

We need more of this, we ain't got nothing to do on this pandemic

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

I'll 爆杀 in this contest. Hope everyone good luck!

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

Codeforces is Best thing to do in home quarantine.

Stay At Home

Keep Social Distancing.

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

We need more contests during self-isolation))))

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

can we have this website in dark mode? it will be easier on the eyes.

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

Thank god. I'll finally have a break of 2:00 hrs in which I'll not regret my life which I've been doing this whole quarantine

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

just be an expert

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

 Effect of Corona !!

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

I think codeforces should restrict registrations at 25k or something.. Excess load might cause servers to remain down. A good contest for few is better than no contest at all. :/

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

please more contests in this "corona" time live contests feels more competitive than virtual :) ;

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

wish you successful home quarantine...CF Registration amount proves, you are fighting against corona...

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

the number of the participant has come to a new record.

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

OMG 20k participants!!!

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

stay home

stay safe

protect covid-19

I hope we will get the quarantine and isolation related problem.

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

Already 22000+. Today total registration gonna be 24k+

Stay Home. Stay Safe.

Be a Compititive Programmer.

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

Seeing the number of registrations, I already opened m1.codeforces.com XD

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

Wow!! 22000+ Registration!!!
Now Waiting for 23000+

Corona_fact

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

I bet there will long submission queue !!. 23K !! Dayyyummm !!!

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

Has the number of participants broken the record?

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

CF servers can't handle so many participants

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

very weird problem d

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

    It was dp, and I really liked the problem; something unique. I don't think I can explain more, since my own solution was very messy. Hope the pretests were strong.

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

      it can be solved with greedy approach pretty easily too

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

        Could you, please, elaborate? Because I couldn't really think of any approach, at all (just Pupil things :)) — but I am getting better). I tried DP and backtracking, but got lost in the details and couldn't implement them properly.

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

          Ok, so we would like to assign colors in following pattern: 1 2 1 2 1 2.. We will assign same color to all segments with equal numbers in it, so for sequence like this: 3 3 3 1 1 2 4 5 5 the colors would look like this: 1 1 1 2 2 1 2 1 1. Now the only problem is that first and last element can still be different and have same color assigned to it. To fix that we take any segment of length >= 2 and change color of last element in it to to opossite one and recalculate the color array. For previous example it would look like this: 1 1 (2) 1 1 2 1 2 2. In case there is no segment of length >= 2, simply set color of last element to 3. https://codeforces.com/contest/1328/submission/74454901 — my implementation

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

          It was a very hard implementation for me at least lol. First, if there is only one kind of number in the array, answer is 1, so paint all of them as 1.

          Second, if n is even, paint them in alternate colors 1,2,1,2 and it will be correct for every input.

          Third was problematic, answer can be 2 or 3, depending on the number of adjacent elements which are different. If that number is even the answer is again 2, other wise its 3.

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

            For case t=[1,2,3] we need 3 colors [1,2,3] and for t=[1,2,2,3,3] we need 2 colors [1,2,1,2,2]. So your explanation is not true.

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

              1 2 3, if written in a circle have 3 adjacent elements that are different (1 2) (2 3) and (3 1), thus the answer is 3. Sorry for not clearing this, count includes all the adjacent elements including the first and last. Although You are right, it is wrong for other test case like 1 1 2 2 2 2 3, because it says 3 colors are required, but it can be done one 2.

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

anybody else that couldn't participate due to the heavy load on servers?

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

anybody else that couldn't participate due to the heavy load on servers?

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

Can E be solved using LCA?

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

Almost 25K registrations! Really Coronaforces)

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

how to solve D?

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

    I only consider 4 situations:

    1. all elements are the same : (1 color)1 1 1...

    2. the length of the elements is even : (2 colors)1 2 1 2...

    and now we just need to think situations where the length of the elements is odd

    if t[1]==t[n] then: 1. (2 colors)1 2 1 2...

    else if t[1]!=t[n] and at the same time there exist one i(1<=i<=n-1) where t[i]==t[i+1] then:

    1. (2 colors)1 2 1 2...

    2. otherwise: (3 colors)1 2 1 2 ... 3

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

      What if 7 3 3 4 4 4 4 4 . If I am not wrong according to your algorithm, the answer should be: 1 2 1 2 1 2 1 . But here t[n] is not equal to t[1] and they are also adjacent, then how they got same the colors?

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

        since there is one index i satisfy the condition t[i]==t[i+1], we can paint the same color on i and i+1. So for your example, since the first element is equal to the second element, you can paint these elements into 1 1 2 1 2 1 2, and it is correct. I got to go to bad now, if you don't understand somewhere, i will let you know tomorrow :)

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

    Think greedily. Try to use minimum number of colors to color figure 1 upto n-1(you can color these n-1 figures maintaining all constraints using 2 colors only) and then think is you can color figure n with a color already used. If not then give it a new color!!!

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

Is it only I or everyone was facing issues with the speed of loading for codeforces. I submitted 3 mins before the end of the contest but still, it didn't get submitted.

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

    Try using m1.codeforces.com next time, I sent all my submissions from there with no problem (while I couldn't submit sometimes from www.codeforces.com)

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

could you tell me how to slove the problem D by easy algorithm

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

    If you like graphs you can see it is a coloring problem. Your vertices are the different animals and there is an edge between them if they are of a different type and adjacent. Now you want to color this graph, such that all adjacent vertices have different colors. This gives you three cases: 1. If the graph has no edges (ie only one type) you only need one color

    1. The graph is not a cycle, then you need two colors, since you can just color any path as 1212...

    2. The graph is a cycle, then it is important whether it has an odd or a even length (if you are interested how this generalises look up bipartite graphs)

    If the length of the cycle is even, then you can't color it in a 1212...1 fashion, since the first and the last edge would have the same color. Therefore you need three colors and can color it like 1212...23

    If the length of the cycle is odd than you only need two colors and can color it like 1212...2

    I hope that is understandable :)

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

      Or more simply put ; if the graph is non-bipartite ; then print the bipartite coloring.

      If it is bipartite ; it would be because two adjacent vertices get the same color while bipartite coloring ( This is the odd length cycle case ) . Color one of these vertices to some 3rd color ; and then say Yayy! when u receive AC !

      Code

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

    If there is only $$$1$$$ type of animal, then the answer is $$$1$$$ color. We can simply print $$$1$$$ $$$n$$$ times.

    If $$$n$$$ is even then the answer is $$$2$$$. We simply print alternating $$$1 2 1 2 . . .$$$

    So, we are left with the case when $$$n$$$ is odd. If we can find any $$$i$$$ such that $$$type[i]=type[i-1]$$$(cycle included, i.e. $$$type[0]=type[n-1]$$$) then the answer is $$$2$$$, as the parity can be switched. Otherwise, the answer is $$$3$$$.

    To print the colors with answer $$$2$$$, you can alternate $$$1$$$ and $$$2$$$ with the exception of $$$i$$$ where $$$type[i]=type[i-1]$$$. Put that as the same color. This changes the parity.

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

    If all elements are same, answer is 1 If all elements are distinct and number of elements is odd, answer is 3 otherwise answer is 2

    if all are distinct, simply print 1 2 1 2 ... like this otherwise take every segment containing distinct elements and fill it by 1 2 1 2... those are left, give any colour to them

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

    By observation it can be seen max distinct color required will be 3. Now if n is even 1212.. pattern will work if there are more than one number. For all same obvious 1 color will be required. Now for odd n, consider if there are at least 2 contiguous same number in cyclic array in that case color required will be 2 otherwise 3

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

    You can solve D without graphs as well. It can be solved greedily.

    1. If n is even, just print "1 2" n/2 times

    2. If n is odd but a[0] == a[n-1] print "1 2" n/2 times with an extra "1" in the end

    3. If n is odd but there is a point where arr[i] == arr[i-1], then from 0 to i-1 print "1 2" and from i to n-1, print "2 1"

    4. If none is true, print "1 2" n/2 times with an extra "3" in the end

    Corner Case (it was for me): If all are same print "1" n times.

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

Whoever made D is a sadist. T_T

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

Detailed video for F

Here

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

    thanks it was helpful

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

    please can you tell me why using library sorting I am getting TLE but with radix sort it passes my_sub constrain is just n= 2*10^5 so O(nlogn) is fine right the why?

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

      in Java, arrays.sort can run in O(n^2) in some conditions.

      I'm not well aware of how this works in Java, but I heard that can be the case sometimes.

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

I thought I would never complain about that but 101 tests in E did make my submission take a lot of time to be judged :)

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

I don't know whether someone else has experienced this or not but codeforces was taking way too much time to show up. And many times it just says some error has occurred (my connection was good enough). Kind of annoying during the contest.

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

Too much traffic

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

I suprised that with that much number of registrants, the main page still worked faster than m1

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

I've got 403, 503, 504, 502 not once or twice) Who got more 'AC'?

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

(At least)
last three minutes of the contest
the sites were inaccessible
(including the lightweight websites like m1.codeforces.com).

I had no chance to submit my problem D solution.

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

I finally thought I had found all the corner cases for D but it still gave me WA. Are we sure they generated all the possible outputs? xD

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

    I used dp as I didn't need to worry about handling all corner cases explicitly XD (P.S. I couldn't think of any corner cases).

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

    Ok, reading j_peters comment above I just found what I was missing. It was a narrow miss and just because I'm dumb >D My fault

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

    1 2 2 3 Ans 2 colours Check this

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

      Yea, you're right. I missed the fact that you could use any two adjacent of the same type to flip the sequence and use 2 colours, not just the last ones.

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

Second pretest prob D why this answer is wrong ?

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

    Why do you believe it is considered wrong?

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

      Because that's what my code prints, when I submit it show me WA pretest 2!

      Edit

      Sorry my bad I though pretest 2 = query 2.

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

        Are you sure it says pretest2 and not Test 2?? You can look with more detail to where did it fail from your submissions tab.

        EDIT: Oh, ok then, no problem

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

Is this contest rated?

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

Is this contest rated?

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

what the fuck! I can't access the codeforce after submitting A until div3 over! It always show 403 forbidden or log out my account. No other meaning, I'm just bringing up what happened to me.

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

    Use the lightweight mirror sites. Such errors are to be expected in contests with a large number of participants. After all CF isn't a for-profit company, and can't buy up a large amount of servers unless really necessary.

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

vovuh please make it unrated for me or consider my d solution. I submitted this solution at 22:00 butdue to netowrk traffic or i don't what happened hasn't got submitted. I am saying so because my solution was right otherwise I wouldn't requested you(I submitted as soon as connection got back). Please refer to my issue

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

    I had the code for D wrttien with 15 mins to go, but couldn't submit at all. I was finally able to submit in the last minute and it gave wrong answer :(

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

      I submitted at 22:00 but I don't know what happened because of some site error i didn't get submitted. BTW my solution was correct I submitted it without any changes

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

Make the contest unrated because lot of people couldn't submit their solutions :/

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

    The mirror sites worked just fine.

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

    Hi, sorry about it. I'm working on performance improvements. But am I right that m1/m2/m3 worked well most time? I explicitly suggested to use them in case of any technical issues, right?

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

      With a few exceptions towards the beginning, M2 worked fine for me throughout the round.

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

      in Italy we had problems even using the mirror websites :c so i guess it would be better to make it unrated

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

        I even faced that problem

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

        don't ask for making round unrated (under the name of slow servers). The actual reason is that your rating will go down (because you solved only two questions). Even though you are complaining that the server was slow, I see that you have already made a lot of submissions. How many more did you want to make

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

          well, you can even see i got AC with basically the same code (i tried to submit it during the contest, but the website and the mirror1 weren't working) ten minutes later the end of the contest.

          (the other submission in the same minute is an error, i submitted the wrong file)

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

            Then it's your responsibility to check mirror2 and 3 as well. The rounds prepared with so much of hard work cannot be made unrated because of a few people's nuisances. I hope you take that positively

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

      It is already unrated for me, but it was so sad I couldn't submit E. It's good to know about the mirror sites. I didn't know about them.

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

      Honestly the main one worked pretty fine for me..

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

      Faced issues even with M1 website. Was not able to load questions. Had to re-submit code few times. If many people faced such issues , maybe we make this contest unrated ?

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

      M3 worked fine as well

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

      For me all m1,m2,m3 worked just fine !

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

      I used m2 , it worked fine

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

      Nah! I tried both m1 and m2, none worked.

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

      m1 and m2 didn't work.

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

      sir i have no experience using m1,m2 and m3 then , i thought it would free up after one or two reloads but that was not the case,i was logged out around 5-6 times

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

The moment I realized that my 'expert dream' was broken! Btw, how to solve E in the time limit?

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

    Instead of iterating to find kTH ancestor, precompute LCA(using binary lifting) and rest is same what you are doing.

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

    What I understood in your solution that you're trying to get the depth of every node in the tree, then what else? cause I didn't get the idea of the second part of the code after the BFS call

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

      In each query, I make a path from the root to the vertex which has the biggest level. Every vertex in that query or their parent must belong to that path :(

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

    Actually one can evade writing full-fledged LCA at all. To do this, just notice that you are only interested in parents of the marked vertices. Checking whether one node is an ancestor of the other can easily be done if you use time when DFS enters and leaves the node (tin / tout). AFAIK, there were absolutely no problems with TL with this approach.

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

Can someone explain how to solve B? I feel stupid.

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

    Consider position of the left 'b', let that pos be $$$n-p$$$ Then there exist $$$p-1$$$ strings with left 'b' at that position, because you can place the right 'b' at $$$p-1$$$ positions.

    Implement a loop counting the number of these strings with increasing $$$p$$$.

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

vovuh, хороший див 3 раунд) Продолжайте в том же духе.

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

How to use dp in D? I solved using a lot of if else statements

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

    for problem D, my solution was this

    let the continuous elements form a grp,

    if #grps == 1 then all same color

    else if #grps is even then only 2 colors (alternate colors) else if #grps is odd and #grps == n then 3 colors

    else if #grps is odd and #grps < n then we can do with 2 colors only , we just have to color the last element of a continuous grp (of sz > 1) with a color diff from that of the members of the same grp and continue alternating

    but this gave WA on TC2, dont know why

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

    after the contest, i implemented a dp solution and left a lot of comments, check it out if you want

    https://codeforces.com/contest/1328/submission/74505814

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

Could someone help me figure out what is wrong with my submission in Problem E 74478785

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

    An edge from u to v doesn't mean that u is the parent of v if we build the tree from root 1

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

recently all div.1 guys were arrested by police... 'cause this site was underage.

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

Service was not so much bad comparing whith load..

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

Anyone experienced something like this after submitting solutions. HTTP Status 403-Forbidden(Sorry I am not able to upload the image in comments. So here is the link of the screenshot I am talking about: https://pasteboard.co/J0UgDjL.png I submitted my solution for A and C and experienced this screen and assumed that my answer got submitted but it wasn't and it was happening throughout the contest.

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

What's the point of keeping a rated contest when your servers can't handle the load ? The website barely worked for me during the contest. I was getting logged out from time to time and submitting was almost impossible.

Couldn't be more disappointed.

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

I want more contest. It is the best way to spend time!

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

I solved E in O(N+K) (K is the total sum of k_i) using offline querys and dfs. If you guys solved it with O(NlogN) complexity, have a look at my solution :D

https://codeforces.com/contest/1328/submission/74433847

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

To solve E, I used binary lifting technique on the tree. I precomputed for each node $$$log(n)$$$ parents using dfs(same preprocessing which is done for LCA). To process each query, I pick the node with index $$$i$$$ that has maximum depth among the $$$k$$$ nodes which are given in the query then I simply check for any other node in $$$v$$$ if:

-$$$v[j]$$$ is an ancestor of $$$v[i]$$$ on the path from $$$1$$$ to v[i] with distance equal to $$$depth[v[i]]-depth[v[j]]$$$ from $$$v[i]$$$

-$$$v[j]$$$ is the child of the ancestor of $$$v[i]$$$ on the path from $$$1$$$ to $$$v[i]$$$ with distance equal to $$$depth[v[i]]-depth[v[j]]+1$$$ from $$$v[i]$$$

if none of these two conditions is fulfilled then the answer is "NO" and if at least one of these two is fulfilled for all nodes in $$$v$$$ then the answer is "YES" for this query.

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

    This task has a simpler solution.

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

    Online && O(n)

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

    I think that's a bit easier:

    1. Sort all $$$v[i]$$$ by their depth.
    2. Take the deepest one ($$$v[0]$$$) and lift it to the depth of $$$v[1]$$$.
    3. They must either be the same vertex or have the same parent.
    4. Keep lifting $$$v[0]$$$ to all remaining $$$v[i]$$$.
    • »
      »
      »
      4 года назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      Why am I getting a WA on tc 56. Any hints to the testcase.

      Thanks in advance!!

      My Solution

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

      Won't it cause TLE if the tree is "straight" because in that case deepest node will have depth = n so time complexity would be O(m*n) ?

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

        Good question! This is what the binary lifting technique solves (as mentioned by amiratou): for each node, you store its parent, its 2-parent (parent's parent), 4-parent, ..., $$$2^k$$$-parent up to $$$L = \log(n) \approx 19$$$. Then you can jump through the tree in $$$L = O(\log n)$$$ steps for each $$$v[i]$$$.

        The statement guarantees that the total size of queries is under $$$2 \cdot 10^5$$$, so this should work.

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

My rating right now is less than 1600 but it is showing me as unofficial participant in this contest... This is may be because i registered when I was expert... So finally whether i will be considered Official or not in this contest?

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

Giving this div 3 contest for first time on this platform would have been a lot more fun if their web server wouldn't have stopped responded which took the peace of my mind. It took me a lot of time to understand that I have to go to one of those light websites, login again, wait for 3 minutes and refresh the page to see the verdict. It was a total mess.

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

There was problem in submitting code It showed Http error while submission

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

How soon editorial will be because there are a lot of interesting and hard problems?

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

How to solve D?

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

    answer 1 — when all the numbers in the array are the same

    answer 2 — when you have n% 2 = 0 or when you have two consecutive identical elements (you can change the parity, draw there is not difficult))

    answer 3 — everything else (paint the first vertex in color 3, and then alternate 1 2)

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

http://codeforces.com/contest/1328/submission/74484167

Can anyone explain me whats wrong in my solution for D ?

I basically looked for an adjacent pair of equal values. If such pair exists then answer would surely be 2 (or 1). I started giving colors accordingly based on comparision of a value with it's preceding one.

If such pair doesn't exist then answer would either be 2 or 3 depending on whether number of elements is even or odd.

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

Can anyone hack this submission. Not able to find why it is right or wrong :(

Thank You

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

    I did not run any testcases, just went through your code and i think your logic is right.

    You have sorted in decreasing order of levels, and after that for each pair you have checked if their lca is either equal to the latter or its parent. This is what I understood from your code.

    This is correct in my opinion because suppose answer is YES, then it is mandatory that a vertex with greater level lies in subtree of all vertices with level lower than its own or in case a vertex of lower level is replaced by some other element at distance 1, then from it's parent. Since you have sorted in decreasing order so transitive relation will hold within the vertices i.e if u lies in subtree of v with level[u] > level[v] and v in turn lies in subtree of w with level[v] > level[w] then u lies in subtree of with level[u] > level[w] and above condition will hold true.

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

The questions were standard however the server was very slow and had a very bad gateway. I had been trying for logging in for the past 20 minutes and submit however I was not able to do

It would be nice if you make the contest unrated.

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

Why during the contest codeforces has thrown me out of its profile many times and I couldn't open tasks ? Also I couldn't join to m1, m2, or m3 codeforces. Why this bad things happen to me? Who had same problems?

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

This time, the contest was at a very good level. The problem D had the exact amount of difficulty which should be there for creating a margin between participants and it saved the contest from becoming a speedforces :)

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

Anyone knows why https://codeforces.com/contest/1328/submission/74488792 is accepted (Python) and https://codeforces.com/contest/1328/submission/74488483 is not (PyPy) as generally PyPy is faster than Python. Cost me 1 hour...

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

recently police arrested div.1 guys... 'cause the site was underage. p.s. -- i tried submitting problem D solution during last minutes, but site kept on crashing... phew! 24K contestants

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

Conduct contests alternatively on day basis. Quarantine days.

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

MikeMirzayanov, включите пожалуйста HTTPS для зеркал m1. и m3. (на m2. работает). Вдруг мой пароль кто-нибудь перехватит и будет делать неправильные посылки во время раунда?)

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

seems like vovuh prepared these questions for Educational round and it posted as div3 by mistake lol

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

As mentioned in the annoncement that it will be unrated for participants with rating >=1600,but still it is showing me as a trusted participant and also there are lots of expert in official standing. Does anybody know why this is haapening?

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

Can someone get penalized for unsuccessful hack attempt in div 3 contests?

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

i was logged out almost 5-6 times, it was showing bad gateway all the time

and logging in would take another 5-6 min

and this might have happend to many users

https://i.imgur.com/zVqJ4a1.jpg

@codeforces do something about it in future and about this round

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

How to Solve D if it is compulsory to paint the same type of animals with the same color, and we have to minimize the total number of colors used as given in the problem statement.vovuh awoo

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

The server was too slow! I couldn't even read some problems and check my verdict after submissions! I hope Codeforces will fix the issues in future contests because it affects our ratings!

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

1328D - Карусель, карусель --- это радость для нас Долго ждал отправки, примерно минут 6, отправил Ошибку Компиляции, когда решение оказалось правильное, я бы мог успеть сдать ее.

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

Сегодня на раунде у меня (и у многих моих друзей) была проблема. Сервер жутко лагал и на загрузку страницы уходило около 3 минут. При этом мой интернет имеет скорость около 20 Mbps по данным ооклы. Переход на вспомагательные сервера не помагал. Такое началось около 3 недель назад, когда число учатсников резко увеличилось. Также такие лаги только вначале и за 10 минут до конца все достаточно быстро. Можете поставить +, если у Вас было так же, наверное это и увидят.

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

MikeMirzayanov Its not good. I was using m1.codeforces.com during the contest and while solving problem d , no clarification came that two same adjacent species can have different colors too. throughout the contest i was getting wa bcoz of this fact. why no announcement appeared on mirror sites.

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

    It was pretty clear from the problem statement itself that two same and adjacent species could have different colours. You should maybe try and read the problem carefully than complain.

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

    I think you are wrong, as many participants (it is just my opinion). This issue is even considered in examples and you just didn't see it as many of the participants who asks us about this. The second test case of the example: $$$t = [1, 2, 2, 1, 2, 2]$$$, $$$c = [2, 1, 2, 1, 2, 1]$$$. $$$t_5 = t_6$$$ and $$$c_5 \ne c_6$$$.

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

      vovuh My complain is only that, why updates are not visible on mirror sites. I am not complaining about the question. But if new updates would have appeared then it would be good for participants who use mirror sites for faster access. MikeMirzayanov

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

        Okay, if you complain only about this, then I agree with you that notifications and clarifications should be allowed in mirrors because it's unfair and it's an advantage for other participants. But don't forget the initial target of these mirrors: they were created to allow users read and solve problems almost offline even if the main site doesn't respond (afaik). I don't sure but hope this issue will be fixed.

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

          Yes, one might get the right approach or atleast understand what the question is really asking, where sometimes people face difficulties due to some lack of clarifications. so if updates are also appear on mirror sites then its good. leave it, no issue. i will open one main tab of cf.com aside of mirror site, to get any notifications. thanks for reply.

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

            I even didn't notice there was a notification for that problem. This failure could be a good experience for future contests. Personally, I won't start thinking on a problem, let alone coding, if I don't understand every corner of a problem statement.

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

Screenshot-6f034c10bf8721386.png

Why am I unofficial??? MikeMirzayanov vovuh

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

Sadly, a lot of O(n^2) and O(k) solutions are passing for B i think

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

    I think no , in worst-case : n = 10^5 or k = 10^9 ,So: if O(n^2) = 10^10 OR if O(k) = 10^9 this will give TLE that if also T = 1 , Let's say if T = 10^4 and n = 10^5 in evey test-case so complexity will be equal : 10^10 * 10^4 = 10^14 this absolutely TLE :). So i think every solution O(n^2) or O(k) if pass in pretests will Fail in final test.

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

How to solve Problem F using DP?

Thanks!

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

How to solve C ?? idea needed

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

    We know the following:

    $$$0 = (0+0)\mod 3$$$

    $$$1 = (0 +1)\mod 3$$$

    $$$2 = (1+1)\mod 3$$$ or $$$ (0+2)\mod{3}$$$

    We loop $$$i$$$ from $$$0$$$ to $$$n-1$$$:

    For $$$c[i]=0$$$: we simply append $$$0$$$ to both a and b.

    For $$$c[i]=1$$$: we append $$$0$$$ and $$$1$$$ to $$$a$$$ and $$$b$$$ respectively. After doing this the first time, we would always have $$$a>b$$$, so we append the reverse i.e. $$$1$$$ and $$$0$$$ to $$$a$$$ and $$$b$$$ respectively. This minimises $$$a$$$, the maximum of the two.

    For $$$c[i]=2$$$: we append $$$0$$$ and $$$2$$$ to $$$a$$$ and $$$b$$$ respectively, once we have encountered $$$c[j]=1$$$. Otherwise, we simply append $$$1$$$ to both $$$a$$$ and $$$b$$$. We can see this easily if we take a number which has no $$$1$$$. We would try to distribute $$$2$$$ evenly, as we want to minimize the maximum.

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

Can we Solve D question using DP ? If so, how?

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

    Yes, I used dp.

    I colored the last element of the array $$$1$$$. Then, I start from index $$$0$$$ to $$$n - 2$$$ (not to $$$n - 1$$$ because it's already been set as color $$$1$$$).

    Note that the current color should differ from the previous one. So we can use dp[previous color][index in array]. One more consideration is that color of element $$$n - 2$$$ should differ from color $$$1$$$, which is the color of element $$$n - 1$$$.

    Code: 74462353

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

      Hi beginner1010 Thanks for the code. I was also doing the similar thing with same logic and dp states. I got stuck in getting the path though while calculating it directly in recusrive function.

      Can you tell me why is this wrong? 74503627

      Anyways, Thanks a lot:)

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

My solution for Question D without using Graphs and DP.

https://codeforces.com/contest/1328/submission/74499296

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

Need idea for B , i got TLE using stl next_permutation.

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

    You cannot use next_perm function as it will calculate n*n perms.

    you simply need to find positions of both the b's.

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

solving these isn't hard, solving under 2 hours is. tips please( except practice )

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

Is there any other way to solve E rather than LCA?? Can somebody please help with what is the problem in this approach,, Link : https://ide.geeksforgeeks.org/jws6KpkplH

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

    Lets say what len[i] is length from root to i. We have some nodes in query, lets sort they by their len and group by this len in some map<int, vector> sort_by_len. lets say current_root — root of lasts nodes. Go through the sort_by_len and say, what if nodes with the same len have different parent we don't have answer. Of course if it is a root of tree we need to update current_root = 0; If they have the same parent = current_parent, if we dont have current_root we need update it = current_parent, in another case we need to say what this current_parent is child of current_root (we can do it using tin and fup time in tree in O(1)). In case if it isn't we don't have answer. And update current_root.

    Link: http://codeforces.com/contest/1328/submission/74462201

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

    Well I wasn't able to understand your code. But indeed you can solve it in O(nlogn) using dfs. There is another version of DFS, where you store arrival and departure time of every node. Search for it. 1 For answering every query, just sort parent of all vertices with increasing depth. (Depth is a distance of node from root that can be calculated using dfs and parent too). 2 Now for each vertex let's say v, check if arrival time is moe than or equal to vertex u and departure time is less than Equal to vertex u. (Here is the first vertex vertex in the sorted list of vertices) 3 If not then answer is NO else it's YES. :)

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

i had an issue at problem C usually i use Kotlin for my submissions i had TLE at test case 5 i made another submission using same code but in java this time and i got an ac

the kotlin sub : https://codeforces.com/contest/1328/submission/74481945 the java sub : https://codeforces.com/contest/1328/submission/74513383

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

More div. 3 contest pls ~.~

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

Admins, please check out these two submissions: Submission 1 Submission 2

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

D. Carousel The expression "one right after another" is difficult for non-English speakers to understand. I don't know if it is good or bad to color c = [1,2,1,2] for t = [1,2,3,4].

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

    The expression means no two distinct adjacent elements of array t can be of same color while the array being cyclic in nature. Your array c satisfies that condition with minimum distinct colors hence it's good to color t with c.

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

      Thank you. If the word "adjacent" is in the problem sentence like this, I think I was not at a loss.

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

what is the penalty system for hack in this round?

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

    mkawa2 the rule is you hack someone's solution and they get their rank degraded so at last you get your rank improved.

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

In the time of Home Quarantine anyone who is going to every platform and looking for next contest dates can simply use THIS WEBSITE to know about all ongoing and upcoming contests :)

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

Can anyone tell me that now I am Specialist and why am I still unofficial in Div. 3?

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

need help!! i'm not able to submit the code in practice .....it shows the message 'practice only allowed for finished and unfrozen contests'.

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

Can anyone tell me why am I still unofficial in yesterday's Div. 3 even though I am Specialist?

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

Can anyone tell me why am I still unofficial in yesterday's Div. 3 even though I am Specialist?

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

Take a look at these submissions which were hacked by the same person. 74455963 74447150

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

To not keep you waiting, the ratings updated preliminarily. In a few hours, I will remove the cheaters, fix wrong division cases and update ratings them again!

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

    is there an automated system to remove cheaters or you have to do it by hand?

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

    I was Specialist at the start of yesterday's Div.3 contest and still I am unofficial..can you tell me why?

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

    the same problem for me, I should not be a participant, I was an expert before the contest.

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

O(n) Pypy2 solution TLEs. Link: https://codeforces.com/contest/1328/submission/74427464

Same solution ACs when submitted in Python2. Can anyone explain why?

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

Wasn't this round unrated for 1600+ people? I saw some experts rating got changed .

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

Finally became Expert on Codeforces !!

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

Is there a contest before the April Fools Day? So happy to see more contests!

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

My solution got hacked in this contest for C problem(TLE) 74438213 and when i submitted same solution later 74557117 it got accepted by online judge. I want to know the reason behind this MikeMirzayanov and vovuh. Though my solution has complexity of O(n).

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

I was rated for yesterday's Div. 3 contest despite having 1600 rating. Would it be possible for me to be unrated? I assume I was marked as an official participant due to my rating recently being changed to 1600.

Thanks!

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

My submission for Ternary XOR got TLE in test case 17. Can anyone explain why? Submission- https://codeforces.com/contest/1328/submission/74446725

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

    AC with couple I/O optimizations and C++ 17. However 2 ms below the TL. Sumbission

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

      I got TLE in system test case for these two lines? Sad thing. But thank you so much

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

        I added two lines in main and changed your "endl" to "\n" (it's faster, AFAIK, but I've never benchmarked.

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

    String compare takes O(string size) time. That's why overall complexity for your code is n*(n+1)/2; which is too big.

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

Why did I show a 76-point increase yesterday after participating in the game, and today everything about the game was gone, the score changed back to the original, no news was received, and even the record of the competition disappeared

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

who is the best hacker of this round ?

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

I was rated for the contest and become a specialist. But now when enter codeforce today, I wonder that my rating is gone. I am unrated again. why? why did it happen? @admin please fix it.

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

why the contest is rated for some people are blue (expert) like ruban the rating was 1602 and should be unrated and got +48 and the rating is 1650 and it's not unofficial

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

    why do you care? what do you care? I think that the administrators of codeforces will figure it out for themselves

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

iam getting wrong answer in test 5(testcase-92) for tree query...here is the link to my solution.

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

I think CF-Predictor is predicting wrong rating change now-days due to large partcipation.

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

when the ratings will return for this contest?

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

MikeMirzayanov could you please inform us when the ratings for the latest Div3 contest would be returned?, as it has been a long time since the ratings disappeared..Sorry for disturbing..

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

When will the rating change return?We have waited for a long time!

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

IS THIS UNRATED??

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

Are rating changes revoked by Codeforces? Earlier it showed on the profile page. Now it shows the one-contest old ratings.

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

Is the contest unrated?

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

I registered for this round when I was a specialist, so it was supposed to be rated for me. But when the rating changes rolled back, my participation status was changed to unofficial (and ratings didn't change). I have seen that the participation status depends on the rating during registration, but I was made 'out of competition' after the contest was over. What should I do?

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

Just stay at your home and start coding, better for you & your family and your society. **** ****

I HOPE EVERYONE TO HAVE SAFE LIFE.