chokudai's blog

By chokudai, history, 3 years 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

| Write comment?
»
3 years ago, # |
  Vote: I like it +73 Vote: I do not like it

One of the best educational contests. Thanks atcoder!

»
3 years 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.

»
3 years 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?

»
3 years 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

»
3 years ago, # |
  Vote: I like it +20 Vote: I do not like it

HardCoder

»
3 years 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 ?

  • »
    »
    3 years 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

    • »
      »
      »
      3 years 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

  • »
    »
    3 years 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
    • »
      »
      »
      3 years 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)

      • »
        »
        »
        »
        3 years 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.

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

    basically knapsack like dp

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

    I solved Problem D using dp.

»
3 years 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) !!!!!

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

Can someone share a neat implemeantaion of pE?

»
3 years 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.

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

How to solve G — Propagation?

  • »
    »
    3 years 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.

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

DELETED

»
3 years 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...

  • »
    »
    3 years 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.

  • »
    »
    3 years 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"

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

    try writing expert in lowercase. atcoder is case sensitive

  • »
    »
    3 years 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))))))))))

»
3 years 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
»
3 years ago, # |
  Vote: I like it +1 Vote: I do not like it

lol i hate geometry problems

»
3 years 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.

  • »
    »
    3 years 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

  • »
    »
    3 years 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
    • »
      »
      »
      3 years 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.

      • »
        »
        »
        »
        3 years 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 :(.

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

        Attatching GO code here:

        Code
»
3 years 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.

  • »
    »
    3 years 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!!

»
3 years 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
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    The sum of the number of snacks can exceed 300.

    • »
      »
      »
      3 years 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 ?

      • »
        »
        »
        »
        3 years 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.

»
3 years 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?

  • »
    »
    3 years 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

  • »
    »
    3 years 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.

    • »
      »
      »
      3 years 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.

»
3 years 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; }
  • »
    »
    3 years 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.

    • »
      »
      »
      3 years 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
      
      • »
        »
        »
        »
        3 years 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.

»
3 years 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
»
3 years 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
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      3 years 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.

      • »
        »
        »
        »
        3 years 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].

»
3 years 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.

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve Problem G?

»
3 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Pretty boring, expected better from an ABC round :/

»
3 years 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?