We will hold AtCoder Beginner Contest 293.

- Contest URL: https://atcoder.jp/contests/abc293
- Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20230311T2100&p1=248
- Duration: 100 minutes
- Number of Tasks: 8
- Writer: cn449, leaf1415, kyopro_friends, m_99, PCTprobability
- Tester: yuto1115, kyopro_friends
- Rated range: ~ 1999

The point values will be 100-200-300-400-500-500-600-600. We are looking forward to your participation!

What is the counter test case for this problem B's solution? I kept getting WA.

ugly code5

3 4 1 5 4

For this test case, your code gives wrong answer.

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

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

SpoilerI treated

`i`

as red and`i+n`

as blue. Then I used union-find.Probably, the problem is multiple edges

Input

`1 1`

`1 R 1 B`

Output

`1 0`

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 componentsMy 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 lol

D: Just union-find lol

E: I knew this was some matrix exponentiation task but I was too lazy so I just copy pasted a Reeds-Sloane template

G: Mo's. Update using the fact that each element $$$e$$$ with amount $$$v$$$ in the interval contributes $$$v \choose 3$$$ to the answer.

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.

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

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.

.

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

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

Solution for problem E using simple recursion Source Submission

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:

CodeIf 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[6]{maxn}\leq\sqrt[6]{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 implementation

Total 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

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<c, so rb<rc), and thus r=(a%(bc))/b.

In fact, I decided to use this at first, but I kept getting WA at sample3 so I gave it up.

Great explanation, thanks!

This is true when $$$a \equiv_{\mathrm{mod}\ b} 0 $$$ (or in other words $$$a$$$ is divisible by $$$b$$$).

It seems to be this obvious formula:

SpoilerThe

`if`

part avoids division by zero.If you want to calculate ans = (X/D)%m

(X/D) = K*(m) + ans

X = K*(D*m) + D*ans

=> X%(D*m) = D*ans

ans = (X%(D*m))//D

I actually had the same solution: https://atcoder.jp/contests/abc293/submissions/39630645

The 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 approachIs 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}$$$.

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 5

And 9/2 mod 7 is 1

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

E is tricky that

`a^0`

is not necessarily`1`

. When`m==1`

,`(a^0) % m`

is`0`

.How to solve E?

why 2/25 test cases are failing in problem C , can someone help me sumbission

try this testcase:

expected output:3

thanks for the test case , base case was wrong:( , now got ac