atcoder_official's blog

AtCoder Beginner Contest 367 Announcement
By atcoder_official, history, 3 months ago, In English

We will hold AtCoder Beginner Contest 367.

We are looking forward to your participation!

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

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

In the codeforces handle section on profile page anyone can anyone's handle so what's the use of it?

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

    It is based on the trust system which is relatively common in Japan. For example, you have snacks that you can take and then put in the box the amount of money equal to their price. Nobody is watching to see whether you will put in the money or not, but everyone pays. Of course, there is no way this would work in western countries.

    For real though, what do you gain by putting someone else's handle?

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

I hope I can solve ABCD, and I hope everyone can get a good score.

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

Problem E: https://cp-algorithms.com/algebra/binary-exp.html#applying-a-permutation-k-times

Problem F: https://codeforces.net/blog/entry/85900?#comment-736594

atcoder_official I completely understand if there is a shortage of problems for ABCs, but what is the point of putting such well known problems? I would rather have an ABC maybe two times a month but with better problems.

→ Reply
  • »
    »
    3 months ago, # ^ |
      Vote: I like it -7 Vote: I do not like it

    ABCs nowadays are dogshit. First few probelms are usually ways trivial and most had appeared somewhere before, and the last one is usually too hard, only some chinese or IGM+ solve it LOL

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

HOW CAN SOMEONE WRITE SUCH WELL COMMENTED SOLUTION for PROBLEM A, under 40 seconds ( Provided, you have to read the question as well ) .

https://atcoder.jp/contests/abc367/submissions/56773722

UNLESS of course, GPT.

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

    I've had a look at his submissions, and it turns out that only A and B are coded in this style, as his submissions on problems C, D, E and F have completely different style and template.

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

How can this submition1 TLE in promblem E? About 30 minutes later i just add one line assert submition2 and pass. This bothers me very much in the contest.

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

    Can you explain your approach for the problem E ?

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

      This is the basic binary jumping problem. Usaco guide will help you, and problem E is like this CSES problem. In brief of E, just make the binary jumping table for X, and jumping k times for each start position i.

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

    Also the statement of problem D is very comfused, "The minimum number of steps required to walk clockwise from rest area s to rest area t". What minimum?

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

      If it didn't specify "minimum" then you could choose to walk all the way around the lake from $$$s$$$ back to $$$s$$$ any number of times, then continue to $$$t$$$, resulting in (potentially) different numbers of steps modulo $$$M$$$ for the same pair $$$(s, t)$$$.

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

        Can you help me explain why my approach for D is wrong

        My submission

        My approach : First I find all subarrays whose sum is multiple of M Secondly , I find all the subarrays such that their sum%mod equals entire arrays sum .

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

    I don't know why submission1 has TLE and submission2 doesn't have TLE.(some optimization?) But it is slow to access memory randomly. By accessing memory simultaneously for i=1..n, it becomes faster because of caching. https://atcoder.jp/contests/abc367/submissions/56834042

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

    diobrando97 I guess the assert changed the compiler optimization behavior, if you removed the unroll-loops optimization your code will pass, so the assert kind of prevents this optimization or changes its behavior.
    Just comment this out pragma GCC optimize("O3,unroll-loops")

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

      No assert and comment " #pragma GCC optimize("O3,unroll-loops")" =>TLE * 12

      No assert and comment " #pragma GCC optimize("O3,unroll-loops") #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")" => TLE * 4

      With assert and comment " #pragma GCC optimize("O3,unroll-loops") #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")" => Pass with 1978s

      Magic

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

can someone tell why this code fails for D? I translated the problem as, count of subarrays have sum % m == 0 and size of subarray >= 2. for that im using prefix sums. for an array a $$$ a_1, a_2, ..., a_n $$$, I create prefix sums with the array $$$ a_1, a_2, ..., a_n, a_1, a_2, ... a_n-1 $$$ . then I just count mods and calculate answer.

Submission

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

    Size of subarray can be taken to be 1 as well if you think. Main constraint is that the size of subarray can't be taken as n.

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

      I now understand that it can be taken as 1 but I think my code already deals with it. no clue what else is going wrong. ig i'll have to wait for testcases to come out on dropbox

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

    I modified your submission. Now it can pass.

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

      can you explain?

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

        Consider this test case;

        Spoiler

        There are only 2 rest areas. The answer is 2 (From 1 to 2 and from 2 to 1). Your solution outputs 4. It is over-counting.

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

          so if talk in terms of explanation, we have to adjust the sliding window before moving onto the ith index?

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

Problem E was basically this

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

how to solve d and f?

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

In problem G, if we don't care about the size of the subsequence being a multiple of M then we can use xor basis to find the basis size let's call it b.

Then the answer is 2^(n-b) * sum(representable value ^k)

However I hit a road bump when considering subsequence size, did any one solve it based on this approach?

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

Can Someone explain Problem F, I understood it was hashing but need some reference for it.

→ Reply