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

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

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

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

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

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

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

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

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

Спасибо MikeMirzayanov за платформы, помощь с идеями для задач и координацией нашей работы. Задачи были придуманы и написаны командой Университета ИТМО: MikeMirzayanov, myav, Aris, Gornak40, senjougaharin и Vladosiya.

Также большое спасибо: pavlekn, KoT_OsKaR, natalina, vladmart, Phantom_Performer, Be_dos, ctraxxd, diskoteka, lunchbox, kzyKT, MODDI, molney, FEDIKUS, Nickir, 74TrAkToR, kamishogun, KseniaShk, Sokol080808, NintsiChkhaidze, Asad5059, heon за тестирование раунда и весьма полезные замечания. Список тестеров будет пополняться.

Всем удачи!

UPD: Разбор

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

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

Hoping for the delta ++ ^..^

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

Hoping for positive delta

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

Finally, an unrated div3 for me!

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

Excited !!

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

Wishing a good div for one piece fans

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

wishing a good div for one piece fans

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

    haha, I couldn't solve D and E but F was pretty easy. Hoping +ve delta

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

      Can you give me a hint?

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

        For problem F

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

        here are few observations, 1. Since we can only choose dancers with different levels and exactly m dancers with each pairwise dancers level difference be be strictly less than m.

        First, Sort the array then store count of each different level dancer, second, use unique of array to get only unique level dancers, then iterate over it now for dancer i with ai level can be paired with dancers having level less than ai+m, so in the same array look if i+m-1 < n and a[i+m-1]-a[i] <m , n is the unique dancers, and if above condition is true then we can have all pairs that exist from number of dancers of a[i] level * number of dancers with a[i+1] level uptill number of dancers with a[i+m-1] level this can be achieved by using prefix product array.

        hope this help, my submission

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

          nice, thanks bro. I thought that the difference was between each 2 adjacent numbers in the subsequence idk why

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

    I'll need a timeskip to solve D

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

As a tester, i'm highly recommend to participate in this round. I think, one of the best div.3 round.

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

Waiting for testers comments :)

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

In my opinion every round goes good but when some unrated participants make fake id's and participate in the contest, the contest is ruined for programmers like us i hope we don't face any external problem in this contest .Good luck to all!!

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

Please provide hints and proofs for the problems along with editorials It helps in upsolving and understanding concepts for beginners instead of directly jumping to solutions :)

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

Lets make our delta ++ ;)

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

hope to be a wonderful round and end up with a big postive delta:)

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

Hopefully this round will help me(adding positive delta) to become expert. Good luck everyone..

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

Good luck!

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

if i do not register for contest and do not solve any single sum, can i still hack others solutions ? And will there be any rating decrease for unsuccessful hacks if i dont give the contest ?

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

    yes and no

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

    Div3 or educational round has no hacking points.You can hack any other solutions. See for details Hacking GUID

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

    No, you cannot participate in hacking others' solutions in a contest if you are not registered for the contest and have not attempted any of the problems yourself. Additionally, if you do not participate in the contest or attempt any problems, you will not receive a rating change, whether for successful or unsuccessful hacks. Rating changes are calculated based on your performance in the contest itself.

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

Previous Div 3 contest saw a lot of Pupils and Specialists getting promoted to Expert's and some even to a Candidate Master's status. Wishing luck to all the participants for the round! Hoping to have a fair round.

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

Думаю будет отличный раунд! Всем удачи!

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

As a tester, I would highly recommend this round! The problems are very interesting with neat solutions! Statements are also pretty short!

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

summoning +ve deltassss (please)

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

who is MikeMirzayanov? CF community tell me about the living legend.

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

my 6th round, hoping to become pupil this time

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

Hoping for a smooth contest and great problems.

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

As a tester, I would suggest participating in the contest :) Problems are cool and challenging.

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

Feeling this will be an hard round

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

As AI Bard, I will be participating in this round. Hey newbies, it would be a shame if you lose to Bard.

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

      FREEDOM! I will give, if no one before.

      P.S: what we do is erasing 'L' in 'LLM' and inserting instead 'G'.

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

    How to lose to someone who has not solved a single problem and have 3 incorrect submissions in a contest?

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

Missin theses Div3 's rounds, looking forward to enhance my knowledge :")

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

XD

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

Hoping for a balanced and interesting problemset :)

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

