chokudai's blog

By chokudai, history, 4 weeks ago, In English

We will hold Sciseed Programming Contest 2021(AtCoder Beginner Contest 219).

The point values will be 100-200-300-400-500-500-600-600.

We are looking forward to your participation!

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

»
4 weeks ago, # |
  Vote: I like it +73 Vote: I do not like it

One of the best educational contests. Thanks atcoder!

»
4 weeks ago, # |
  Vote: I like it +44 Vote: I do not like it

What a action packed day tommorow :0

ABC -> CF -> kickstart back to back with around 30 min break in between each of them.

»
4 weeks ago, # |
  Vote: I like it +10 Vote: I do not like it

so the recent AtCoder rounds have two extra problems than the regular ones we used to, these two problems have 500, 600 difficulty, maybe it worth increasing the contest time a little?

»
4 weeks ago, # |
  Vote: I like it -26 Vote: I do not like it

Hope this contest will bring good luck to me in CSP-S 2021 (1st round) tomorrow :)

P.S. If you don't know what CSP is click here

»
4 weeks ago, # |
  Vote: I like it +20 Vote: I do not like it

HardCoder

»
4 weeks ago, # |
Rev. 2   Vote: I like it +3 Vote: I do not like it

For me C/D was too hard according to previous :(

Ho to solve D ?

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    felt really good after solving today's C ...actually the given string can be compared with abcde....z and then normal sort function can be used ... got it after 30 minutes ...but felt really good after solving :D

    • »
      »
      »
      4 weeks ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      i did the same xD
      convert given string to abcdef--- and again convert from abcdef-- to given string :3

  • »
    »
    4 weeks ago, # ^ |
    Rev. 2   Vote: I like it +12 Vote: I do not like it

    D was dp.

    $$$dp[i][j][k]=$$$minimum no. of meals we can buy from first $$$i$$$ meals so that we have at least $$$j$$$ items of first type and $$$k$$$ items of second type.

    Transitions:

    $$$dp[i][j][k]=min(dp[i-1][j][k],1+dp[i-1][j-a_i][k],1+dp[i-1][j][k-b_i],1+dp[i-1][j-a_i][k-b_i])$$$

    Code
    • »
      »
      »
      4 weeks ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      what do transitions mean with fixed k and fixed j?(when we take only one part of lunchbox or something)

      • »
        »
        »
        »
        4 weeks ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        It means that we take the $$$i-th$$$ box but count only the items of first or second type.

        • »
          »
          »
          »
          »
          4 weeks ago, # ^ |
          Rev. 2   Vote: I like it 0 Vote: I do not like it

          Hey, can you explain why this discrete dp doesn't work? I mean when ith lunchbox is taken then we will only get a[i] and b[i] (which is discrete). I don't understand why we are doing continuous dp, over here. It would a great help. Thnx.

          code
    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      This gives WA on the test cases added after contest.

      • »
        »
        »
        »
        4 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Hello, thanks for reminding, it was a small mistake in loop, I corrected it now :)

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    basically knapsack like dp

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    D can be solved using Dynamic Programming. Approach: Let dp(i, j, k) be the minimum number of boxes to eat from first i boxes in order to get j octopus balls and k fish-shaped cakes. The transitions will be

    dp(i, j, k) = min(
        1 + dp(i - 1, min(x, j + a[i]), min(y, k + b[i])),
        dp(i - 1, j, k)
    )
    

    . Where x and y are X and Y (given as inputs)

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Hi, Could you please tell the significance of min(x,j+a[i]) and min(y,k+b[i]) in your code? I wrote just 1+dp(i-1,j+a[i],k+b[i]) and got WA / RE etc. How does it affect the logic?

      • »
        »
        »
        »
        4 weeks ago, # ^ |
        Rev. 3   Vote: I like it 0 Vote: I do not like it

        Hello!

        See the constraints given in the problem. It's N <= 300 and Ai, Bi <= 300 which means (j + a[i]) and / or (k + b[i]) can go upto 300 * 300 which results in RE(due to out of bounds). But, think what happens when (j + a[i]) or (k + b[i]) becomes >= x or y? Whenever (j + a[i]) becomes >= x, we have achieved the goal of getting >= x octopus balls given in the problem. So, we can consider all values (j + a[i]) >= x as x (this is done to avoid Runtime Errors) since we just need to get any number of balls >= x and so we don't care if we have got > x balls or = x balls. The same applies to (k + b[i]) too. Hence, the reason I take min(x, j + a[i]) instead of (j + a[i]) is to make sure that this parameter never exceeds x.

        P.S: It took me 5 incorrect submissions to find this!

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

          I see I see I understand it now! Thank you! Whoa 5 attempts, looks like a very important optimization!

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I solved Problem D using dp.

