chokudai's blog

AtCoder Beginner Contest 262 Announcement
By chokudai, history, 2 years 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?
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Similar D

→ Reply
»
2 years 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
»
2 years 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
»
2 years 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
  • »
    »
    2 years 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
    • »
      »
      »
      2 years 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
  • »
    »
    2 years 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
»
2 years 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
»
2 years 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
»
2 years 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
  • »
    »
    2 years 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
    • »
      »
      »
      2 years 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