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

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

<too-old-joke-about-copy-paste>

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

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

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

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

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

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

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

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

Удачи!

</too-old-joke-about-copy-paste>

UPD: Также спасибо infinitepro за помощь с условиями и тестирование раунда!

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

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

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

will it be rated??

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

Third unrated round for me in a row :(

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

Monogon contest again got rescheduled :(

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

    It's good that it got rescheduled. Would have been sad if it became unrated like the previous two rounds.

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

I think they are running this round because they think there will not be a crash and an infinite queue. looking forward to it

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

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

Codeforces is my new School ... teaching me and hosting Contest :XD Thanks a lot CodeForces!!

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

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

"the round will be rated for you." Hope this time,,, this line will be true for me..Btw Thanks for your hard work..

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

Deleted

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

Hopefully this wont be unrated !!

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

I was eagerly waiting for the announcement :)

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

Let's all pray for smooth conduction of this round.

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

It was better make a test round before real contest :D

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

This will be my first ever time competing.. any pointers?

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

Situation or system in last 2 rounds.

hope all will be fine this time :)

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

Why there is unusual time for round 657 ?..

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

    May be authors comfortable with that time.

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

      Codeforces contest time are generally xx:05 or xx:35 according to GMT. But that rounds scheduled at 09:00 GMT(not 09:05). So that i assume that round is tied with some other contest(may be some onsite contest).

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

</too-old-joke-about-copy-paste> not too old for me :D

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

To qualify as a trusted participants of the third division, you must:

  • take part in at least two rated rounds (and solve at least one problem in each of them),
  • do not have a point of >>> 1900 <<< or higher in the rating.

I believe this is incorrect :)

Edit: Nevermind, just noticed it's the same in previous rounds. There's a different limit for being a trusted participant and being ranked. Sorry for the noise.

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

Hoping that this contest goes on smoothly _____

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

Who could tell me how to remove or report that comment?so dirty..

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

i'm coming back to this site after a break of 3+ years. so i'm new to this "12-hour open hacks" system.

firstly, is it something new? or has it been a regular thing in contests recently?
also, does it mean there will be a kind of "hacking phase" which lasts for 12hrs after the 2-hour "coding phase" has ended?

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +21 Проголосовать: не нравится
    1. It's a regular thing for div.3 and Educational Rounds.

    2. Yes.

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

      oh this is new for me ... i guess we would need to solve the problem (or atleast, pass the Pretests) in order to hack other participants' solutions?

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

        Nope. You can hack any problem, even if you didn't solve it.

        What's more, sources can be copied for local test.

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

    dolphins returning to Italy and footballers returning to CodeForces, Cool!

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

Hoping positive delta change for all :p

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

I believe there should be a half-hour unrated short contest some time before the actual contest, to test the system's current load handling capacity.

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

As a tester, I won't say anything, since you already know how good vovuh contests are!

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

Hope atleast first problem do not take time.

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

really excited for this contest. I just hope it doesn't get ruined unlike past few contests. Looking forward to learn a lot from vovuh's tasks.

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

why is the time extended 15 min?

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

Good luck and high rating to everyone! :)

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

Hey, I don't think this is right:

  • do not have a point of >>1900<< or higher in the rating.

Although you can find this sentence after it:

if your rating is less than >>1600<<, then the round will be rated for you.

I think this may puzzle those people who are new and without any experiences before in Codeforces.

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

Seems more like a Div2 than Div3

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

Great contest, thanks a lot for this, now I see what vovuh hype was about.

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

Deleted
Just realized 2^26 is more than 200000 lol the meme is pointless

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

    living in a country with a different number of alphabets surely make you confuse

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

