Vladosiya's blog

By Vladosiya, history, 10 months ago, translation, In English

Hello! Codeforces Round 874 (Div. 3) will start at May/19/2023 17:35 (Moscow time). You will be offered 6-8 problems with expected difficulties to compose an interesting competition for participants with ratings up to 1600. However, all of you who wish to take part and have a rating of 1600 or higher, can register for the round unofficially.

The round will be hosted by rules of educational rounds (extended ICPC). Thus, solutions will be judged on preliminary tests during the round, and after the round, it will be a 12-hour phase of open hacks.

You will be given 6-8 problems and 2 hours and 15 minutes to solve them.

Note that the penalty for the wrong submission in this round is 10 minutes.

Remember that only the trusted participants of the third division will be included in the official standings table. As it is written by link, this is a compulsory measure for combating unsporting behavior. To qualify as a trusted participant of the third division, you must:

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

Regardless of whether you are a trusted participant of the third division or not, if your rating is less than 1600, then the round will be rated for you.

Thanks to MikeMirzayanov for the platform, help with ideas for problems and for coordination of our work. Problems have been created and written by ITMO University team: MikeMirzayanov, myav, Aris, Gornak40, senjougaharin and Vladosiya.

We would like to thank: pavlekn, KoT_OsKaR, natalina, vladmart, Phantom_Performer, Be_dos, ctraxxd, diskoteka, lunchbox, kzyKT, MODDI, molney, FEDIKUS, Nickir, 74TrAkToR, kamishogun, KseniaShk, Sokol080808, NintsiChkhaidze, Asad5059, heon for testing the contest and valuable feedback. List of testers will be updated.

Good luck!

UPD: Editorial

  • Vote: I like it
  • +194
  • Vote: I do not like it

»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hoping for the delta ++ ^..^

»
10 months ago, # |
  Vote: I like it -38 Vote: I do not like it

Hoping for positive delta

»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Finally, an unrated div3 for me!

»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

wishing a good div for one piece fans

  • »
    »
    10 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      10 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Can you give me a hint?

      • »
        »
        »
        »
        10 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        For problem F

      • »
        »
        »
        »
        10 months ago, # ^ |
        Rev. 3   Vote: I like it +3 Vote: I do not like it

        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

        • »
          »
          »
          »
          »
          10 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    10 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I'll need a timeskip to solve D

»
10 months ago, # |
  Vote: I like it +11 Vote: I do not like it

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

»
10 months ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

Waiting for testers comments :)

»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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!!

»
10 months ago, # |
  Vote: I like it +11 Vote: I do not like it

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 :)

»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Lets make our delta ++ ;)

»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Good luck!

»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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 ?

  • »
    »
    10 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    yes and no

  • »
    »
    10 months ago, # ^ |
    Rev. 3   Vote: I like it +1 Vote: I do not like it

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

  • »
    »
    10 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

»
10 months ago, # |
  Vote: I like it +27 Vote: I do not like it

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

»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

my 6th round, hoping to become pupil this time

»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hoping for a smooth contest and great problems.

»
10 months ago, # |
  Vote: I like it +5 Vote: I do not like it

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

»
10 months ago, # |
  Vote: I like it +2 Vote: I do not like it

Feeling this will be an hard round

»
10 months ago, # |
  Vote: I like it +4 Vote: I do not like it

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

  • »
    »
    10 months ago, # ^ |
      Vote: I like it +13 Vote: I do not like it
    Spoiler
    • »
      »
      »
      10 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      FREEDOM! I will give, if no one before.

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

  • »
    »
    10 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

XD

»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hoping for a balanced and interesting problemset :)

»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hoping for no cheats :{

»
10 months ago, # |
  Vote: I like it +4 Vote: I do not like it

Hoping to score a chance to AK this competition!

»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

nice contest

»
10 months ago, # |
  Vote: I like it -6 Vote: I do not like it

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.)

»
10 months ago, # |
  Vote: I like it +6 Vote: I do not like it

div4 or div3 contest?

»
10 months ago, # |
  Vote: I like it +6 Vote: I do not like it

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?

  • »
    »
    10 months ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    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.

    • »
      »
      »
      10 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

    • »
      »
      »
      10 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      • »
        »
        »
        »
        10 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

        • »
          »
          »
          »
          »
          10 months ago, # ^ |
          Rev. 2   Vote: I like it 0 Vote: I do not like it

          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 :)

          • »
            »
            »
            »
            »
            »
            10 months ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

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

»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    10 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      10 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      • »
        »
        »
        »
        10 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

    • »
      »
      »
      10 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    10 months ago, # ^ |
      Vote: I like it +17 Vote: I do not like it

    Recursion? I did it with DSU.

    • »
      »
      »
      10 months ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    10 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    Submission link

    • »
      »
      »
      10 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      • »
        »
        »
        »
        10 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

        • »
          »
          »
          »
          »
          10 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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

»
10 months ago, # |
  Vote: I like it +1 Vote: I do not like it

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

  • »
    »
    10 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    • »
      »
      »
      10 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      How to do D?

      • »
        »
        »
        »
        10 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

      • »
        »
        »
        »
        10 months ago, # ^ |
        Rev. 3   Vote: I like it 0 Vote: I do not like it
        How I did:
  • »
    »
    10 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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.

    • »
      »
      »
      10 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

    • »
      »
      »
      10 months ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      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.