»
4 weeks ago, # |
  Vote: I like it +9 Vote: I do not like it

The implemention of E and F was so painful (at least for me) !!!!!

»
4 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

Can someone share a neat implemeantaion of pE?

»
4 weeks ago, # |
  Vote: I like it +6 Vote: I do not like it

For me the gap from D to E was big. Solved A-D in like 30 minutes, than did not found any clear idea for E or F.

»
4 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

How to solve G — Propagation?

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    Similar to brute force approach. The bottleneck of the brute force approach is when x has a lot of neighbours, updating all the neightbours will take long. So we need to deal with these type of nodes separately.

    Call a node x big if the number of it's neighbours is >= sqrt(2e5). There are very few nodes of this type. So, the idea is to maintain an array of pairs last_propagation for the big nodes. If qi is the last query when a big node b appeared as a query, then last_propagation[b] will be equal to (value of node b at that the time of the query, qi).

    We also always keep the values of these big nodes updated as we process each of the queries sequentially. But we're fine if the values of the small nodes are not always kept updated, since it won't take long to get their latest value using the last_propagation array.

    Then, to process the queries, consider two cases:

    • If x is big, update it's last_propagation and also update it's big neighbours' values.

    • If x is small, get it's latest value and then update all it's neighbours the brute force way.

    Here's my submission using this idea. Let me know if I need to clarify anything above.

»
4 weeks ago, # |
Rev. 2   Vote: I like it +3 Vote: I do not like it

DELETED

»
4 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

how tf solve A? I have 1 WA and can't get what's wrong...

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Maybe you missed "If, however, his rank was Expert, print "expert", ..."

    I did, for one penalty.

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Tell me that you are joking.If not share your submission link

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You printed "expert" for n = 100
    But if n >= 90 then answer is "expert"

  • »
    »
    4 weeks ago, # ^ |
    Rev. 2   Vote: I like it +3 Vote: I do not like it

    try writing expert in lowercase. atcoder is case sensitive

  • »
    »
    4 weeks ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    okey guys, that's really funny, switch on C button is laggy on my keyboard, so I've sent the same wrong code twice))))))))))

»
4 weeks ago, # |
Rev. 3   Vote: I like it +3 Vote: I do not like it

Why does this not work for G? (35x AC, 2x WA)

Split nodes into "light" (degree $$$\lt \sqrt{m}$$$) and "heavy" (degree $$$\geq \sqrt{m}$$$).

For each node we additionally keep track of all adjacent heavy nodes.

For light nodes, we directly push the result of a query to all of its neighbors after a query.

Additionally for all nodes (heavy or light), when we have a query, we will check for any newer values from heavy neighbors.

Remember to perform a heavy neighbour pull at the end for all nodes before printing the answer.

This takes a total of $$$O(m + (n + q) \sqrt m)$$$ since there can be at most $$$\sqrt{m}$$$ heavy nodes in the graph by definition.

Code
  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    That's what I did, and it passed (code).

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Oops, must be an implementation mistake somewhere then. Thanks for the info.

      • »
        »
        »
        »
        4 weeks ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        I am same to you, my code 35*ac ,2*wa ...

      • »
        »
        »
        »
        4 weeks ago, # ^ |
        Rev. 2   Vote: I like it +1 Vote: I do not like it

        The heavy node value might be overwritten later on, thus you need to store the value, too.

        6 5 3
        1 2
        2 3
        3 4
        3 5
        3 6
        3 1 2
        
        
    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thank you, how do you know when to do heavy-light splitting? I'm having trouble identifying this type of problem

»
4 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

lol i hate geometry problems

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I need to go debug my E. My basic idea was to represent the board as a bitmask try all 2^16 bitmasks and check a) Do i cover the required cells? b) Are the cells i have connected? (used DSU) c) Does my polygon have any holes? (used DSU) d) Do i have any self intersections (i.e. corners where one pair of opposite diagonals are included and the other pair where there are not)? However, even on the sample, I'm coming up short on the count, so I'm overkilling boards somewhere.

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You don't have to use DSU for checking holes. You can simply do a bfs starting from an edge square that is empty and check if you can visit all empty squares without leaving any behind

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    What do you mean by "self intersections", I did the following in my AC code:

    A mask is considered good iff:

    • The selected nodes are connected and cover all $$$(i, j)$$$ with $$$a_{i, j} = 1$$$
    • All non-selected node components consist of at least one boundary cell.
    Code
    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks. I must have a bug in my connected checker, as I agree that the self intersections check SHOULD not be necessary. I agree on the "hole-check" piece with you. I guess I'll go use it to discover my bug elsewhere, as it shouldn't be flagging anything.

      • »
        »
        »
        »
        4 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Finally found the bug: i<15 vs. i<16 in for loop termination condition. Painful :(.

      • »
        »
        »
        »
        4 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Attatching GO code here:

        Code
»
4 weeks ago, # |
  Vote: I like it +22 Vote: I do not like it

God save me from tasks like this E. Only you and its author know which moat is considered correct.

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Kudos to the author of E for giving us such a painful experience of implementation hell ! xD!!

»
4 weeks ago, # |
Rev. 3   Vote: I like it -13 Vote: I do not like it

Can someone help me with D) . I used knapsack . why is it wrong ?

