We will hold AtCoder Regular Contest 176.
- Contest URL: https://atcoder.jp/contests/arc176
- Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20240421T2100&p1=248
- Duration: 120 minutes
- Number of Tasks: 6
- Writer: PCTprobability
- Tester: maspy, Nyaan
- Rated range: — 2799
The point values will be 400-400-700-700-800-1000.
We are looking forward to your participation!
Hoping for the best ARC Round!
Good luck to all who are competing!
As a writer,I hope everyone who participates in this contest will enjoy it. Good luck!
Good Luck!Hope C!
I didn't get the question right
A was kinda tricky if you don't get the point :( I spent 30+ min on it :(
what was the idea?
can u please explain the solution of A. I am unable to get (b[i] — a[i] + n) % n , i cant understand it even after looking at the editorial
Maybe you can look at the following cases:
Where
x
andy
means $$$1$$$ ando
means $$$0$$$. You can divide them into $$$n$$$ sets that in each set, the elements has a same $$$(b_i-a_i)\bmod n$$$.Nice Explaination , thankyou so much
Yet another pure math contest. I suck at math, so dislike.
can B be solved using bitmasks? I don't know about it but i reduced it to a point like this where quotient is
but I was unable to solve it as I'm not good enough in bitmasks and stuff
what is the idea behind A?
The idea of the editorial is that:
First, let's try solve the problem without the given m value-1 cells.
How to solve m = 1? If you fill all cells on the antidiagonal with 1, then the sum of any row or column will be 1. No two cells on the antidiagonal are on the same row or column, and each row and each column are contributed by exactly one cell on the antidiagonal. (Assuming 0-based coordinate system is used) Cell v[i][j] on the antidiagonal are those where i + j = n-1. This solves the problem for m = 1.
What if m = 2? First fill the antidiagonal with 1. Then, you can "shift" the antidiagonal by 1 to the left and fill this new "antidiagonal" with 1. This new "antidiagonal" covers all cells v[i][j] where i + j = n-2 and v[n-1][n-1], or equivalently all elements v[i][j] where (i + j) mod n = n-2.
Applying to an arbitrary m, you just need to pick m such "antidiagonal"s and fill cells on them with 1.
How to solve the original problem where m value-1 cells are given? You just need to fill the "antidiagonal" of those m cells first. Some of them might belong to the same "antidiagonal". Then you can fill any rest "antidiagonal"s as needed.
Does B have no testcase with $$$n = m-1$$$ and $$$k=m-1$$$? I realised this condition a few seconds after submitting, but to my surprise, my code got AC.
Data of problem A is weak. As a result of me and my friends' verification, there is not a single piece of data that is $$$M \ne N < 2M$$$. And this is the evidence.
For example, this code which I submitted during the contest must be wrong. It gives completely wrong answer with this input.
I sent a clarification an hour ago, and I'll update as soon as possible when I see any response. I hope that I can write up a code that will allow me to get Accepted after the data is strengthened.
And I LOVE problem B. Very beautiful problem!
can anyone explain question b solution i did not understand
My First ARC got a 0pts but Rating+26, seems like it does need so many brainstroming instead of a number of algorithms at ahead problems.
Problem B is really a clever problem. I think I will never notice the case k=m-1 until I read the editorials. Hats off to the problem writers!
Data of problem C is also weak
The Editorial of C says:
and I forgot to check this case ($$$X_v < k$$$) during the contest, but my code got AC.
There is an input for this case:
my code during contest will give $$$40320$$$.
My code passed your case, but for this case:
my code will give 4.
I'm not sure whether this is common.
I hacked a lot people when I try to use their codes to check my wrong code. I'm so helpless. Who could help me?
Can someone explain the following code for problem A — 01 Matrix Again ?
There are total of n^2 elements in matrix so each (i-j)%n will occur atmost n times.
(you can draw the matrix of (i-j)%n for some n to see it youself)
since element are occurring on separate row and col we can assign 1 to such element that will increase the sum by n. How many times we need to do this? m times
So at last we just need to select m remainders out of n and assign 1 to those positions.
since some pairs are already given, we can just use remainder of those.
I hope it helps...
can someone explain me the problem problem D in it ,I cant understand how transition states are made.
Consider solving the subproblem for k, where we convert all p[i] <= k to 0 and p[i] > k to 1. The subproblem is to calculate, after m swaps, the number of (p[i], p[i+1]) such that one of them is 0 and the other is 1. Let s0, s1, s2 represent the states of containing 0, 1, 2 ones in an adjacent pair (p[i], p[i+1]) respectively.
Now, let's consider the transitions of a single swap:
Transitions starting from s2 is just symmetrical to the above transitions starting from s0:
Transitions starting from s1 can be similarly deducted:
With the above transitions, you can construct a 3x3 matrix M, where M[a][b] = the number of ways for the sa -> sb transition in a single swap. Let MM = M^m. Then MM[a][b] = the number of ways for the sa -> sb transition in m swaps. Let S be the 3x1 matrix where S[a][0] = the number of sa states in the original permutation. Let T = MM * S. T[a][0] will be the sum of the number of sa states after all possible m swaps. The answer to the subproblem is T[1][0].