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

Автор vishaaaal, 3 года назад, По-английски

Hello Codeforces!

Attention all players, the game is about to begin.

RECursion, the coding community of NIT Durgapur is glad to invite you to RECode 20.0 — an open to all contest which will be held on 15 November 2021 at 21:00 IST.

The contest is themed around your recent favorite series Squid Game! :))

You will be given 6 problems and 2 hours to solve them. It is highly recommended to read all the problems.

We present our special thanks to CodeChef for enabling us prepare and present the contest on such an amazing platform.

Prizes distribution are as follows :

  • Cash prize for Rs. 3000 for the overall top performer.
  • Cash prize of Rs. 2000 for the top performer from NIT Durgapur.
  • Certificates for all top performers.

For further details, contact :
Rushil : +91 85113 08746
Ankit : +91 8420998766

See you on the leaderboard!
Happy Coding :D

PS : As a gentle reminder, the contest is about to start in less than 30 minutes.
Good luck to all the participants! :)

PS : Editorials can be found here :-
Problem A — Marbles
Problem B — Deok-su and his Debts
Problem C — Ddakji
Problem D — Glass Stepping Stones
Problem E — Guard Quarters
Problem F — A Way Out

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

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

Looking forward for the contest!!:-D

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

Excited about the contest!!

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

Like the previous RECodes, the contest got to be amazing !

Waiting for it :p

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

As always, RECode is going to be awesome!

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

Contest has started!

Good luck and have fun!

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

How to submit after the contest? I cannot see any submit button.

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

In example 1 of Problem of C, there should be 48 possible permutations right? Only invalid permutation would be those in which 1 is on 2 3 4 position. Can anyone tell me why this approach is wrong?

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

    Consider the permutation given in the example itself. It doesn't have $$$1$$$ at indices $$$2$$$,$$$3$$$ or $$$4$$$ (assuming one-indexing).

    The total flips we get over all queries are $$${3+5}$$$, $$${7+2+1}$$$, $$${5+7+2}$$$ which sum up to $$$32$$$. Which is less than the number of flips obtained using the permutations given in sample.

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

      Yeah so answer should be 5!-3*4! right?

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

      My problem with the editorial is that it is assuming that let's say their are 5 positions that has maximum amount of flips( assuming this number to be 3). Now they are assuming that in the final answer only the last 5 ( cardboards that allow the maximum 5 flips can be allowed). Now let's say we have cardboards with capability 1 2 3 3 5 5 5 6 7 7 7. Why don't we consider all numbers that are greater than or equal to 3 to for those 5 positions. Since the left over numbers will still give us the same answers for position which we will flip less than 3 number of times.

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

        It is because- suppose a cardboard can be flipped $$$x$$$ times in each game, then in every game, that said cardboard would have to be flipped $$$x$$$ times only. I think you are assuming that a cardboard can be flipped only once in a game.

        Hence, to maximise the total, we should consider placing the cardboards in accordance to the maximum number of times they can be flipped.

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

    Not only $$$1$$$,even $$$2$$$ shouldn't be on any of the positions- 2,3,4.

    Hence- positions 2,3,4 are reserved in a way for cardboards- 3,5,7.

    -> 3!*2!= 12 permutations in total

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

      Why ? These positions are going to be flipped 2 times no ? So 2 is also possible in those positions right ?

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

        Not twice.. Each cardboard would be flipped the number of times it can be flipped, in every game.
        -> $$$A_i$$$ times only

        Considering the first example
        The frequency of the selected positions are as given:
        1 2 2 2 1
        Let us consider the arrangement-> 2 5 7 3 1
        The flips in total we do is: 2*1+5*2+7*2+3*2+1*1= 33

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

        But it won't lead to maximum result.

        Consider the arrangement in the given example only, as I have explained in a comment above, leads to $$$32$$$ flips over all games but the optimal answer is $$$33$$$ flips.

        Also, let me clarify the statement once.

        Statement