We will hold TOYOTA SYSTEMS Programming Contest 2021(AtCoder Beginner Contest 228).
- Contest URL: https://atcoder.jp/contests/abc228
- Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20211120T2100&p1=248
- Duration: 100 minutes
- Number of Tasks: 8
- Writer: Kodaman, leaf1415, physics0523
- Tester: math957963, Nyaan
- Rated range: ~ 1999
The point values will be 100-200-300-400-500-500-600-600.
We are looking forward to your participation!
Best of luck everyone!
is it hard than regular ABC or it's only for me ?
Each time there is a sponsor involved, the contest seems to be harder.
This time I struggled a lot on the implementation.
Would be stuck on C if the clarification had not come. I was finding if K rank is possible or not instead of top K. Happened with someone else?
I specifically used python for E to avoid overflow but still getting WA. What am I doing wrong here?
I too faced same problem, not sure what's the issue here (4 test cases were WA)
Answer should be 0 if $$$M \equiv 0 \mod 998244353$$$. Euler's theorem only applies if $$$M$$$ is coprime to the modulo.
I also submitted same logic code throughout the contest and got 5 Wa , later resubmitted with excluding the case that if (m%mod ==0 ) cout<<0 and it got accepted , the edge case we fell on was that our code will give 1 instead of 0 if k^n was divisible by mod-1 because in the mpow function ret is initialized to 1 so if no operation are performed (i.e b is 0)it will always return 1
2 998244352 998244353
The answer should be 0 for this but your code will print 1. Same thing happened with mine then I check if M is multiple of 998244353 answer should be 0
See https://en.wikipedia.org/wiki/Fermat%27s_little_theorem, the second equation is only valid if $$$p \nmid a$$$.
You need to check for $$$998244353 \mid M$$$. If this is $$$0$$$ you must output $$$0$$$.
thanks
Might be a stupid question: Is there a lemma or sth, which states how to deal with mod powers? Is this the "general" way of trying to reduce the term via Fermat's Little Theorem? (Like stated in the editorial) My stupid ass thought that just applying modPow would be ok( without -1 in the first mod):
For task D i used another array of same size consisting of 0s in place of -1 and update it's value to 1 if a positive value is assigned to an index and made range sum query to find the next h having (a[h] == -1). Where am i going wrong? my submission
in d i used brute forced passed 18/19 cases got tle in one of it please tell there is only short change or complete another implementation for accepted ones i have got no idea after seeing 1 or 2 solution please also tell how u guys got approach or how u thought thnx in advance
Use set, you will get accepted.
Initially store all the values from 1 to N in the set and now for every query of type 1 find the lower_bound of x % N. If lower_bound doesn't exists then take the first element because that will be closest to the x. After that set this value to x and erase it from the set.
I used brute force and saw only 2 TLEs. Then I used a hash table to memoize the jump. Only 1 TLE left.
Finally I changed the hash table to a vector. Then I got AC.
can u plz share link of solution as i too used vector and got 1 tle https://atcoder.jp/contests/abc228/submissions/27393225 here is the link of my solution can u plz share your username of atcoder or your solution link
My solution link: https://atcoder.jp/contests/abc228/submissions/27398060
can u plz explain whats vector w is doing in your solution
Vector w is the memo-ization of the linear probing. Instead of jumping from, eg, 1->2->3->...->M, we can jump directly from 1->M.
Can anyone please explain why
this passes for all test cases in E
we wanna calculate m ^ (k ^ n)
say cnt = k ^ n
now m ^ cnt = m ^ (cnt % (mod — 1)) by fermat's little theorem.
Edit: If you want video explanation u can see my solutions video here
Why we have to add (mod-1) with x in binpow(m, x + mod — 1, mod)?
The only case where
binpow(m, x, mod)
gives wrong answer is $$$m = a \cdot \text{mod}$$$, $$$x = b \cdot (\text{mod}-1)$$$ (because it's evaluated as $$$0^0$$$, that equals $$$1$$$ according to binpow). If you add $$$\text{mod}-1$$$, it becomes $$$0^{\text{mod}-1} = 0$$$.Yes I covered that case in the video, I find it harder to explain in text, so I linked the video
In problem E this Binary Exponentiation code gives WA
it gives the correct answer when I add n %= mod
why is this line needed?
Here are the video Solutions to the first 5 problems in case you prefer that.
For problem A in the case
0 0 0
.The answer is supposed to be NO .How is it possible that it is YES.s!=t