We will hold AtCoder Beginner Contest 367.
- Contest URL: https://atcoder.jp/contests/abc367
- Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20240817T2100&p1=248
- Duration: 100 minutes
- Writer: physics0523, toam, ynymxiaolongbao
- Tester: yuto1115, cn449
- Rated range: ~ 1999
- The point values: 150-150-300-400-450-500-675
We are looking forward to your participation!
In the codeforces handle section on profile page anyone can anyone's handle so what's the use of 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?
I hope I can solve ABCD, and I hope everyone can get a good score.
Problem E: https://cp-algorithms.com/algebra/binary-exp.html#applying-a-permutation-k-times
Problem F: https://mirror.codeforces.com/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.
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
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.
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.
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.
Can you explain your approach for the problem E ?
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.
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?
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)$$$.
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 .
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
got it, thank you!
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")
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
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
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.
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
I modified your submission. Now it can pass.
can you explain?
Consider this test case;
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.
so if talk in terms of explanation, we have to adjust the sliding window before moving onto the ith index?
Problem E was basically this
how to solve d and f?
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?
Can Someone explain Problem F, I understood it was hashing but need some reference for it.
You can use set hash for this problem. If you dont know about the topic: watch this: video
Thanks. I will look into it.