how to solve question D???????????????

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

    Just brute force with recursion.

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

      what will be the time complexiy in that case

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

        O(2^logn) i guess

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

          Simple bruteforce . set l=0 , r=n-1 , mid=(l+r)/2 , at each moment you can either change range [l,mid] to current character or change [mid,r] ; Time complexity : O(2^log2(n)+26n) which is O(n) Ps : O(26n) to compute prefix sums of occurences of each character .

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

          O(2^logn)=O(n)

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

          With every time using "count", it should be O(n*2^logn) which is equal to O(n^2) right?

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

            Actually length of string is also halved each time. It could have been precalculated,it thinked this way also, but realized that count within solve() is better in term of time.

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

    Divide and Conquer, complexity should be O(n), because each character would be counted at most twice. (I am not sure about the complexity part tho)

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

      yes, it´s $$$O(n)$$$. Look: let $$$T(n)$$$ be the amount of operations for an array of length $$$n$$$.

      $$$T(n) = 2\cdot T(\frac n 2) + O(1)$$$, for $$$n > 1$$$.

      $$$T(1) = O(1)$$$.

      if you solve this: you´ll get that $$$T(n) = O(n)$$$

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

My solutions (untested, but overall ideas should be right):

A
B
C
D
E
F
G
  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    in D do you need the prefix sum? since it will iterate in ln(n) anyway?

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

      I did D without prefix sum

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

      no, it's not needed (although I used it), look:


      int cost(int i, int j, char c){ int res = 0; while(i <= j) res += (s[i++] != c); return res; } int solution(int i, int j, char c){ if(i == j) return s[i] != c; int mid = (l+r)/2; int s1 = solution(i, mid, c+1) + cost(mid+1, j, c); int s2 = solution(mid+1, j, c+1) + cost(i, mid, c); return min(s1, s2); } /// inside main() cout << solution(1,n);

      This has complexity $$$O(n\cdot \log n)$$$, so it is fine. If you want to do it linearly, use a prefix sum to compute the cost.

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

    is DP was necessary in question D or normal recursion will work

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

      Bruteforce recursion works in just 30ms

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

      Actually, simple recursion does work. Oops.

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

        I am not understanding why my solution to D is giving TLE when I don't use s.substr() and instead pass the limits in the function(Link to submission) and gets accepted when I pass the substring to the function(Link to submission). Can anyone tell me the reason for it?

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

          Passing a string to a function passes it as a copy if you don't take the reference as the attribute and hence it leads to a O(n^2*log(n)) solution which is TLE. Instead, when you pass the substring, it is of the same order as the number of operations in your for loop and the complexity is not affected. You can instead do:

          int func(string &s,int st,int ed,char c)

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

            Thanks!

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

            Thanks sayam! I had the same doubt!I even used prefix sum still I got TLE, was unable to understand the issue.

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

            Can you please elaborate?

            I got TLE on my first submission which i thought was having O(2*logn) as time complexity, after reading your comment i just changed (string s) to (string &s) and boooom the sol got accepted :(

            Doesn't that change only affect the space complexity? How time complexity is getting affected?

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

              creating a copy of a string of length n takes O(n) time and O(n) extra space. (this happens if you call by value) which when done over n times gives time complexity O(n^2).

              & operator in parameter name helps it to pass by reference, (as if using the same string but with a different name) so no time or space required.

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

      Normal recursion will work

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

    For D you can also try every possibility of the good array and find the minimum answer from all possibility. The total possible good array will be n

    Solution

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

      How did you come up with the number of good arrays for a given n? I thought there is only n good arrays for a given n...

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

        Yeah! Thank you for pointing out. I just recalculated, It should be n. My math sucks.

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

    I used the local minimum approach on C but getting WA on test 876 pls help

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

Was G component wise 2-SAT or there is a easier approach to it?

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

    The easier approach is just bipartite coloring. You just need to build a bit special graph to apply it.

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

That was an amazing contest! Thanks Vovuh

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

    Its Problem E I think. Also it shattered me when I cam to know that a good problem can be googled easily.

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

    Ohhkk.. So whosoever read that article just had to implement it.

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

Is it me or the contest was at a bit higher level than usual Div3?

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

This can help you with first 4 problems. https://docs.google.com/document/d/1Fq4UAJBh9Tn48hiF6bLzwvl7ce5XikqWeFmFfw1Q0OE/edit?usp=sharing

Help me with the last 3 problems.

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

How to solve E ?

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

G was implementation heavy i believe.

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

Okay , my rating got fucked up again anc I need a quick editorial now.

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

My Solution to C , i try to provide a proof of the solution too . Hope You like It.

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

in D I forgot to call the string by reference and got one TLE omg

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

    Just realized what I was doing wrong after reading your comment. Big facepalm! I usually always pass things by reference.... F

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

      And here I am trying to use DP, thinking my solution is too slow instead of passing string by reference :(

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

Did anyone solve F with dp on trees + rerooting technique ?

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

I think there was typo while naming the round It should be Codeforces Round#656(Div 2)

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

https://mirror.codeforces.com/contest/1385/submission/87160668

Can anyone tell me what's wrong here? I guess the complexity O(n),still giving TLE.

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

Is there anyone who solved E without topological sort? I tried with dfs but getting WA on test 2.

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

    I did. First check for cycle with directed edges. If not found you can always direct the undirected edges and still have an acyclic graph. I had two adjacency lists, one for directed edges and the other for undirected edges. Have 3 states each for visited, completed and not visited separately. In a dfs run from a vertex, if any of the undirected edge is directed to a completed vertex, then this can never be a part of the cycle. So remove this vertex from the adjacency list of the completed vertex. Code : 87141053

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

D is annoying complecated statement. Once understood the defintions it is "implement what statement says".

Not sure why such problem is in the set. From my point of view the most idiotic kind. It is not more than decypher obfuscated problem statement.

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

Good contest indeed!

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

Tasks were interesting, more div 2 than div 3 in my opinion.

Only thing I do not like, that you are allowing more than two occurrences of same element in $$$G$$$. That is not funny joke.

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

    Yep, I thought it could be stupid because it is the only case when $$$-1$$$ appears, but now it's too late to change anything.

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

      Problem G test case:

      5
      5 3 5 1 4
      1 2 3 2 4
      

      ans:

      2
      1 2
      

      why it is wrong? help please :)

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

        If you swap columns $$$1$$$ and $$$2$$$, you get $$$a_1 = [1, 2, 5, 1, 4]$$$ and $$$a_2 = [5, 3, 3, 2, 4]$$$. Both rows are not permutations.

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

          see the other way, I am swapping 5 from 1st with 2 from 2nd i.e [2,3,5,1,4] n [1,5,3,2,4]

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

            You are not allowed to perform such operations. The element can't change its initial column.

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

    Wasn't that included in the samples?

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

      Yeah, you are right. I have noticed it after contest. I had another case when I expected ans to be $$$-1$$$ (and that situation is impossible, except case where more than two numbers are equal). I need to check samples more careful.

      Anyway, still it is not funny :)

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

