chokudai's blog

TOYOTA SYSTEMS Programming Contest 2021(AtCoder Beginner Contest 228) Announcement
By chokudai, history, 3 years ago, In English

We will hold TOYOTA SYSTEMS Programming Contest 2021(AtCoder Beginner Contest 228).

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

We are looking forward to your participation!

  • Vote: I like it
  • +30
  • Vote: I do not like it

Comments Comments (29)
| Write comment?
»
3 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Best of luck everyone!

→ Reply
»
3 years ago, # |
  Vote: I like it +8 Vote: I do not like it

is it hard than regular ABC or it's only for me ?

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Each time there is a sponsor involved, the contest seems to be harder.

    This time I struggled a lot on the implementation.

    → Reply
»
3 years ago, # |
  Vote: I like it +2 Vote: I do not like it

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?

→ Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

I specifically used python for E to avoid overflow but still getting WA. What am I doing wrong here?

Spoiler
→ Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    I too faced same problem, not sure what's the issue here (4 test cases were WA)


    def mpow(a,b,mod):
    ret=1
    a%=mod
    while b>0:
        if b&1:
            ret=(ret*a)%mod
        a=(a*a)%mod
        b>>=1
    
    return ret

N,K,M = map(int, input().split())
mod=998244353
v1=mpow(K,N, mod-1)

v2=mpow(M,v1, mod)
print(v2%mod)
    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +16 Vote: I do not like it

      Answer should be 0 if $$$M \equiv 0 \mod 998244353$$$. Euler's theorem only applies if $$$M$$$ is coprime to the modulo.

      → Reply
    • »
      »
      »
      3 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      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

      → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

    → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

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

    → Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 6   Vote: I like it 0 Vote: I do not like it

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

        ll rem = modPow(k, n, mod); // calculating r
    ll ret = modPow(m, rem, mod); // getting the result
    cout << ret;
    → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    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.

    → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
»
3 years ago, # |
  Vote: I like it +7 Vote: I do not like it

Can anyone please explain why 

long long n, m, k; cin >> n >> k >> m;
long long x = binpow(k, n, mod - 1);
cout << binpow(m, x + mod - 1, mod);

this passes for all test cases in E

→ Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 2   Vote: I like it +5 Vote: I do not like it

    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

    → Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 2   Vote: I like it +4 Vote: I do not like it

    Why we have to add (mod-1) with x in binpow(m, x + mod — 1, mod)?

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
      ← Rev. 2   Vote: I like it +9 Vote: I do not like it

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

      → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it +4 Vote: I do not like it

        Yes I covered that case in the video, I find it harder to explain in text, so I linked the video

        → Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

In problem E this Binary Exponentiation code gives WA

int pwmd(int n, int m,int mod) {
  int res = 1;
  // n %= mod;     correct ans when this line is added
  while (m > 0) {
    if (m & 1)
      res = (res % mod * n % mod) % mod;
    m >>= 1;
    n = (n % mod * n % mod) % mod;
  }

  return res;
}

it gives the correct answer when I add n %= mod

why is this line needed?

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Here are the video Solutions to the first 5 problems in case you prefer that.

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

For problem A in the case 0 0 0.The answer is supposed to be NO .How is it possible that it is YES.

→ Reply