chokudai's blog

AtCoder Beginner Contest 262 Announcement
By chokudai, history, 21 month(s) ago, In English

We will hold AtCoder Beginner Contest 262.

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!

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

Comments Comments (13)
| Write comment?
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Similar D

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +3 Vote: I do not like it

Unfortunately, Ex is exactly the same as this Chinese problem which came out in 2017 at Tsinghua University training camp. :(

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
    ← Rev. 2   Vote: I like it +3 Vote: I do not like it

    Well, the constraints are not exactly the same, but a Chinese tutorial gave a solution with a complexity of $$$O(q\log q)$$$.

    → Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
»
21 month(s) ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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 %100 and %size so 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)$$$?

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yup it is.. I solved it with $$$O(n^3)$$$.

    Here is my submission

    → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

    → Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
21 month(s) ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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.

→ Reply
»
21 month(s) ago, # |
← Rev. 2   Vote: I like it -10 Vote: I do not like it

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

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
    ← Rev. 2   Vote: I like it -10 Vote: I do not like it

    I'd say this is $$$O(n^2 \log n)$$$ . For $$$N=3000$$$ bitset intersect 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.

    → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      I'd rather say this is $$$O(\dfrac{n^3}{\omega})$$$ :)

      → Reply