### chokudai's blog

By chokudai, history, 3 months ago, We will hold AtCoder Beginner Contest 293.

The point values will be 100-200-300-400-500-500-600-600. We are looking forward to your participation! Comments (55)
 » What is the counter test case for this problem B's solution? I kept getting WA. ugly code#include using namespace std; #define nl '\n' void Solve(){ int n; cin>>n; vector v(n); vector calledOut(n + 1); for(int i = 0; i < n; i++){ cin>>v[i]; } int called = 0; for(int i = 0; i < n; i++){ if(!calledOut[i + 1]){ calledOut[v[i]] = true; called++; } } cout<>T; while(T--){ Solve(); } } 
•  » » 53 4 1 5 4For this test case, your code gives wrong answer.
•  » » » It seems that this test case itself is invalid Even if this test case is valid, my code outputs 1 2 5, is it wrong?
•  » » » » The number of elements in the answer is actually 3, but your code gives 2.
•  » » » » » Perhaps I misunderstood the problem statement, so the elements of the given array are not necessary to be distinct?
•  » » » » » » Yes.
•  » » » » » » » Ok, I was so upset and left the contest so early not even bothering to read C, D, E.
 » today, re-learn how to sum the Geometric Progression :) good problem
 » 3 months ago, # | ← Rev. 2 →   Can't seem to get D to AC, failed 6 test cases. My idea is to label $2*i$ as blue and $2*i + 1$ as red for $i \in [1, n]$ and treat it as a graph dfs problem Spoilervt> G; vt vis; void dfs(int u, int p = -1) { if(vis[u]) return; vis[u] = 1; for(auto v: G[u]) { if(v == p) continue; dfs(v, u); } } void solve() { int n, m; cin >> n >> m; G = vt>(2 * n); vis = vt(2 * n); for(int i=0; i> a >> b >> c >> d, a--, c--; a = a * 2 + (b == 'R'); c = c * 2 + (d == 'R'); G[a].pb(c); G[c].pb(a); } int ans1 = 0, ans2 = 0; for(int i=0; i
•  » » Same idea and i am facing the same issue.
•  » » I treated i as red and i+n as blue. Then I used union-find.
•  » » 3 months ago, # ^ | ← Rev. 2 →   Probably, the problem is multiple edgesInput1 11 R 1 BOutput1 0
•  » » » yeah it got accepted now.
•  » » » This was the edge case, thanks!Forgot to handle self cycle.
•  » » Colors don't matter, you can just DFS and check for cycles in each component
•  » » I just treated the graph as undirected and used: no of components with cycle = m — n + no_of_connected components
•  » » I faced the same problem and made 2 incorrect submissions. Finally got AC after I used DSU.
 » 3 months ago, # | ← Rev. 2 →   My solution for each problem are explained below. SpoilerA: just output $S_{i\oplus 1}$ for all $i$B: For all $i$, do $X_{X_{i}}=X_i$. Now the cells that have to call itself will automatically "do nothing". After we finish, count and enumerate indices where $X_i \neq i$.C: Just backtracking lolD: Just union-find lolE: I knew this was some matrix exponentiation task but I was too lazy so I just copy pasted a Reeds-Sloane templateG: Mo's. Update using the fact that each element $e$ with amount $v$ in the interval contributes $v \choose 3$ to the answer.
