Блог пользователя chokudai

Автор chokudai, история, 3 года назад, По-английски

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!

  • Проголосовать: нравится
  • +30
  • Проголосовать: не нравится

»
3 года назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

Best of luck everyone!

»
3 года назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

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

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

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

    This time I struggled a lot on the implementation.

»
3 года назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

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?

»
3 года назад, # |
Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

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

Spoiler
  • »
    »
    3 года назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    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)
    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится +16 Проголосовать: не нравится

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

    • »
      »
      »
      3 года назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      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

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

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

  • »
    »
    3 года назад, # ^ |
    Rev. 6   Проголосовать: нравится 0 Проголосовать: не нравится

    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;
    
»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится

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

  • »
    »
    3 года назад, # ^ |
    Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

    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

  • »
    »
    3 года назад, # ^ |
    Rev. 2   Проголосовать: нравится +4 Проголосовать: не нравится

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

    • »
      »
      »
      3 года назад, # ^ |
      Rev. 2   Проголосовать: нравится +9 Проголосовать: не нравится

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

      • »
        »
        »
        »
        3 года назад, # ^ |
          Проголосовать: нравится +4 Проголосовать: не нравится

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

»
3 года назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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?

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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