### chokudai's blog

By chokudai, history, 13 months ago,

We will hold AtCoder Beginner Contest 198.

The point values will be 100-200-300-400-500-600.

We are looking forward to your participation!

• +37

 » 13 months ago, # |   0 Thanks, these type of contests are helpful for beginners like me.
 » 13 months ago, # |   +2 How to solve C? I tried binary search to avoid precision issue, and even python to avoid overflow issues. Still fails on 3 testcases.
•  » » 13 months ago, # ^ |   +1 it ruined the contest for me
•  » » 13 months ago, # ^ |   0 See this problem: https://codeforces.com/problemset/problem/1307/B
•  » » 13 months ago, # ^ | ← Rev. 3 →   +9 c is just the ceil value of distance and r.corner case: if distance < r answer = 2 Spoiler ll r,x,y; cin>>r>>x>>y; ll bal=((x*x)+(y*y)); ll dis=sqrt(bal); if((dis*dis)!=bal) dis++; if(dis
•  » » » 13 months ago, # ^ |   +11 Thanks. Very funny edgecase :/
•  » » » 13 months ago, # ^ |   0 Yes that was the corner case. Thanks!
•  » » » 13 months ago, # ^ |   0 if distance < r answer = 2 — could you please explain, why?
•  » » » » 13 months ago, # ^ |   +3 Obviously you cannot reach the point with one step, since with one step you can reach only points of distance exactly r.
•  » » » » » 13 months ago, # ^ |   0 if distance r. can you please explain.
•  » » » » » » 13 months ago, # ^ |   0 with two steps we can go every distance between 0 and 2*r
•  » » » » » » » 13 months ago, # ^ |   0 yeah.. thanks understood
•  » » 13 months ago, # ^ |   +8 the answer is always less than or equal to $10^{5}\sqrt{2}$ so no need for binary search.. you can use linear search
•  » » 13 months ago, # ^ |   0 Binary Search will be able to help you with some part of this problem. But, for checking if the number is a perfect square or not you have to calculate its the number of divisors can be odd or not. Link to my submission
•  » » 13 months ago, # ^ |   0 Spoiler#include #define fast {ios_base::sync_with_stdio(false);cin.tie(NULL);} using namespace std; typedef long long int ll; const int mxn=2e5+5,mod=1e9+7; int main(void){ fast; ll x,y,r; cin>>r>>x>>y; ll d=x*x+y*y; ll dis=0,steps=0; bool ok=0; if(d=d) break; } cout<
•  » » 13 months ago, # ^ |   0 Idea is really simple, if d is divisible by r then d/r is answer else walk from 0,0 to x,y in r steps until you get a isoscles triangle such that base(rem) is less then 2r(triangle inequality) and then add 2 to the answer and break.Code: Code//Think simple yet elegant. #include using namespace std; #define fast ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); #define ll long long #define all(v) v.begin(),v.end() #define ff first #define ss second #define pb push_back #define mp make_pair #define pi pair #define REP(i,n) for(int i=0;i> r >> x >> y; double d = sqrt(x*x + y*y); double rem = d; int ans=0; ll xx = floor(d); if(abs(d-xx)<1e-6 and xx%r==0LL){ cout<
•  » » 13 months ago, # ^ |   +1 By the way, the same edge case showed up on 1307B - Cow and Friend (very similar problem overall).
 » 13 months ago, # |   +14 How do you solve F?