»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

  • »
    »
    10 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

  • »
    »
    10 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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++.

  • »
    »
    10 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

  • »
    »
    10 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      10 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    10 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

  • »
    »
    10 months ago, # ^ |
    Rev. 4   Vote: I like it 0 Vote: I do not like it

    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

»
10 months ago, # |
  Vote: I like it +2 Vote: I do not like it

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

  • »
    »
    10 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    10 months ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

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

    • »
      »
      »
      10 months ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      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).

      • »
        »
        »
        »
        10 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Implementation without DSU is relatively easy. Here you can check out mine 206530050

    • »
      »
      »
      10 months ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      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.

    • »
      »
      »
      10 months ago, # ^ |
        Vote: I like it +4 Vote: I do not like it

      E absolutely easy to implement — just straightforward DFS.

  • »
    »
    10 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    10 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    10 months ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    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.

  • »
    »
    10 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

  • »
    »
    10 months ago, # ^ |
      Vote: I like it +16 Vote: I do not like it

    if you used segtree you super over over killed it

    • »
      »
      »
      10 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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).

      • »
        »
        »
        »
        10 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

        • »
          »
          »
          »
          »
          10 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

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

        • »
          »
          »
          »
          »
          10 months ago, # ^ |
            Vote: I like it +14 Vote: I do not like it

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

      • »
        »
        »
        »
        10 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Why not just do a prefix multiplication with modular inverse?

      • »
        »
        »
        »
        10 months ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        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; }
      • »
        »
        »
        »
        10 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        yep, preprocess with sliding window after sorting them.

»
10 months ago, # |
  Vote: I like it +1 Vote: I do not like it

STLforces

»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Waiting for editorials^_^

»
10 months ago, # |
  Vote: I like it +3 Vote: I do not like it

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

  • »
    »
    10 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    10 months ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    D is doable in O(n).

    • »
      »
      »
      10 months ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      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).

    • »
      »
      »
      10 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      • »
        »
        »
        »
        10 months ago, # ^ |
        Rev. 3   Vote: I like it 0 Vote: I do not like it

        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.

    • »
      »
      »
      10 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      • »
        »
        »
        »
        10 months ago, # ^ |
        Rev. 2   Vote: I like it +3 Vote: I do not like it

        I don't think my solution was really tricky.

        206488860

        • »
          »
          »
          »
          »
          10 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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.

      • »
        »
        »
        »
        10 months ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        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.

    • »
      »
      »
      10 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

someone please help me with problem D?

  • »
    »
    10 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

  • »
    »
    10 months ago, # ^ |
    Rev. 3   Vote: I like it +3 Vote: I do not like it

    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

    • »
      »
      »
      10 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      • »
        »
        »
        »
        10 months ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        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.

        • »
          »
          »
          »
          »
          10 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Thanks! Got it !

»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

how to solve D? i don't understand it

»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

D consumed lot of time for me:(

»
10 months ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

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:(

  • »
    »
    10 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    • »
      »
      »
      10 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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 :< .

  • »
    »
    10 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      10 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    10 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    you can group the same number together and maintain their frequency to count how many ways

  • »
    »
    10 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    you just need m consecutive values.

»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    10 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    that distance thing might be giving u tle...i guess its working O(n^2) coz of that...

»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

emmmmmmmmmmmmmmmmmmmmmmm... so stupid am I

»
10 months ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

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.

»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How where we supposed to do 2nd?

  • »
    »
    10 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    HInt
»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    10 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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 :(

    • »
      »
      »
      10 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Can you elaborate? What's the known performance problem? Isn't it O(N log N) as one would reasonably expect?

    • »
      »
      »
      10 months ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      i hacked 134 submissions, where 133 was java sort error.

»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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 :)

»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I need editorial for question B. Help!!

  • »
    »
    10 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    10 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    • »
      »
      »
      10 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      • »
        »
        »
        »
        10 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

»
10 months ago, # |
  Vote: I like it +1 Vote: I do not like it

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?

»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
10 months ago, # |
  Vote: I like it +2 Vote: I do not like it

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

»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

  • »
    »
    10 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

»
10 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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

»
10 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Problem F is fantastic

»
10 months ago, # |
  Vote: I like it +2 Vote: I do not like it

Can anyone share your approach for G?

»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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 ?

  • »
    »
    10 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
10 months ago, # |
  Vote: I like it +1 Vote: I do not like it

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

  • »
    »
    10 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Just wait.It will be updated in several hours.

»
10 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Tutorial?

»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

can someone give hint for problem B?

  • »
    »
    10 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    10 months ago, # ^ |
      Vote: I like it +20 Vote: I do not like it

    It is called system testing which occurs after hacking phase in div3s is completed and the submissions are rejudged with the new added testcases

»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

  • »
    »
    10 months ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    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)
    
»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone give hint for problem D?

»
10 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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)

»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

please add the rank list in the blog :'(

»
10 months ago, # |
Rev. 3   Vote: I like it +3 Vote: I do not like it

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

  • »
    »
    10 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    said a man with a lot of skipped solutions : )

    • »
      »
      »
      10 months ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      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.

»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Thanks

»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Is it rated?

»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

good luck everybody!!!

»
10 months ago, # |
Rev. 2   Vote: I like it +1 Vote: I do not like it

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.

  • »
    »
    10 months ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    your solution is getting judged even you are rated or not .

»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

»
10 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

.

»
10 months ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

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.

»
10 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

.