We will hold AtCoder Beginner Contest 262.
- Contest URL: https://atcoder.jp/contests/abc262
- Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20220731T2100&p1=248
- Duration: 100 minutes
- Number of Tasks: 8
- Writer: m_99, Kodaman, kyopro_friends, leaf1415, PCTprobability, nok0
- Tester: PCTprobability, physics0523
- Rated range: ~ 1999
The point values will be 100-200-300-400-500-500-600-600. Since this is used as a qualification round of a local contest,
- Earlier problems are easy to implement.
- Later problems have similar difficulties.
- The style of problems are slightly different (though closer to normal ABCs than to normal ARCs).
We are looking forward to your participation!
Similar D
Unfortunately, Ex is exactly the same as this Chinese problem which came out in 2017 at Tsinghua University training camp. :(
Well, the constraints are not exactly the same, but a Chinese tutorial gave a solution with a complexity of $$$O(q\log q)$$$.
Can someone explain in sample code D line 24 how to be correct?
I tried similar dp table like my submission but failed to make thin.
Can anyone tell me why does $$$O(n^4)$$$ work for Problem D?
This is my AC solution: https://atcoder.jp/contests/abc262/submissions/33695369
I tried to do it without the outer loop (here: https://atcoder.jp/contests/abc262/submissions/33690321 ) but then realized that I cannot do
%100and%sizeso that's the reason why the outer loop is necessary (so that remainders are a result of 1 division).I was trying to find $$$O(n^3)$$$, but turns out $$$O(n^4)$$$ is fine here. How come?
Would it be possible to do $$$O(n^3)$$$?
Yup it is.. I solved it with $$$O(n^3)$$$.
Here is my submission
I dont think so, your recur() which is O(N^3) runs N times and you reset your dp array(with worst case O(N^3) space complexity) N times too.
Can you please what is wrong with %100.
What I actually did: My dp states are i(index),rem(curr sum%100),l(curr length)
My transitions would be : Either I would take that element or not.
int ans=0;
ans+=rec(i+1,(rem+a[i])%100,l+1,n); // Took that element
ans+=rec(i+1,rem,l,n); // Didn't took that element
dp[i][rem][l]=ans
My Code : Link.
Thank you in advance for helping
Can anyone try to find a counter case for this F implementation (I'm pretty sure the idea is right, but I guess I've missed some cases during contest).
Submission
This code appeared in "My submissions" and it is still visible there. When I finished A and turned to B during the contest, I noticed that there was a code, about 500 bytes long, So I checked it and found it WAS NOT my code(My code template has a length of 4000 byte+). Please fix the bug plz.
$$$Problem$$$ $$$B$$$ can be solved in $$$O(n^2)$$$. Submission
Here is the hard version of $$$Problem$$$ $$$B$$$ which requires $$$O(n^2)$$$.
UPD: Above approach is $$$O(n ^ 3 / w)$$$, $$$w$$$ depends upon architecture (either $$$32$$$ or $$$64$$$).
I'd say this is $$$O(n^2 \log n)$$$ . For $$$N=3000$$$
bitsetintersect is no longer constant time.edit: Person below me has rightfully corrected me. It's 3000 bits that are necessary, not log(3000) bits (as is the case for example for Knapsack problem).
Thanks for rewarding discussion with negative comments. I will definitely avoid participating given that you guys found this discussion so unhelpful. I found the person above me and below me very helpful and I have learnt a bit.
I'd rather say this is $$$O(\dfrac{n^3}{\omega})$$$ :)