We will hold AtCoder Regular Contest 107.
- Contest URL: https://atcoder.jp/contests/arc107
- Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20201031T2100&p1=248
- Duration: 100 minutes
- Number of Tasks: 6
- Writer: maroonrk, yosupo, sigma425
- Tester: maroonrk, yosupo, sigma425
- Rated range: 0 — 2799
The point values will be 300 — 400 — 500 — 600 — 800 — 900.
We are looking forward to your participation!
Auto comment: topic has been updated by maroonrk (previous revision, new revision, compare).
The contest starts in ~10 mins.
~1 minutes left
Best of LUCK!!
Maths only round?
MathCoder ew
Just counting and counting and still counting...
F is not counting anyway.
What's the solution of C?
The swappable rows and cols are independent of each other. Both build components. In each component there are factorial(componentSize) permutations. Multiply all of them.
Which rows and cols are swappable can be found by brute force in O(n^3)
I did the same. But idk why my 2nd sample was coming wrong.
Can you take a look once? Submission
Thank you :)
You may debug it on your own, use my submission as reference ;)
I looked at my code once more and found my stupid mistake.
:(
I did the same thing, in sample test case 1 there were 1 swappable pair of rows and 2 swappable pair of columns, so how is the answer 12?
for sample test case 1:
Edges in column:
which means there is only one component whose size is 3(1,2,3).
Edges in row:
which means there are 2 component, whose sizes are 2 (1,3) and 1(2).
then the ans = fact[3] * fact[2] * fact[1] = 12.
Reference soln: link
Got it, thanks!
Honestly, math homework today felt a bit boring :/
good atCombinatory Regular contest.
How to solve C?
For the columns, you count the number of connected components (I use a dsu for this). Do the same for the rows. Now count the number of permutations for each component. The answer is the product of all those numbers.
I did the same thing. Instead of using dsu, I did BFS. But, my solution doesn't match output of sample 2.
Oh shit, I just made a stupid bug in my code lol.
Basically solve independently for rows and columns and multiply the answer for both of them.
Make a network where i,j is connected if rows i and j can be exchanged. Now the answer is the multiplication of the factorial of the size of each connected component(since size! ways to arrange these components).
Do the same for columns.
Reference link — link
Observe that switching rows has no effect on columns that you can switch, and vice versa. So now, the switching of rows and columns is independent of one another. Now we just need to find which rows we can switch ($$$O(n^3)$$$). The number of ways we could arrange these rows is $$$m!$$$ for each group of size $$$m$$$ that we can switch (By group I mean a set of rows that we can arrange in any order). We can find each of these groups with DSU. Do the same for columns, and multiply for your answer
how to solve D?
For D use DP approach.
Initially lets start with k ones. Now we have to make n-k further breakdowns to have n elements. Each breakdown will result in two numbers with values half of the breakdown element. (For eg, If we decide to break down 4 1/2 elements, we will have 8 1/4 elements)
Now lets breakdown in descending order starting from 1. (ie break some 1's -> break some 1/2's ->break some 1/4's and so on)
Its now a n^3 dp with states as the breakdowns left(to have total n elements in the array and we initially start with k elements) and the amount of the latest value elements we have after the breakdown in the last step. This could be reduced to n^2 by prefix sums.
Reference solution — link
A much simpler approach : Let $$$dp(N,K)$$$ be the number of multi sets with sum $$$k$$$ and size $$$N$$$ . You can recursively formulate $$$ dp(N,K) = dp(N,2*K) + dp(N-1,K-1) $$$.The first term $$$dp(N,2*K)$$$ is the case when you don't take 1 and so the sequence starts from $$$\frac{1}{2}$$$ so it is equivalent of taking sum to $$$ 2*k$$$ and let the sequence to start from 1,The other term ,$$$ dp(N-1,K-1) $$$ is the case when you have taken 1 in the multiset,so your sum reduces to $$$k-1$$$ and length to $$$N-1$$$ and you can still start from 1.
Does sequence will never start from 1/4 or 1/8 or 1/16.......? or are they already included in dp(N,2*K) part? I didn't understand this part.
Update: Got it. It will be included in dp(N,2*K) part. dp(N,2*K) will not only tell the sequence starting from 1/2 but also for all 1/2^i for i>=1. because we are iterating from backward. So dp(n,2*k) will contain dp(n,4*k) and so on... Here is my accepted submission.
can you explain more about dp(N,2*K) how it is including 1/4 ,1/8....???
dp[i][2*k]+= dp[i-1][2*k-1]+dp[i][4*k]. Similarly dp[i][4*k]+= dp[i-1][4*k-1]+dp[i][8*k] and so on. So dp[i][4*k] value denotes the number of sequences which starts from 4*j=1 => means 1/4. Similarly, dp[i][8*k] for sequence starting from 1/8. and so on.
And dp[i][8*k] is included in dp[i][4*k] which is further included in dp[i][2*k] which is included in dp[i][k].
ll solve(ll idx,ll n,ll k){ if(n==0 && k==0)return 1; if(k>n)return 0; if(n<=0 || k<=0 || idx>=12)return 0; if(dp[idx][n][k]!=-1)return dp[idx][n][k]; ll ans=0; ans=solve(idx+1,n,k*2)+solve(idx,n-1,k-1); ans%=M; dp[idx][n][k]=ans; return ans; }
I am doing the same thing which you have told but getting wrong answer.I have used idx which tells the power of 2(2^idx).Can you tell me why is it giving wrong answer on 2nd test case.
How to solve E ?
Try to brute force the first 100 rows and columns,try to find the regular pattern.
It is enough if we only find the first 4 rows and columns.
But I think 100 is very safe.
It is right, but always prepare for memory issues
Yes. By pigeonhole principle.
https://atcoder.jp/contests/arc107/submissions/17758415 My solution to A. But I kept getting TLE. What other trick should I have used in implementation?
Did you notice the constraints? a <= 1e9. Isn't it obvious you got TLE? No tricks in implementation, rather you should have realized this TLE issue, and come up with some math solution that works in O(1).
Observe that $$$a,b,c \geq 10^9$$$. It will definitely TLE. Try to think of reducing this sum (product??) with math.
Am I the only person who just solve A,B,D,E? :)
rage quit after reading tutorial of E :(
How to solve B ???
I registered but did not submit any solution .. Will my rating effected by this contest ??
For B rewrite the equation as $$$(A + B) - (C + D) = k$$$
Loop through all possible values of $$$(A + B)$$$ and calculate how many pairs($$$1 <= a <= n$$$, $$$1 <= b <= n$$$) can form $$$(A + B)$$$ same for $$$(A + B) - k$$$ = $$$(C + D)$$$ and multiply the both
Submission: Link
And nothing will happen to your rating
Who can give a rather elegant proof for E? (Or just case handling?)
My proof contains a bit of cases but is overall quite clean.
Let us show four facts (true for cells with indexes $$$\ge 5$$$):
1) The configuration
x x
does not occur. This follows directly from the statement.2) The configuration
2 1 2
does not occur. Indeed, it would generatebut we have already established that
0 0
cannot occur.3) The configuration
1 2 1
does not occur. Indeed, it would generatebut we have already established that
0 0
cannot occur.4) The configuration
0 2 0
does not occur. Indeed, it would generatebut we have already established that
2 1 2
cannot occur.Now that we have these four facts, consider three consecutive cells
x y z
. It holds $$$y\not= x$$$ and $$$y\not=z$$$.Thus we have proven that $$$y=mex(x,z)$$$. As a consequence (by induction on the indices) we get
Hence we have shown $$$a(i,j) = a(i-1,j-1)$$$ for any $$$i,j$$$ large enough ($$$i,j\ge 5$$$ should be enough).
Unless I'm missing something, I think you just proved the inductive step: $$$a_{i,j-1} = a_{i-1,j-2} \implies a_{i,j} = a_{i-1,j-1}$$$, but you haven't proved the existence of a base case, like for example: $$$a_{5,5}=a_{4,4}$$$. Moreover, if we can prove this base case, we may use the same reasoning to prove $$$a_{5+i,5+j}=a_{4+i,4+j}$$$ in general, without any inductive step.
Here is my hopefully-with-not-so-many-cases case analysis attempt:
We'll use the main fact that (ignoring the first row and column) no 2 adjacent (with a common side) entries have the same value on them.
Let's take an arbitrary 4x4 subrectangle that doesn't include the first row or column. We'll show that $$$x=y$$$.
There are 2 cases:
By the main fact, the $$$?$$$ signs may be $$$a$$$ or $$$c$$$. There are 2 cases:
but $$$a = mex(b,b) = c$$$. Contradiction.
Since entries above and to the left of a $$$2$$$ should be $$$0$$$ and $$$1$$$ (in some order), we know that
t u v
should be either0 1 0
or1 0 1
. So, by the main fact, we can reveal both $$$2$$$ in step A. Then, since $$$mex(2,2)=0$$$ we know in step B thatt u v
was actually1 0 1
. By the main fact, we know in step C that the $$$?$$$ sign should be $$$2$$$, and again, since it has a $$$1$$$ to its left, there must be a $$$0$$$ above.Finally, by the main fact, $$$q=2$$$, but then: $$$0 = mex(2,2) = mex(2,q) = 1$$$, which is a contradiction.
You are right. On the other hand, your solution is clean and correct.
fengyecong Can you explain your solution for D? or can anyone try to explain this?
In problem D's editorial, how do you make sure that when you multiply k by 2 continuously, it does not get too large?
$$$k>n$$$ is zero.
Oh.. So sad I thought of this dp during contest but I keep thinking that k could be out of range.. Thanks.
Here are video editorials of A-D and a screencast of doing badly on all of them
Ignore.
maroonrk Can we expect tommorow's ABC 181 to be resheduled in clash to cf round #680 ?
Could someone explain why it's possible to obtain any permutation in a connected component for problem C? Editorial says that we can swap A and D in a sequence A-B-C-D, where we can swap connected elements, by a sequence of adjacent swaps. But after we swap A and B, we get a sequence B, A, C, D, where it might be impossible to swap A and C. What obvious fact am I missing?
Say among four columns A, B, C and D, you can swap pairs (A, B), (A, C) and pairs (C, D), so all of these form a single component.
We can achieve all orderings by an order of swaps. Starting from ABCD, to get BDAC, we make swaps to get ABCD -> BACD-> BCAD-> BDAC, to get CBDA, we follow ABCD-> ABDC-> CBDA.
We can see that for a pair(x, y), we can achieve this swaps through a sequence of swaps, if x and y lie in same connected component. Visualize like moving on a path over spanning tree formed by these edges (pairs).
let's denote the transposition of positions
i
andj
by(i j)
.then
(A C)
=(A B)*(B C)*(A B)
(*
denotes the function composition)it's easy to prove inductively that in order to generate the entire permutations, you only need N-1 transpositions forming a spanning tree, using the above equality.
(this is also one of the basic exercise you'll find in any group theory course)
Why in A this code gives me wa?
...
This overflows because you multiplicate three multiplicators, then use the mod operation. Since the mod value is at about 2^30 that would require the integer type to be about 90 bit. Use instead something like
cout<<((((s1%mod)*(s2%mod))%mod)*(s3%mod))%mod;
multiplication one value at a time.Can anybody tell me why I am getting TLE. Link To My Submission
How to Solve B with Inclusion-Exclusion principle??
For context, the editorial of problem B says that it can also be solved using "inclusion-excusion and so on" in $$$O(1)$$$. Would be great if someone could briefly explain the approach.
Video Solution for D
IOI2024 d2t2.