•  » » 13 months ago, # ^ |   +25 Apparently it was A054473, but how to solve this formula? >_<
•  » » » 13 months ago, # ^ |   +12 How to search this on oeis? :')
•  » » » 13 months ago, # ^ |   +3 I even tried google the same definition and couldn't find that formula lol
•  » » » 13 months ago, # ^ |   +3 Here is the painful process I went through to derive it. Burnside lemma Scroll down to "Group of permutations of the cube in cyclic representation" on this page + manually count every cycle type For every cycle type, find the count of its fixed points. Trivial enough to do for all cycles being of equal length (it is exactly the same as Task A in the contest!) This left me with cycle types (1, 1, 4) and (1, 1, 2, 2). Do a little math to reduce their expressions. By a little, I mean a lot by the standards of competitive programming. The former is easier wherein you have to solve $4a + b + c = s$. Write it as $b + c = s - 4a$ and create an arithmetic series accordingly. The latter is more involved, but involves thinking along similar lines. The AC submission came a few minutes after the contest end.
•  » » » 13 months ago, # ^ |   +6 Thanks for the link, from here we can solve the problem in $O(15^3*log(S))$. Notice that using denominator of the generating function given in the link, we can write the recursion for the answer. The recursion is as follows: $f_n = f_{n-1} + 2f_{n-2} - 2f_{n-4} - 4f_{n-5} + f_{n-6} + 3f_{n-7} + 3f_{n-8} + f_{n-9} - 4f_{n-10} - 2f_{n-11} + 2f_{n-13} + f_{n-14} - f_{n-15}$Next, you can simply use matrix exponentiation. But, can someone provide a proof of this recursion?
•  » » » » 13 months ago, # ^ |   0 Notice that using the denominator of the generating function given in the link, we get the recursion, can you elaborate on how did you arrive at it?
•  » » » » » 13 months ago, # ^ |   0 When we simplify the polynomial in the denominator, we get x^{15}-x^{14}-2x^{13}+2x^{11}+4x^{10}-x^9-3x^8-3x^7-x^6+4x^5+2x^4-2x^2-x+1When we equate it to zero and consider x^15 as fn then I get the recursive formula you mentioned, but why does this work?
•  » » » » 13 months ago, # ^ |   0 Update: This works because of the formula from General Linear Recurrences
•  » » » 13 months ago, # ^ |   0 AC solution Codeint md = 998244353; vector mul(const vector &a, const vector &b){ vector c( a.size(), vl( b[ 0 ].size() ) ); for(int i = 0; i < a.size(); ++i) for(int j = 0; j < b[ 0 ].size(); ++j) for(int k = 0; k < a[ 0 ].size(); ++k){ c[i][j] = (c[i][j] + a[i][k] * b[k][j])%md; if(c[i][j] < 0){ c[i][j] = (c[i][j] + md)%md; } } return c; } int main(){ vl V = {1, 1, 3, 5, 10, 15, 29, 41, 68, 98, 147, 202, 291, 386, 528}; vl Y = {1, 1, 3, 5, 10, 15, 29, 41, 68, 98, 147, 202, 291, 386, 528}; reverse(ALL(V)); vector M; M.PB({1, 2, 0, -2, -4, 1, 3, 3, 1, -4, -2, 0, 2, 1, -1}); for(int i=0;i<14;i++) M.PB(vl(15)); for(int i=1;i<=14;i++){ M[i][i-1] = 1; } vector b(15, vl(15)); REP(i,15) b[i][i] = 1; vector a = M; dsl(S); S -= 6; debug() << imie(S); if(S<15) return !pl(Y[S]); S -= 14; // Fast matrix multiplication ll p = S; while( p > 0 ){ if( p & 1 ) b = mul( b, a ); a = mul( a, a ); p >>= 1; } vector c; for(int v:V) c.PB({v}); b = mul(b, c); pl(b[0][0]); return 0; } 
•  » » 13 months ago, # ^ |   -7 I wonder if it can be solved with matrix exponentiation.. or probably it has something to do with generating functions as atcoder is helplessly in love with convolutions these days.
 » 13 months ago, # |   0 How to solve D?
