### maroonrk's blog

By maroonrk, history, 5 weeks ago,

We will hold AtCoder Regular Contest 107.

The point values will be 300 — 400 — 500 — 600 — 800 — 900.

We are looking forward to your participation!

• +138

 » 5 weeks ago, # |   +8 Auto comment: topic has been updated by maroonrk (previous revision, new revision, compare).
 » 5 weeks ago, # | ← Rev. 2 →   +33 The contest starts in ~10 mins.
•  » » 5 weeks ago, # ^ |   +10 ~1 minutes left
 » 5 weeks ago, # |   +10 Best of LUCK!!
 » 5 weeks ago, # |   +12 Maths only round?
 » 5 weeks ago, # |   0 MathCoder ew
 » 5 weeks ago, # |   +30 Just counting and counting and still counting...
•  » » 5 weeks ago, # ^ |   0 F is not counting anyway.
•  » » » 5 weeks ago, # ^ |   -35 F looks like greedy to me, but I lack confidence in implementing what I am thinking :D
 » 5 weeks ago, # |   +4 What's the solution of C?
•  » » 5 weeks ago, # ^ |   0 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)
•  » » » 5 weeks ago, # ^ |   0 I did the same. But idk why my 2nd sample was coming wrong. Can you take a look once? SubmissionThank you :)
•  » » » » 5 weeks ago, # ^ |   +3 You may debug it on your own, use my submission as reference ;)
•  » » » » » 5 weeks ago, # ^ |   0 I looked at my code once more and found my stupid mistake.:(
•  » » » 5 weeks ago, # ^ |   0 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?
•  » » » » 5 weeks ago, # ^ | ← Rev. 2 →   +3 for sample test case 1: 3 13 3 2 7 4 8 9 1 6 5 Edges in column: 1 -- 2 1 -- 3 which means there is only one component whose size is 3(1,2,3).Edges in row: 1 -- 3 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
•  » » » » » 5 weeks ago, # ^ |   0 Got it, thanks!
 » 5 weeks ago, # |   +15 Honestly, math homework today felt a bit boring :/
 » 5 weeks ago, # |   -12 good atCombinatory Regular contest.
 » 5 weeks ago, # |   0 How to solve C?
•  » » 5 weeks ago, # ^ |   +5 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.
•  » » » 5 weeks ago, # ^ |   +3 I did the same thing. Instead of using dsu, I did BFS. But, my solution doesn't match output of sample 2.
•  » » » 5 weeks ago, # ^ |   +3 Oh shit, I just made a stupid bug in my code lol.
•  » » 5 weeks ago, # ^ |   +5 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
•  » » 5 weeks ago, # ^ |   +1 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
 » 5 weeks ago, # |   +3 how to solve D?
•  » » 5 weeks ago, # ^ |   +16 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
•  » » » 5 weeks ago, # ^ |   +27 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.
•  » » » » 5 weeks ago, # ^ | ← Rev. 5 →   +3 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.
•  » » » » » 5 weeks ago, # ^ |   0 can you explain more about dp(N,2*K) how it is including 1/4 ,1/8....???
•  » » » » » » 5 weeks ago, # ^ | ← Rev. 2 →   0 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].
•  » » » » » » » 5 weeks ago, # ^ |   0 Thanks bro got it ..
•  » » » » 5 weeks ago, # ^ |   0 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.
 » 5 weeks ago, # |   +8 How to solve E ?
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   +5 Try to brute force the first 100 rows and columns,try to find the regular pattern.
•  » » » 5 weeks ago, # ^ |   +5 It is enough if we only find the first 4 rows and columns.
•  » » » » 5 weeks ago, # ^ |   +10 But I think 100 is very safe.
•  » » » » » 5 weeks ago, # ^ |   +8 It is right, but always prepare for memory issues
•  » » » » 5 weeks ago, # ^ |   -33 Yes. By pigeonhole principle.
 » 5 weeks ago, # |   0 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?
•  » » 5 weeks ago, # ^ |   0 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).
•  » » 5 weeks ago, # ^ |   0 Observe that $a,b,c \geq 10^9$. It will definitely TLE. Try to think of reducing this sum (product??) with math.
 » 5 weeks ago, # |   +3 Am I the only person who just solve A,B,D,E? :)
 » 5 weeks ago, # |   +39 rage quit after reading tutorial of E :(
 » 5 weeks ago, # | ← Rev. 2 →   0 How to solve B ???I registered but did not submit any solution .. Will my rating effected by this contest ??