Hoping for no cheats :{

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

Hoping to score a chance to AK this competition!

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

nice contest

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

If you want to watch me spending 15 minutes on problem D, here is a screencast. (It is unable to be viewed until the end of the round.)

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

div4 or div3 contest?

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

Really good contest to return to Codeforces after a month of exams! Looks like it will also take me back to specialist :) I didn't have time to do F, was it some nCr + binary search?

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

    Not really (at least not my solution). The observation was that since the difference between any two levels is strictly less than m, then the selected dancers must form a permutation of [a, a+1, ..., a+m-1] for some a. I just did a sliding window with modular inverse on each contiguous range with length greater than or equal to m, using a map to keep track of occurrences.

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

      Hm, my initial idea was to sort the array and binary search the greatest possible value that could be included and then add how many ways you could choose m-2 numbers from the set of numbers between the first number and the greater number to the asnwer.

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

      Similar here. But I sorted the array, remove duplicates then do sliding window of size m.

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

        Same here. Except for I didn't have time to write modular inverse:(( Would've become expert. Here's my submission: 206546474

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

          i just made the logic quickly that i have to cnt the frequency and store in the vector of pair but i couldn't remember i have to change size also i was looping for n all the time after 40 minutes I realized then suddenly change the size and submitted at the last sec then realized didn't comment the extra printing variables and then contest is over and submitted after a sec of the contest and accepted :)

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

            That is why it is advisable to use a debugging header template or use cerr instead of cout for debugging.

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

Am i the only one who struggled with recursion in E?

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

    I did a simple DFS + handshaking lemma to make for easy counting

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

      How did you use the handshaking lemma. Isn't this lemma for undirected graphs?

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

        I'm not really sure, I just observed that any component with edges equal to vertices must be counted. So I just used DFS and added the size of the adjacency list of each node visited then divided by 2 to check if edges equaled vertices visited.

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

      how to find the minimum no in the problem is you can explain some thing

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

    Recursion? I did it with DSU.

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

      at first i used some kind of DFS but it didn't pass because of max recursion depth i suppose

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

    Nope, I did a simple DFS to count the total components and the cyclic components.

    Submission link

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

      Of course you didn't have a such problem cause you've solved it using c++. Im using python which has a very restricted max depth of recursion and therefore i couldn't solve it the way you solved.

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

        I think a good solution to your problem would be switching to C++ :)

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

          It's not a problem, i don't care about my rating anymore. Besides, almost problems that i saw on cf are solvable by python (including this problem) so it's definitely not a big deal

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

lmao gonna lose some rating because I didn't even check restrictions of D for quite a while

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

    Same, I really tried to force an O(n) with casework until I just gave up and bruteforced every array starting with the best possible number.

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

      How to do D?

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

        For permutations starting with the max number, you can generate all possible arrays starting with max-1 in n^2 time. For permutations not starting with the max, you can generate all possible arrays starting with the max in n^2 time. Then just sort all the arrays you generated.

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

    I didn't realized the restriction of D is small until I saw your comment lmao. Luckily it didn't take me too much to come up with a $$$O(n)$$$ solution.

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

      I had some kind of solution for O(n) but it received runtime. Not sure why, will check that later, but damn, it took me hella time to notice that.

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

      Yep, I am even not sure currently what would O(n^2) solution for D look like. I noticed that in starting but all my intutions were just suggesting O(n) solution.

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

Does anyone's code for F was failing on test case 4 ?

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

I couldn't implement it, but is this idea correct for E?

a = # of connected components, b = # of cycles

Get the number of connected components and if it is a cycle then b++.

so if a == b min and max value is same, otherwise min = b + 1, max = b + a.

Plz confirm this, thx.

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

    Almost correct. (I made a similar mistake). Cycles of length 2 can be merged with each other. To be fair, it wasn't very clear from the statement and you had to have implemented it incorrectly to see the mistake.

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

    You find cycles which have >= 3 vertices. Yes, A is the number of connected components, it's true. B is the number of cycles (>= 3) and if you have some vertices which are not in these cycles B++.

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

    Another way is to count the number of components where the number of edges is equal to the number of vertices. I noticed the pattern quickly because it felt similar to a USACO silver problem I had seen before.

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

    Yes I forgot to mention that the size of cycle should be >= 3. Should I find a and b by union-find?

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

      Union-find is a perfect fit for finding cycles in this graph!

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

    max should be just a instead of b + a (because otherwise you would count every connected component that is a cycle twice) , but your idea is correct if we disregard this small mistake.

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

    I use DFS to find the connected components, which is the maximum value.

    A connected component is a cycle if every person in it knows two neighbors.

    The minimum value will be the number of cycles, plus 1 if there is at least 1 connected component (which is not a cycle), since all of them must be connected into a cycle.

    206539377

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

