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
Looking forward for the contest!!:-D
Excited about the contest!!
Like the previous RECodes, the contest got to be amazing !
Waiting for it :p
As always, RECode is going to be awesome!
Contest has started!
Good luck and have fun!
How to submit after the contest? I cannot see any submit button.
Problems will be moved to the practice section by tomorrow.
Is there will be editorial ?
Yes. Editorials will be published soon.
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?
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.
Yeah so answer should be 5!-3*4! right?
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.
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.
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
Why ? These positions are going to be flipped 2 times no ? So 2 is also possible in those positions right ?
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
My bad, I didn't understand the question.
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.
Consider an array $$$arr[]$$$ of length $$$n$$$. You will process $$$q$$$ operations on it. In each operation, you will be given two numbers $$$l$$$ and $$$r$$$ where $$$1\leq l\leq r\leq n$$$. In this operation, you add the values of elements whose indices lie in the range $$$[l,r]$$$ to your score. Your final score is the score you achieve after all $$$q$$$ operations. This score is actually the number of flips as per the statement of the problem.
You have been given the array $$$arr[]$$$ and are allowed to rearrange it however you want. The problem asks you to find the number of ways to rearrange it so that in each arrangement you obtain maximum possible final score. The number should be computed modulo $$$10^9 + 7$$$.