What is the proof of E sol.?

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

    Consider an undirected edge $$$(u,v)$$$. Suppose making this edge directed, gives rise to a cyclic graph, then both the directed edges $$$(u,v)$$$ and $$$(v,u)$$$ must belong to some cycle with the directed edges. But in this case, even after removing the undirected edge, the graph is still cyclic. Otherwise, either $$$(u,v)$$$ or $$$(v,u)$$$ (or both) could have maintained the acyclicity. Thus when the graph is acyclic with the directed edges, we can always direct the undirected edges and still get a $$$DAG$$$.

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

can someone till me the difference between this submission 87132940 and that 87161171 I thought that they are the same idea, but I don't know why the first submission failed

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

My solutions :

A. Iterate on all possible triplets from set of numbers 1, x, y, z, 1e9 for each a,b,c, and check if a given triplet exists that satisfies the given condition

B. Take only first occurrences of each number while iterating make the permutation

C. One obvious way to generate array c is to always take minimum end element of the array and generate the final array. So as we move right, we get a smaller array and better odds to generate a valid array c. So binary search on the answer from range(0,n-1) and check if array C formed by above method is correct.

D. To build the answer for (1,n,c), we obviously need the answers for the range (1,n/2,c+1) as well as for (n/2+1,n,c+1), so either use memoization dp or just build the answer for each character for a range recursively, ie, for (1,n) for 26 characters, build the answer for (1,n/2) and (n/2+1,n) for 26 characters each. Then generate answer for each character for (1,n) using conditions described in the question.