Problem D was so MESSY for me, but maybe I'm just stupid

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

    i was minutes away from solving but couldn't manage in the end

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

    I do think that D and E are super hard to implement.

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

      D is purely an implementation problem I guess. E was not that hard to implement, if you use some DSU implementation. (Assuming DSU implementation is directly available).

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

      I think that implementation wasn't hard at all, but in D maybe just many cases and small things to think of was hard to handle for me.

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

      E absolutely easy to implement — just straightforward DFS.

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

    the $$$O(n)$$$ solution is really short and neat if you think it out on a piece of paper first

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

    Please explain me someone why i can't solve fast easier problems like D, but i solve G in 15mins

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

can someone tell me how to find min no. of dance round in E ??

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

    Connect each pair of dancers with a DSU and count the number of connected components. Notice that, for every connected component, if there exists at least one dancer that does not know both of its partners, it can be merged with another connected component.

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

    We can see there are multiple disjoint sets of elements. For each set, we can classify if the set open or closed. Open set of size m have less than m unique edges (node pair, (3, 4) and (4, 3) are considered same). Then all the open sets can be merged together. And all the closed sets can't.

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

How to solve D?

I thought of multiple cases:

1) When v[0] == n

2) When v[n-1] == n

3) when n is between [1,n-2];

Still, I failed.

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

