We will hold AtCoder Beginner Contest 198.

- Contest URL: https://atcoder.jp/contests/abc198
- Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20210411T2100&p1=248
- Duration: 100 minutes
- Number of Tasks: 6
- Writer: Kmcode, kyopro_friends, sheyasutaka, tatyam, YoshikaMiyafuji
- Rated range: ~ 1999

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

We are looking forward to your participation!

How to solve C? I tried binary search to avoid precision issue, and even python to avoid overflow issues. Still fails on 3 testcases.

it ruined the contest for me

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

c is just the ceil value of distance and r.

corner case: if distance < r answer = 2

SpoilerThanks. Very funny edgecase :/

Yes that was the corner case. Thanks!

`if distance < r answer = 2`

— could you please explain, why?Obviously you cannot reach the point with one step, since with one step you can reach only points of distance exactly r.

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

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

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

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

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

How do you solve F?

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

How to search this on oeis? :')

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

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.

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:

Next, you can simply use matrix exponentiation. But, can someone provide a proof of this recursion?

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?

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?

Update: This works because of the formula from

`General Linear Recurrences`

AC solution

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

How to solve D?

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

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.

If there are more than 10 distinct characters it is impossible

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.

brute force all 10! permutations

can you explain this a little bit more!

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

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

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

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

maybe precision errors, idk.

Might be a precision issue

`91 20 89`

your code gives 1 but the answer is 2From the editorial on F (https://atcoder.jp/contests/abc198/editorial/1080):

What does this mean? Does anyone know what $$$t$$$ refers to?

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})