E. An observation was that if there is no cycle in directed graph using only directed edges, then all other edges can be directed to avoid a cycle. One such orientation is to direct edges on the basis of topological sort. So check if graph built using only directed edges contains cycle, and if it doesn't ,generate a topological sort from that, and order edge nodes on the basis of topological order.

F. An observation was that if at some time we have k leaves for a node, or k leaves for many nodes, it won't affect the answer's maximum if we decide to do operation on any such valid node because if leaves of that node stay, then that node is as good as unusable node at any point in the future. So a possible algorithm is to take the node with highest leaf count, remove (cnt — cnt mod k) leaves and hence do floor(cnt/k) operations, where cnt is the count of leaves attached to that node. We can do this by maintaining the adjacency list, adjacent leaf nodes list, and leaf frequency list and a set to store the node with highest leaf count and updating these as we pop elements from the set.

G. I did this using bipartite graphs. First we check if each value from 1 to n has exact frequency of 2 for making 2 valid permutations. If so, build a bipartite graph where nodes are pair of (row,column) for each value. 2 nodes are in disjoint parts(of bipartite graph) or have edge in between if they are either in the same column or have the same value. Build this graph, and check if it is bipartite. If it is, then an answer exists. To find the optimal answer , let s just find the cost for a connected component. It is the minimum of the cost of moving one disjoint part of the component to row 1 and the adjacent part to row 2, and vice versa. That is where implementation might become a bit heavy.The total cost is the sum of cost for each component.

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

    master_noobie How do we prove this observation for E?

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

      Consider the graph with only the directed edges. If there is a cycle, then obviously we can't remove it, so the answer is NO.

      If there isn't a cycle, then there exists a topological ordering of the nodes, that is an array $$$pos$$$ such that if there is a path from node $$$u$$$ to node $$$v$$$, $$$pos[u] < pos[v]$$$.

      Now consider an undirected edge $$$(x, y)$$$ and assume WLOG that $$$pos[x] < pos[y]$$$. Then if we direct the edge from $$$x$$$ to $$$y$$$ and add it to the graph, the topological order of the new graph remains the same as the topological order of the old graph (there are a few cases here I guess, but nothing difficult). Thus, since the order still exists, there cannot be a cycle in the new graph. Thus after directing and adding all the undirected edges in this way, the resulting graph will have no cycles.

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

Thanks for such a nice problemset vovuh :)

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

Here are my solution ideas for all problems if you are waiting for the editorial. (video published after the contest ended of course). It is possible that my idea for F isn't actually right; I don't have a proof for it yet.

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

Why is this submission wrong? 87125487 It passes the tests if I clear the dp array, but it should not affect the answer, if I understand resize() correctly.

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

    Resize does not reset the existing values in a vector. It only expands/shrinks the tail to match the new size.

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

      Thank you, I found the bug. I kinda knew that, but for some reason thought that it only concerns values (not data structures, and new values are initialized, but old values stay the same), but vector is also a value. This bug has ruined several contests for me, and I am very glad I finally tracked it down.

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

I will be adding detailed video editorials with appropriate proofs and implementation on my YT channel:
Editorial for problem D: https://youtu.be/9gVpnosPKec

I will also add for A,B,C and E.
Enjoy watching!

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

I will be adding detailed editorials for CF problems with appropriate proofs and implementations on my YT channel

Editorial for problem C: https://youtu.be/vjRHaZb16bU
Editorial for problem D: https://youtu.be/9gVpnosPKec
Editorial for problem E: https://youtu.be/yn6ZPaqwlso

Enjoy watching!!

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