Thank you for the great contest. Really liked problem E and F. Although, I got 2 mins late while submitting F. I guess F was easier than E. It was just a combination of binary search and segment tree.

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

    if you used segtree you super over over killed it

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

      That was the first thing that came to my mind. I wanted product of frequencies in range [l, r]. There must be some easier way. But it was fastest for me (as I have segment tree template).

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

        You can use a prefix product array since the array is static :)

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

          Yep, time pressure in last led me to use my segment tree template directly.

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

          You don't even have to do that. Just maintain the product as you traverse with a window

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

        Why not just do a prefix multiplication with modular inverse?

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

        I'm maintaining a 2 pointer approach with unique array elements and map for frequencies.

        Can someone tell me what's wrong with below code? Instead of division, I'm multiplying with modInverse. It is working without modular operations for given testcase in question.


        fo(i,n-k+1){ runningSum *= (pm[b[i+k-1]]); runningSum %= mod; if(b[i] + k > b[i+k-1]){ ans += runningSum; ans %= mod; } // runningSum /= pm[b[i]]; //without mod runningSum *= inv(pm[b[i]],mod); runningSum %= mod; }
      • »
        »
        »
        »
        11 месяцев назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        yep, preprocess with sliding window after sorting them.

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

STLforces

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

Waiting for editorials^_^

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

lol for D, N<=2000. I noticed it but somehow continued trying O(N) solution and I don't know why...

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

    Yep, D was fun. Kind of implementation problem. After having some concrete observations.

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

    D is doable in O(n).

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

      Exactly, but after getting the necessary observations to solve D, my brain automatically forgot about N<=2000 and tried doing O(n) since it was doable (and I was too lazy to impl it so I went to E instead).

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

      Can you share some insight on how to solve D in O(N) instead of O(N^2)?

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

        Suppose a[0] != n (otherwise we can do something similar with n-1). Let i denote the index of n in the permutation. We want n to appear at the beginning, so we need to choose a segment ending at i-1. We must include the suffix starting at index i.

        We need to include index i-1 in the segment, so the new permutation is [n, a[i+1], ..., a[n-1], a[i-1], a[i-2], ..., a[j], a[0], a[1], ..., a[j-1]], for some index j. (Obtained by reversing indices j through i-1). To determine whether to extend the segment to index i-2, compare a[i-2] to a[0]. If greater, it's better to include it because otherwise a[0] would necessarily come afterward, which is smaller. Otherwise we should stop the segment and append the prefix (since we care about lexicographical maximality). If we extended the segment, we compare again for index i-3, and so on until a[j] < a[0] at which point it is optimal to end the segment. This takes O(n) time and it's not hard to see that it produces the correct answer.

        Note that if n is the last element in the permutation, we can also reverse the whole permutation, so we should take that into account. Also, you are allowed in this case to move n in front of all other elements.

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

      It's possible but it's tricky due to the edge cases that arise from the fact that empty prefixes and suffixes are allowed, but the middle portion (that is reversed) must be nonempty. I'd definitely recommend the more brute-force O(N^2) solution instead: faster to code up and less chance of errors.

      Fortunately, the sample input contained a lot of the tricky cases already.

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

        I don't think my solution was really tricky.

        206488860

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

          That's a nice solution but I think it's still quite tricky with all the conditionals. Honestly I think that's more complicated than the O(N) solutions to problems E, F, and G.

          By the way, I'm not sure if you know that Python compares lists lexicographically by default, so instead of this:

              z = 0
              for i in range(n):
                  if a1[i] > a2[i]:
                      z = 1
                      break
                  elif a1[i] < a2[i]:
                      z = 2
                      break
              if z == 1:
                  print(*a1)
              else:
                  print(*a2)
          

          You could write this:

              print(*max(a1, a2))
          

          Except there seems to be a weird edge case for N=1, where you construct a1=[1,1] and a2=[1], so you need to handle that somehow.

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

        Yeah, I feel like it is solvable in O(N) but all the case work just make it not easy to organize, then I noticed the problem constraint allows O(N^2) solution.

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

      I thought so too, is it possible in o(N) with 3 caseworks?

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

For me, Problems A and C were really irritating to be honest. D was okay. E and F were fun to solve and implement.

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

someone please help me with problem D?

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

    Hint: You need to figure out that what can be your first element in resultant list and where that element is. There should be two cases if that element is in the last of original array or somewhere else.

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

    First let's say maximum element={n if a[0]=n else n-1} Let indexMaxi=index of maximum element. fix r once as indexMaxi and once as indexMaxi-1. iterate over all l and choose the best answer. O(n^2) simple ,for O(n) you have to consider cases (I was getting frustated figuring out each edge case)... Solution

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

      why are we considering two indexMax? what's the intuition ?

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

        One case is that when the maximum element which is n is not on the index 0.In that case you can bring n to index 0.The other case is that when n is on the index 0.Then whatever operation you perform n can't remain on index 0.So then we will bring n-1.Instead of doing casework for the 2 cases separately,we check both and take the best answer.Hope it helps.

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

solved E after contest finishes. using simple dfs and some edges cases

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

After this long journey ,I feel tired... Couldn't even solve D..I feel ashamed of myself..

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

how to solve D? i don't understand it

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

D consumed lot of time for me:(

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

Vladosiya problems E and F were in the wrong order in my opinion because problem E is converted to a graph problem and requires graph knowledge which is harder than a brute force problem. (You have to convert it to graph and solve it) but F was very easy. In the last hour of the contest i read task E and got stuck on it, but in the last 10 minutes i read F and solved it in less than a minute but i wasn't able to code it in 10 mins and i upsovled it 10 mins after the contest ends:(

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

    I feel like E was more classic, I thought of the solution almost instantly due to studying some USACO this year. Granted I only had 20 minutes for F and I believe I saw the idea, but I couldn't put together a solution for it in time.

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

      Yeah USACO has some graph problems like problem E in many silver and gold divisions

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

How O(N^3) solution pass in D ?

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

My solution for F was failing for test 3 and I cant understand why. I was using long long so I dont think it should be because of overflow. My idea was to maintain maintain the count of dancers with some value v , sort this and do a sliding windown to find m consecutive numbers. Maintain their product. Use modular inverse for division. Would have become ab expert had this not happened :< .

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

    You were trying to access out of bound, there will be less than n elements in your vector v incase of duplicates.

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

      damn, right! Weird that this didn't come up in test 1 . Ughh... I am so frustrated.

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

Hello! I'm kinda new here T_T it would be great if someone could tell me what is wrong >_< i tried everything i know https://codeforces.com/contest/1833/submission/206552950

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

Can somebody explain how to take care of pairwise distinct in problem F?

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

I'm kinda new here T_T so it would be great if somebody told me what is wrong here.. I tried everything I know T_T https://codeforces.com/contest/1833/submission/206552950

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

I forgot to handle the special case of n=1 in Problem D, causing me to get it wrong 5 times.

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

emmmmmmmmmmmmmmmmmmmmmmm... so stupid am I

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

div4

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

Actually, I couldn't understand the statement of problem E, even after about 3 and 4 times reading. However, I figured out the solution only by drawing the graph of all test cases and guess. A bit lucky for me.

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

Похоже в этот раз будет много отменённых решений после системного тестирования

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

How where we supposed to do 2nd?

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

Hello Everyone, In problem G, in am trying to use queue and traverse along minimum indegree to it's parent and find answer accordingly and update the queue, but somehow i am getting WA , here is link to my submission , any help will be appreciated.

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

It is a good contest

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

Why many Java solutions of B are getting hacked? What's the tc?

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

    I guess because Arrays.sort() on primitive type array in Java has a known performance bottleneck and will TLE. A corresponding wrapper class should be used instead. At least my own solution was hacked because of that, sadly :(

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

This round is so helpful for beginner and also improve their primary skill by solving these types of problem. I think as a beginner its helpful for me like others and enjoy this contest very much.

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

Worst Div3 I have ever seen until now.

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

For those who are interested in the solution for the problems of this round, feel free to check out my video of me solving and explaining them :)

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

I need editorial for question B. Help!!

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

    You just have to sort the array B according to the array A. I used a vector pair to store the array a and its index then after sorting B and sorting the vector pair just insert the elements of B according to their order in A

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

Why O(n^3) solutions in D got accepted

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

    Because the maximum $$$n$$$, 2,000, is not very large. A naive solution for D, which constructs each possible flipped permutation and compares it to the maximum found so far, will use around $$$n^3/2$$$ operations to construct the permutations, but each operation is quite simple, just a 32-bit load and store, if you use ints to store the permutation. If the compiler can optimize by chunking these together into 128-bit loads and stores, this means you have to do just 1 billion of these operations in 1 second, which is possible.

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

      do you mean it is possible in just codeforces compiler not in local compiler?

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

        No, it could also be possible on your local computer, if it's not too slow.

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

I got stuck on problem G in test 3 (I passed 157 test cases on it), but I don't understand my mistake. I used BFS, and I know the other idea of DFS, but I want to understand what went wrong with my BFS implementation.

Here is the link to my code submission : https://codeforces.com/contest/1833/submission/206574785

Could anyone please help me?

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

Just come back after a year, better creating a new acc for the fresh start!

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

A very interesting contest. I've solved 2 problems for the first time!!. Lets go!!

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

Could someone help me solve problem of my code for C problem. I got TLE on test 11,which n is 2000000 but the another 2000000 is passed in less tham 100 ms. Thanks.

My idea is to anlysis whether this number can become odd or even num by a_i-a_j,so I sorted the array to reduce the time using.And if allow num can be odd or even output yes,either no.

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

    Since there can be up to 200,000 array elements, it's probably too slow to do another pass through the array for each element to determine whether there is a smaller odd element. It would be faster to reorganize the parity checking so that you know this immediately.

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

Can someone help me solve the B problem? Sorting the b array directly using Arrays. sort() will timeout, but shuffling the b array and sorting will not timeout. AC code: https://codeforces.com/contest/1833/submission/206582027 TLE code: https://codeforces.com/contest/1833/submission/206582200

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

Problem F is fantastic

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

Can anyone share your approach for G?

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

Hey can someone confirm whether this round is rated or unrated....my profile shows this as an unrated round for me despite my current rating being less than 1600 ?

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

    Me too. Maybe it's because the round is still in the open hacking stage. In fact if you open the profiles of other people who have participated in this round, you will find the same result. So don't worry and just wait for the rating changes.

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

hey so i wanted to ask why was the contest was unrated for me even when im below 1600 ratings

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

hey i wanted to ask why my ratings didn't increase even when im below 1600 ratings :(

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

When will the ranking points update (sorry i'm new here)

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

Tutorial?

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

can someone give hint for problem B?

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

    We want |a[i] — b[j]| to be <= k so a[i] and b[i] must not be far from each other more than k, so we can keep the value close together to minimize the difference

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

why is it so, my answer was accepted yesterday and today they are in queue ??

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

Nice contest. Was able to solve till D. Can someone explain me problem E? I didn't understand the samples for minimum round of dances.

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

    If there is group A-B-C-D-A, it can't be minimized. But if you have E-F, G-H, I-J, you can connect them into one group. Each dancer may have 1 or 2 partners, no other variants, so you can count dancers with 2 partners and with 1 partner. Those with 1 partner may be minimized:

    # if there are dancers with only 1 partner
    if (dancers_1 > 0):
      min_groups = max_groups - (dancers_1 / 2 - 1)
    
»
11 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can someone give hint for problem D?

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

good contest

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

I cannot solve problem B without a time limit exceeded(in java). What can I do to get a better optimization?.(should I put code here?)(Link: https://codeforces.com/contest/1833/submission/206641775)

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

Thanks for this contest. I've got +56.

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

please add the rank list in the blog :'(

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

How to solve the problem F,I have a way but the Time complexity is o(n^2),

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

There are WhatsApp groups available that offer solutions to contest problems while the contests are ongoing. Please get them blocked if possible.

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

    said a man with a lot of skipped solutions : )

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

      Said a man who is probably already a part of that group. Btw all the skipped solutions are from only 2 contests that too from first 10 contests. I have already given more than 100contets now. So plz shut up. Spend your time doing something valuable.

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

I was there after a month passed! It was hard to stand in this CF contest. I should do more practice I know.

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

我错过了比赛,好可惜啊

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

Thanks

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

Is it rated?

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

good luck everybody!!!

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

Здравствуйте. У меня проблема.

Внимание!

Ваше решение 206503312 по задаче 1833D значительным образом совпадает с решениями других участников и находится в группе одинаковых решений Tkm_champion/206503312, rejep001/206503419. Такое совпадение является явным нарушением правил. Отметим, что непреднамеренное утечка тоже является нарушением. Например, не следует пользоваться ideone.com с настройками по умолчанию (публичным доступом к вашему коду). Если вы имеете неоспоримые доказательства, что совпадение произошло по причине использования общего источника, опубликованного до соревнования, то напишите комментарий к посту о раунде со всеми деталями. Подробнее можно прочитать по ссылке http://codeforces.com/blog/entry/8790. Такое нарушение правил может являться основанием для блокировки вашего аккаунта или других штрафных санкций. В случае повторения нарушений, ваш аккаунт может быть заблокирован.

Мне это отправили из системы но я один и тот же человек с двумями аккаунтами пожалуйста скажите что мне сделать я могу доказать это.

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

I just received an email tells that my solution is matched with another solution.

I have another account which has rate 1700 (Div3 is unrated to it), So when i solved the problems in this account, i just submit the solution from my other account (and its not rated to it).

Should System Skip my participation in this case? If not, Can you let this round be rated for me, I don't think that i made rules violation at all.

System

MikeMirzayanov

This is my other account Ismail_Alrifai

my submission from this account 206533710

my submission from other account 206536131

1833F - Ira and Flamenco

Codeforces Round 874 (Div. 3)

Thank you.

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

I did not copy in this contest.

I did not share my solutions .

But received a Violation

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

All the questions in this round were simple enough for plagiarism to occur, it's so stupid to impose plagiarism for A and B. My solutions have been found similar to someone, that's totally possible because of the simplicity of questions. I obviously did all those questions by myself and there is no sharing involved at all. I request to give me back my rating changes.

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

There's some problem with the system plagiarism checking system, hopefully codeforces recognise that the chances for the 4-5 line code, straightway questions, being same are like over 70 percent, it's so weird to impose plagiarism, remove that from my handle, I'm oviously honest.

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

.

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

Attention!

Your solution 206472221 for the problem 1833A significantly coincides with solutions shivam_satyam_/206464201, Nishu Coder/206472221. Such a coincidence is a clear rules violation. Note that unintentional leakage is also a violation. For example, do not use ideone.com with the default settings (public access to your code). If you have conclusive evidence that a coincidence has occurred due to the use of a common source published before the competition, write a comment to post about the round with all the details. More information can be found at http://codeforces.com/blog/entry/8790. Such violation of the rules may be the reason for blocking your account or other penalties. In case of repeated violations, your account may be blocked.

The following complaint was sent to me just 3 hrs ago. Am I supposed to cheat for div3 problem A and that to for a contest that happened on may 19th,but still the system gave me notification after 12 days. even if I cheated then why my rating didn't deducted?. There is a serious bug in your system. please revolve this MikeMirzayanov.

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

.