AtCoder Beginner Contest 198 Announcement

4 года назад, # ^ |

See this problem: https://codeforces.net/problemset/problem/1307/B

→ Ответить

Rudro25

4 года назад, # ^ |

← Rev. 3 →

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<r){
     cout<<2<<endl;
     return;
   }
   ll ans=Ceil(dis,r);
   cout<<ans<<endl;

→ Ответить

spookywooky

4 года назад, # ^ |

+11

Thanks. Very funny edgecase :/

→ Ответить

dush1729

4 года назад, # ^ |

Yes that was the corner case. Thanks!

→ Ответить

OPyrohov

4 года назад, # ^ |

if distance < r answer = 2 — could you please explain, why?

→ Ответить

spookywooky

4 года назад, # ^ |

Obviously you cannot reach the point with one step, since with one step you can reach only points of distance exactly r.

→ Ответить

404butnoterror

4 года назад, # ^ |

if distance <r can we say 2*distance>r. can you please explain.

→ Ответить

spookywooky

4 года назад, # ^ |

with two steps we can go every distance between 0 and 2*r

→ Ответить

4 года назад, # ^ |

the answer is always less than or equal to $$$10^{5}\sqrt{2}$$$ so no need for binary search.. you can use linear search

→ Ответить

vineetjai

4 года назад, # ^ |

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

→ Ответить

AnandOza

4 года назад, # ^ |

By the way, the same edge case showed up on 1307B - Cow and Friend (very similar problem overall).

→ Ответить

4 года назад, # |

+14

How do you solve F?

→ Ответить

Iftekhar_Hakim_K

4 года назад, # ^ |

+25

Apparently it was A054473, but how to solve this formula? >_<

→ Ответить

RisingWizard

4 года назад, # ^ |

+12

How to search this on oeis? :')

→ Ответить

ncduy0303

4 года назад, # ^ |

I even tried google the same definition and couldn't find that formula lol

→ Ответить

meme

4 года назад, # ^ |

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.

→ Ответить

Samarth12

4 года назад, # ^ |

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?

→ Ответить

4 года назад, # ^ |

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?

→ Ответить

4 года назад, # ^ |

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+1

When we equate it to zero and consider x^15 as fn then I get the recursive formula you mentioned, but why does this work?

→ Ответить

4 года назад, # ^ |

Update: This works because of the formula from General Linear Recurrences

→ Ответить

4 года назад, # ^ |

AC solution

Code

int md = 998244353;

vector<vl> mul(const vector<vl> &a, const vector<vl> &b){
    vector<vl> 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<vl> 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<vl> b(15, vl(15));
    REP(i,15) b[i][i] = 1;
    vector<vl> 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<vl> c;
    for(int v:V) c.PB({v});

    b = mul(b, c);
    pl(b[0][0]);
    return 0;
}

→ Ответить

hitch_hiker42

4 года назад, # ^ |

-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.

→ Ответить

vineetjai

4 года назад, # |

How to solve D?

→ Ответить

4 года назад, # ^ |

There can be at most 10 distinct characters. So you have only 10! possible assignments, just try them all.

→ Ответить

vineetjai

4 года назад, # ^ |

← Rev. 4 →

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.

→ Ответить

4 года назад, # ^ |

If there are more than 10 distinct characters it is impossible

→ Ответить

4 года назад, # ^ |

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.

→ Ответить

rgnerdplayer

4 года назад, # ^ |

brute force all 10! permutations

→ Ответить

imtiyazrasool92

3 года назад, # ^ |

can you explain this a little bit more!

→ Ответить

4 года назад, # ^ |

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

→ Ответить

rishabhdeepsingh

4 года назад, # |

which TC am I missing? https://atcoder.jp/contests/abc198/submissions/21665135

→ Ответить

rgnerdplayer

4 года назад, # ^ |

If X*X+Y*Y<R*R, that is, the target is strictly inside the circle, then you need two steps.

→ Ответить

rishabhdeepsingh

4 года назад, # ^ |

still not working. https://atcoder.jp/contests/abc198/submissions/21694467

→ Ответить

rgnerdplayer

4 года назад, # ^ |

maybe precision errors, idk.

→ Ответить