Thanks for the contest, in Problem D — I did learn that passing strings to recursive function can lead to TLE, so pass reference :(

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

Wait is it unrated??? when did it change to unrated???

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

Very interesting tasks!! Almost every task required something new. Now after seeing solutions of E, i am awestruck with the use of topological sort in it.

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

can anyone tell me whats wrong with my code? Problem C https://mirror.codeforces.com/contest/1385/submission/87169051

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

can someone explain why i am getting TLE in problem D here is link to my code https://mirror.codeforces.com/contest/1385/submission/87163991)

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

vovuh nooinenoojno awoo

d_rushabh is hacking the solutions that he submitted using his fake accounts. Remove him from the contest.

+adding similar contestant: mihirarora

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

    I think he doesen't know that in div. 3 rounds you don't get points by hacking. If he hack all his alts, I guess there is no problem then

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

I have tried to explain my approach for E , basically explaining the code for topological sort .

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

Can anyone tell what is this code wrong for solution of Problem B? I take all integers in permutation1 until next integer of permutation2 appears. But it throws wrong ans.

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

    There is a possibility that when you increase the value of j, it might become more than the last index of B and the value at that memory location might be equal to the next A[i], in this situation your code will skip that value and might give you the wrong permutation.

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

8 bbaaddcc explain this pls

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

Isn't it strange today's contest E question is my doubt post on codeforces only that has been answered ? https://mirror.codeforces.com/blog/entry/68765

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

    It is imposible to check your problems against all other problems in the world, especially if they weren't actually published in an OJ. Of course this shouldn't happen, but in general it is common for easy problems to collide with each other.

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

Can somebody help me in question E .My code is giving error on test case 2 and the error says jury has an answer but your code doesn't .Pls help link to my code https://mirror.codeforces.com/contest/1385/my

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

    Please use the correct link to your submission! I'm not sure what the issue is yet, but judging from my experience with this question, have you cleared the adjacent matrix for the vertices after each test case? That might have caused your code to give a wrong answer on testcase 2.

    My code is here 87179787 (I hope it helps)!

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

Can anyone please help me on this in C problem? Getting RTE on Test 2.

https://mirror.codeforces.com/contest/1385/submission/87169468

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

    I looked at your submission. For starters, I think you have overcomplicated your code. However, here is why you're getting your run time error.

    Try running this as a test case.

    1
    2
    4 3
    

    If you dry run your code, in the second iteration of your while loop, you'll see that, you have popped all elements from your deque, but you're still running the loop and comparing the elements, which throws an exception.

    I have not corrected your code, but a simple approach that will help you is this. The solution idea is to look for a suffix of the array such that it's one of the three types. 1. All numbers are non-decreasing 2. All numbers are non-increasing 3. At first the numbers are non-decreasing, then they are non-increasing.

    Among all such suffixes, you needed to find the one that had largest length (ensuring smallest prefix to be removed). I did it in a simpler way. See it here 87122310

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

Again div3 with the same difficulty as div2 bruh.

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

    Really? I can't think of making the problems easier than this without compromising the quality of contest. If anything, its the div 2 rounds that seem more like div 3 nowadays.

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

Div2.5

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

Rated.

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

Hello i'm newbie, can someone explain why is my contest doesn't get rated?

This is not my first contest, I've participate more than 2 contest. I solved atleast 1 problems for each contest.

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

    The past contest you attended became unrated, due to server problems. The rating for this contest will get updated in some time.

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

This was my first RATED contest. I'm a new user. I participated in last two contest Codeforces Round #655 (Div. 2) and Educational Codeforces Round 91 (Rated for Div. 2), but somehow both the contest got unrated. So in this #656 Contest I solved 3 question. Few moments ago I got my rating, which surprised me.....only 460. How can this be possible? Please help me understanding this.

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

A and B should have been swapped :P

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

Edit : Wrong Post

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

edit: commented on wrong post

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

Hello, I got quetion, in the problem D the test case include el case asdfghjk and the answer is 7, but the answer shouldn't be 6?. The string of the answer would be ddddgfee