•  » » 13 months ago, # ^ |   0 There can be at most 10 distinct characters. So you have only 10! possible assignments, just try them all.
•  » » » 13 months ago, # ^ | ← Rev. 4 →   0 Why? Isn't each string is of max length 10. So, no of distinct characters min(26,len(s1)+len(s2)+len(s3))?Is there any proof?EDit: Got it. Because only 10 numbers are present.
•  » » » » 13 months ago, # ^ |   0 If there are more than 10 distinct characters it is impossible
•  » » » » 13 months ago, # ^ |   +3 Say there were 11 characters. All of them must have distinct assignments. But there are only 10 digits. So, 2 characters must have the same assignment — not allowed.
•  » » » » » 13 months ago, # ^ |   0 Well the condition says that "The x-th character of Si and the y-th character of Sj is the same if and only if the x-th character of N′i and the y-th character of N′j are the same."But it doesn't say that if two characters of Si and Sj are not equal then the corresponding digits of Ni' and Nj' also needs to be different. What will you say on this?
•  » » 13 months ago, # ^ |   +3 brute force all 10! permutations
•  » » » 6 months ago, # ^ |   0 can you explain this a little bit more!
•  » » 13 months ago, # ^ |   0 Try to assign the available letters different integer values and see if the equality $N_1 + N_2 = N_3$ holds the complexity is something like 10! like this https://atcoder.jp/contests/abc198/submissions/21669254
•  » » 13 months ago, # ^ |   0 Just brute force over all possible permutations of digits.Complexity: $O(10!)$ Spoiler#include #define fast {ios_base::sync_with_stdio(false);cin.tie(NULL);} #define ld long double using namespace std; typedef long long int ll; const int mxn=2e5+5,mod=1e9+7; int main(void){ fast; int i; bool ok=0; string s1,s2,s3; cin>>s1>>s2>>s3; sets; for(char c:s1) s.insert(c); for(char c:s2) s.insert(c); for(char c:s3) s.insert(c); if(s.size()>10) cout<<"UNSOLVABLE"; else{ int n1=s1.length(),n2=s2.length(),n3=s3.length(); ll a,b,c; int n=s.size(); int code[26],cr=0; int p[10]={0,1,2,3,4,5,6,7,8,9}; do{ cr=0; for(auto x:s){ code[x-'a']=p[cr]; ++cr; } if(code[s1[0]-'a']==0||code[s2[0]-'a']==0||code[s3[0]-'a']==0) continue; a=0,b=0,c=0; for(i=0;i
 » 13 months ago, # |   0 which TC am I missing? https://atcoder.jp/contests/abc198/submissions/21665135
•  » » 13 months ago, # ^ |   +3 If X*X+Y*Y
•  » » » 13 months ago, # ^ |   0 still not working. https://atcoder.jp/contests/abc198/submissions/21694467
•  » » » » 13 months ago, # ^ |   0 maybe precision errors, idk.
•  » » » » 13 months ago, # ^ |   0 Might be a precision issue 91 20 89 your code gives 1 but the answer is 2
•  » » » » » 13 months ago, # ^ |   0 Thanks
 » 13 months ago, # |   0 Can any body tell mw why I am getting wrong answer, when I am finding ceil using this method https://atcoder.jp/contests/abc198/submissions/21696421 and correct answer for https://atcoder.jp/contests/abc198/submissions/21696390Please can any body clarify when to use which method.
 » 13 months ago, # |   0 From the editorial on F (https://atcoder.jp/contests/abc198/editorial/1080): This time, the carry is at most $t$, so we only have to consider the range $0\le j\le 5$. What does this mean? Does anyone know what $t$ refers to?
 » 13 months ago, # |   0 Can anyone kindly provide me with a test case where my submission produces wrong answer, it seems that Atcoder has not yet updated the test cases for ABC 198 but this problem is quite bugging me.
 » 13 months ago, # | ← Rev. 3 →   0 For F, consider the solution : Link I built all the general transformations from original cube and then applied burnside lemma. For each unique transformation, I got connected components and their sizes and from then I solved using matrix exponentiation for each of them. Time Complexity should be (16*16*16*6*log(6) {for building all the states} + 24*(2^6)*(6*6*6)*log(S) {for calculating answer corresponding to all unique states})
 » 8 months ago, # |   0 Why 1st gives AC and 2nd gives WA? //AC double r,x,y; cin >> r >> x >> y; long double dis = sqrt(x*x + y*y); if( dis < r ) cout << "2"; else cout << ceil( dis/r ); // WA int r,x,y; cin >> r >> x >> y; long double dis = sqrt(x*x + y*y); if( dis < (long double)r ) cout << "2"; else cout << ceil( dis/r );