•  » » 5 weeks ago, # ^ | ← Rev. 4 →   0 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: LinkAnd nothing will happen to your rating
 » 5 weeks ago, # |   0 Who can give a rather elegant proof for E? (Or just case handling?)
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   +29 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 generate ? 0 0 2 1 2 but we have already established that 0 0 cannot occur.3) The configuration 1 2 1 does not occur. Indeed, it would generate ? 0 0 1 2 1 but we have already established that 0 0 cannot occur.4) The configuration 0 2 0 does not occur. Indeed, it would generate 2 1 2 0 2 0 but 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$. If $y=0$ then $y=mex(x, z)$. If $y=1$ then either $y=mex(x, z)$ or $x=z=2$ which is impossible. If $y=2$ then either $y=mex(x, z)$ or $x=z=0$ which is impossible or $x=z=1$ which is impossible. Thus we have proven that $y=mex(x,z)$. As a consequence (by induction on the indices) we get $a(i,j)=mex(a(i,j-1), a(i-1, j)) = mex(a(i-1, j-2), a(i-1, j)) = a(i-1, j-1) \,.$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).
•  » » » 3 weeks ago, # ^ |   +10 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$.  . . . . . . . . . . x z . . w y There are 2 cases: If $w \neq z$, then $x$ and $y$ (by the main fact) should be different from $w$ and $z$ and so they should be equal to each other (since there are 3 possible values) and we're done. If $w = z$, let's assume that $x \neq y$ to reach a contradiction. Let $a$, $b$ and $c$ be the 3 different values.  . . . . . . . ? . . a b . ? b c By the main fact, the $?$ signs may be $a$ or $c$. There are 2 cases: 2.a) Both $?$ signs are $c$. Then, by the main fact, we have two $b$ above:  . . . . . . b c . b a b . c b c but $a = mex(b,b) = c$. Contradiction. 2.b) At least one $?$ sign is $a$. Without loss of generality, suppose the bottom row $?$ sign is $a$. Then, we have $mex(a,a) = mex(a) = b$ and $mex(b,b) = mex(b) = c$, so $b$ and $c$ should be $0$ and $1$ in some order (since the $mex$ of a singleton may not be greater than $1$). So $a$ needs to be $2$, and then $b = mex(a) = mex(2) = 0$ and $c = mex(b) = mex(0) = 1$. Replacing $a$, $b$ and $c$, we have:  . . . . . . . . . . . . . . q 0 . . v ? A) . 2 v ? B) . 2 1 ? C) . 2 1 2 . u 2 0 => 2 u 2 0 => 2 0 2 0 => 2 0 2 0 t 2 0 1 t 2 0 1 1 2 0 1 1 2 0 1 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 either 0 1 0 or 1 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 that t u v was actually 1 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.
•  » » » » 3 weeks ago, # ^ |   0 You are right. On the other hand, your solution is clean and correct.
 » 5 weeks ago, # |   0 fengyecong Can you explain your solution for D? or can anyone try to explain this?
 » 5 weeks ago, # |   0 In problem D's editorial, how do you make sure that when you multiply k by 2 continuously, it does not get too large?
•  » » 5 weeks ago, # ^ |   +9 $k>n$ is zero.
•  » » » 5 weeks ago, # ^ |   0 Oh.. So sad I thought of this dp during contest but I keep thinking that k could be out of range.. Thanks.
 » 5 weeks ago, # | ← Rev. 3 →   0 Can somebody please explain problem B Quadruple ??
 » 5 weeks ago, # |   +22 Here are video editorials of A-D and a screencast of doing badly on all of them
 » 5 weeks ago, # | ← Rev. 6 →   0 Ignore.
 » 5 weeks ago, # |   +8 maroonrk Can we expect tommorow's ABC 181 to be resheduled in clash to cf round #680 ?
 » 5 weeks ago, # |   -8 Is it possible to solve problem A in c++? I used the approach recommended in the tutorial but got the wrong answer for large a b c inputs
•  » » 5 weeks ago, # ^ |   0 As you didn't show us your submission I assume that u didn't check the overflow here. See this solution to better understand- #include using namespace std; #define int long long int #define mod 998244353 const int N=1e5+5; signed main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int a,b,c;cin>>a>>b>>c; int s1=a*(a+1)/2,s2=b*(b+1)/2,s3=c*(c+1)/2; cout<<((((s1%mod)*(s2%mod))%mod)*(s3%mod))%mod; return 0; } 
 » 5 weeks ago, # |   -8 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?
•  » » 5 weeks ago, # ^ |   0 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).
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   +8 let's denote the transposition of positions i and j 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)
 » 5 weeks ago, # |   0 Math only round and require great mental affect.
 » 5 weeks ago, # |   0 For A , I don't really understand why // is needed instead of just / in the Python solution. Both feels like it does the same thing but using just divide / gets the wrong answer.
 » 5 weeks ago, # |   0 Why in A this code gives me wa? code... #include using namespace std; #define int long long int #define mod 998244353 const int N=1e5+5; signed main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int a,b,c;cin>>a>>b>>c; int s1=a*(a+1)/2,s2=b*(b+1)/2,s3=c*(c+1)/2; cout<<((s1%mod)*(s2%mod)*(s3%mod))%mod; return 0; } 
•  » » 5 weeks ago, # ^ |   0 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.
•  » » » 5 weeks ago, # ^ |   0 Thanks
 » 5 weeks ago, # | ← Rev. 3 →   0 Problem B:the number f ( N , K ) of pairs of integers ( a , b ) such that 1 ≤ a , b ≤ N and a + b = K .f(N,K)=min(K−1,2N+1−K)forK=2,3,…,2N.Here, I observed that it can be K-1 if both a and b are positive but I didn't understand 2nd part 2N+1-K. How this comes up? what is the proof?UPD: got it.
•  » » 5 weeks ago, # ^ |   0 Can you please share it!!
•  » » » 5 weeks ago, # ^ |   0 For N=5, K=7, a+b can be (1+6), (2+5), (3+4), (4+3), (5+2) and (6+1).[considering 1<=a,b<=+Infinity]now, because of N=5, we have to take (5+2) as the highest sum within constraints. We can make the formula as (5-2+1)==(5-(K-5))+1==(N-(K-N))+1==(2N+1-K).
 » 5 weeks ago, # | ← Rev. 2 →   0 Can anybody tell me why I am getting TLE. Link To My Submission
 » 5 weeks ago, # | ← Rev. 2 →   +5 How to Solve B with Inclusion-Exclusion principle??
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   0 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.
 » 4 weeks ago, # |   0