My Code
  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    The sum of the number of snacks can exceed 300.

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      i have 300*300 = 90000 states as columns (all possible pairs of (x, y)) that's why i initialised dp as dp(n, vector<long long>((x + 1) *(y + 1)))

      So i have covered all states right ?

      • »
        »
        »
        »
        4 weeks ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        Nope, check this test case:

        2 300 300 250 250 300 100

        Here, we would need a state to represent (550, 350), which is not covered in your code.

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve D, I got the easy $$$O(n^{4})$$$ dp, optimized it like hell for it to pass. What was the $$$O(n^{3})$$$ idea?

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Just have a state that represents >300 for each snack instead of trying to use the actual values. So in total there should be $$$O(n^2)$$$ states which should result in $$$O(n^3)$$$ solution

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    dp[i][j][k] = most taiyaki I can get after taking j of first i boxes and having k takoyaki. i did forward DP, but either need to be careful on order to avoid double counting or push updates to a queue-stack and do them at the end.

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      yaa this is exactly what I also did, need to be careful with optimization.

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

What a joke.solve a and b less than 5min. Then just WA-WA-WA-WA

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Please someone explain why this comparator doesn't work? for C.


bool co(const string s,const string t){ p=sz(s),q=sz(t); i=0; while(i<min(p,q) and mp[s[i]]==mp[t[i]])i++; if(i<min(p,q) and mp[s[i]]<mp[t[i]])return true; return false; }
  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    If one of the strings is a prefix of the other one you return false. But that should be true or false, depending on which string is shorter.

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Sir,can you give me an example plz?

      for input:

      zyxwvutsrqponmlkjihgfedcba
      4
      z
      zy
      zyxv
      zyxwvu
      

      My output:

      z
      zy
      zyxwvu
      zyxv
      
      • »
        »
        »
        »
        4 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        The comparison function needs to return true if the first string is lex smaller than the second. So it returns the wrong value if the first string is a prefix of the second. Because then the first one is lex smaller, but the return value is false. But should be true.

  • »
    »
    4 weeks ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    I used this as a comparator in the sort function, preety similar to yours

    Solution
»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

This is my code for problem D, can somebody give me a counter test for this code? I got 40/50 test passed at atcoder.

Code
»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

This is the first time I didn't solve C. Can someone tell me what is wrong with my implementation? I have written it 12 min after the competition has started and didn't find wrong test till the end of the contest, but I have only 2 AC https://atcoder.jp/contests/abc219/submissions/25932882

»
4 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

problem D — can anyone guide me where my logic getting wrong? top-down implementation

Spoiler
  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Here is my top-down implementation, you can go through it.

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I understood top-down but I am curious to know where my logic is getting wrong.

      • »
        »
        »
        »
        4 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        You should memorize x and y also because the same value of n can give different answers due to different values of x and y.Then your answer will be dp[n][x][y].

»
4 weeks ago, # |
  Vote: I like it +11 Vote: I do not like it

I immediately related to Xenia and tree the moment I read problem G. Kudos to the authors for a really educative problem.

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve Problem G?

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I feel like E is a little easier than D, because I think D is related to DP while E is related to brute-force.

After some observations, you can figure out the solution to E, but for a beginner coder like me, I just couldn't figure out a way to solve D.

Even though I didn't solve E in time, I still feel happy that it's at least solved in the end.

Here's my video during the contest.

»
4 weeks ago, # |
  Vote: I like it +5 Vote: I do not like it

Pretty boring, expected better from an ABC round :/

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Alternate solution to $$$G$$$: We keep a bucket of size $$$\leq \sqrt{M}$$$ that stores {vertex, update_value} pairs that we haven't updated in the graph yet. When the size of this bucket becomes $$$\sqrt{M}$$$, then we iterate through every element in it and update the whole graph correspondingly. When we add a new vertex to the bucket, then search through each element in the bucket and find its updated value based on that. Total time complexity should be $$$O(N + Q\sqrt{M})$$$ or something, but my code is still TLEing on some cases. Is it because of using ordered_set?

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone please explain E a bit more, I have watched many sybmissions but not getting it