•  » » 3 months ago, # ^ | ← Rev. 2 →   Can you explain about the 2 by 2 matrix formula in the editorial for problem E? https://atcoder.jp/contests/abc293/editorial/5962
•  » » $E$ can be solved simpler. Let $f(x) = a^0 + a^1 + \dots + a^{x-1}$. Then:If $x$ is even $f(x) = f(\frac{x}{2}) + a^{\frac{x}{2}} \cdot f(\frac{x}{2})$.If $x$ is odd $f(x) = a^0 + a^1 \cdot f(\frac{x}{2}) + a^{\frac{x}{2} + 1} \cdot f(\frac{x}{2})$.Write simple recursion.About problem $F$. I precalculated answers and carefully looked at it. Then I calculated $a_x = \sqrt[\leftroot{-2}\uproot{2}x]{n}$ for all integer $x$, which are meaningfull. Then simply tried all numbers in ranges $[a_x - 10, a_x + 10]$. I have no idea, why it is correct.
•  » » » How to come up with these kind of equations please please tell. I can't find recurrence relations please
•  » » » Oh cool, this is much easier to understand. Thanks! I tried so hard to use the sum formula with mod inverse, little did I know that depending on M, it may not even exist :(
•  » » » » Can you help me understand it please please
•  » » » » » 3 months ago, # ^ | ← Rev. 2 →   If x = 4: f(x) = a^0 + a^1 + a^2 + a^3 = (a^0 + a^1) + a^2 * (a^0 + a^1) = f(x / 2) + a^(x / 2) * f(x / 2).If x = 5: f(x) = a^0 + a^1 + a^2 + a^3 + a^4 = a^0 + a^1 * (a^0 + a^1) + a^(x / 2 + 1) * (a^0 + a^1) = 1 + a * f(x / 2) + a^(x / 2 + 1) * f(x / 2).Hopefully this helps you understand the recursive formula.
•  » » » 3 months ago, # ^ | ← Rev. 3 →   .
•  » » » » 3 months ago, # ^ | ← Rev. 2 →   return 1%m;E is tricky that a^0 is not necessarily 1. When m==1, (a^0) % m is 0.
•  » » » » » got accepted thanks
•  » » » » » i forgot to add that case thanks for clearification
•  » » What is reeds sloane template where to find it
•  » » » It's an algorithm that finds linear recurrences given the sequence's first few values. The template is on here but I can assure you there are very few moments when you actually need it to solve a certain task (again, I used it because I was lazy)
•  » » » » How to find this kind of recurrence should we start from base to top with some hit and trial method. Or its my bad math that i can't find these relations?
 » 3 months ago, # | ← Rev. 2 →   Soltuion for d : Spoileridea was to do a dsu and count the number of cycles and remove that number from total groups to find other number n,m=map(int,input().split()) parent=[i for i in range(n+1)] def find(x): st=[] while parent[x]!=x: st.append(x) x=parent[x] while st: parent[st.pop()]=x return x ans=0 for _ in range(m): e=[el for el in input().split()] l=int(e) r=int(e) pl=find(l) pr=find(r) if pl==pr: ans+=1 else: parent[pl]=pr s=set() for i in range(1,n+1): find(i) for el in parent[1:]: s.add(el) print(ans,len(s)-ans) 
 » Solution for problem E using simple recursion Source Submission
 » 3 months ago, # | ← Rev. 2 →   Solution to F: It is possible to write a function that checks if a number x can be written in base b with 1s and 0s like this: Codebool good(ll x, ll b){ ll cur = 1; while(x){ ll next = cur*b; if(x==cur) return 1; if(cur>x) return 0; if(x%next==0){ cur = next; continue; } x-=cur; if(x%next==0){ cur = next; continue; } return 0; } return 1; } If the number written in the base b has many digits it means that b is small. If b is large it means that the mask (representation of n in base b) has few digits. By defining the threshold at 6 digits it means that we can check b until $\sqrt{maxn}\leq\sqrt{10^{18}}=1000$. And then we have large b's left (with few digits in the mask). We can check all the masks up to 6 digits and do a binary search to find if there is a b that matches the mask.My implementationTotal complexity per test case: $\Theta((1000+2^6)\log_b n)$
•  » » Wow, it seems that we have similar ideas(see my comments below). But, I don't have enough time to finish it during contest, and only solve it after contest.
 » Somehow I used an ugly method to solve problem F (after contest).For some base-b, at first we check all the combination of patterns (1/0)b^0+(1/0)b^1+...(1/0)b^4, and find all the valid b. Then, note that we have at most 10^(18/5) other candidates to check, and it suffices to implement brute-force for this part (this is beacuse we must start from at least b^5, and valid b must satisfy b<=10^3.6).But I think the editorial's idea is better to understand.
 » Can anyone explain the winner's (maspy) elegant solution to problem E?https://atcoder.jp/contests/abc293/submissions/39612056 A, X, M = map(int, input().split()) if A == 1: print(X % M) else: mod = M * (A - 1) x = pow(A, X, mod) - 1 x //= (A - 1) print(x % M) 
•  » » I think I might have an explanation to the "else" part.The original problem is equivalent to computing (a/b)%c. Suppose that (a/b)%c=r, then we must have a/b=qc+r, and a=qbc+rb, then we compute a%(bc)=0+rb (because r
•  » » » Great explanation, thanks!This is true when $a \equiv_{\mathrm{mod}\ b} 0$ (or in other words $a$ is divisible by $b$).
•  » » 3 months ago, # ^ | ← Rev. 2 →   It seems to be this obvious formula: Spoiler The if part avoids division by zero.
•  » » If you want to calculate ans = (X/D)%m(X/D) = K*(m) + ansX = K*(D*m) + D*ans=> X%(D*m) = D*ansans = (X%(D*m))//D
•  » » I actually had the same solution: https://atcoder.jp/contests/abc293/submissions/39630645The idea is that we need to divide by $X - 1$ in order to do the geometric sum formula, but the problem is that $X - 1$ may not have an inverse mod $M$ as we aren't given that $M$ is prime and large enough. So, we use the fact that if $Ar \equiv Br \pmod{Cr}$, then $A \equiv B \pmod{C}$. We calculate the numerator of the geometric sum mod $M(X-1)$ and divide both the residue and modulus by $X - 1$ in the end.You might also notice that $M(X-1)$ doesn't fit in a 32-bit integer, so even using long longs, multiplication will overflow, thus why both I and the person you referenced used Python.
 » what will be approach for C?
•  » » My approach#include using namespace std; int h,w,arr; int f(int x,int y,set s){ int cnt=0; s.insert(arr[x][y]); if(x==h-1&&y==w-1&&s.size()==h+w-1) return 1; else if(x==h-1&&y==w-1) return 0; if(x+1>h>>w; set s; for(int i=0;i>arr[i][j]; } } cout<
 » Is it possible to calculate a/b mod m for when b and m are not coprimes? I guess no in general right? (for values up to 10^18 for example). This would help in problem E if I knew I had to come up with a different approach. Is this common, realising you have to have a different approach because a/b is impossible?
•  » » What do you mean by $a / b mod m$. For cases when inverse of $b$ modulo $m$ exists, then $a / b$ is defined as $a . b^{-1}$.
•  » » » 3 months ago, # ^ | ← Rev. 6 →   Given 3 integers a, b and m 1<=a,b,m<=10^18 — calculate a/b mod (m). That is a divided by b mod m (or a/b%m in modular arithmetic I guess). Is it possible to solve this? Obviously it is possible when b has a modular inverse, but not possible otherwise?For example 10/2 mod 7 == 5 because the modular inverse of 2 mod 7 is 4. 10*4 mod 7 is 5And 9/2 mod 7 is 1And other example is 16/8 mod 8. Obvioulsy 16/8 is 2 and 2 mod 8 is 2. But there is no modular inverse of 8 mod 8.
 » 3 months ago, # | ← Rev. 2 →   E is tricky that a^0 is not necessarily 1. When m==1, (a^0) % m is 0.
 » How to solve E?
 » Java solution passes all test cases except 1 — TLE. https://atcoder.jp/contests/abc293/submissions/39664825Can someone help me ?
 » why 2/25 test cases are failing in problem C , can someone help me sumbission
•  » » try this testcase: 3 2 1 2 3 4 5 6 expected output:3
•  » » » thanks for the test case , base case was wrong:( , now got ac
 » Why did at coder stop uploading test cases after abc287 ? I'll unable to check my mistake
 » Hello all ! Anyone can teach me or give some ideas of how to solve the problem C with DFS iterative ? Thanks a lot !