atcoder_official's blog

Sky Inc, Programming Contest 2023 (AtCoder Beginner Contest 329) Announcement
By atcoder_official, history, 12 months ago, In English

We will hold Sky Inc, Programming Contest 2023 (AtCoder Beginner Contest 329).

We are looking forward to your participation!

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

»
12 months ago, # |
  Vote: I like it +13 Vote: I do not like it

I <3 AtCoder. When I visit Nihon, I want to visit AtCoder office.

→ Reply
»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Completely clueless on E :(
Saw 3 WAs of Forested, got demoralized further.

→ Reply
»
12 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

today's D realize me, how poor I am in building logic :(

→ Reply
  • »
    »
    12 months ago, # ^ |
      Vote: I like it -27 Vote: I do not like it

    If you know segment tree you can do it easily.

    Code
    → Reply
  • »
    »
    12 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    you could have just solved it using heaps tho

    → Reply
    • »
      »
      »
      12 months ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      Array is enough. One additional variable to keep track of smallest id, You can just keep track of largest one yet on-line. Like the maximum subarray problem, but not exactly.

      → Reply
»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can we solve F using bitsets?

→ Reply
»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Harder version of problem E (with outputting the operations)

Here from Coding Ninjas.

→ Reply
  • »
    »
    12 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Any Hint for F

    → Reply
    • »
      »
      »
      12 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      small to large merging technique submission

      → Reply
      • »
        »
        »
        »
        12 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I got tle for 6 test cases but passed all 38 cases. I Didn't check small and large set. Is this the reason for the tle?

        → Reply
        • »
          »
          »
          »
          »
          12 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Yes.

          That will cost $$$O((n - 1) * (n - 2) / 2)$$$

          assume all the boxes contain exactly $$$1$$$ ball of distinct color than all others.

          Suppose adding left set into the right set in merging. Now if you start merging like below. $$${ \newline \text{1 + 1 (costs 1 iterations)} \newline \text{2 + 1 (costs 2 iterations)} \newline \text{3 + 1 (costs 3 iterations)} \newline \text{....} \ \newline \text{n - 1 + 1 (costs n - 1 iterations)} \ \newline \text{total iterations} = (n - 1) * (n - 2) / 2 }$$$

          → Reply
          • »
            »
            »
            »
            »
            »
            12 months ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Thanks. Can u explain problem E also. I have no clue how to solve it!

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              12 months ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              I couldn't solve problem E during the contest but upsolved it by seeing a beautiful submission by callmepandey.

              So we can solve this problem with dp (ofc), as we can see size of stamp is so small so for each index we can match the character to the character of the stamp.

              For string $$$S$$$ the first character should be matched to the first character of the string $$$T$$$ same for the last character. Now we will check for each index in $$$S$$$ in the range $$$(2, N - 1)$$$ so will try match the current character with the character in $$$T$$$, based on the previous matched indices. There are few case works.

              → Reply
      • »
        »
        »
        »
        12 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        okay

        → Reply
  • »
    »
    12 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    what is the complexity of swapping two sets??

    → Reply
»
12 months ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

E is just a modified DP version of this problem (but it took me too long to recognize that)

Not a bad problem though

→ Reply
  • »
    »
    12 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you share your submission?

    → Reply
  • »
    »
    12 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    please elaborate

    → Reply
    • »
      »
      »
      12 months ago, # ^ |
      ← Rev. 3   Vote: I like it 0 Vote: I do not like it

      We want to build a string $$$S$$$ and in this case our "dictionary" contains $$$\frac{m(m + 1)}{2}$$$ strings (some of the substrings of $$$T$$$ might be the same).

      The only difference between Word Combinations and today's problem is that some prefix of $$$S$$$ should be a prefix of $$$T$$$ and some suffix of $$$S$$$ should be a suffix of $$$T$$$ as well (not just any string from the dictionary). After this the problem is reduced to the cses problem, also we don't even need a trie to solve it, brute-forcing all substrings of $$$T$$$ at each position works as well due to a small $$$M$$$.

      P.S. I just call every check if some target is reachable with given parts problem a knapsack problem, not actually sure if that is accurate

      → Reply
      • »
        »
        »
        »
        12 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Can I see your code? How does your solution handle this?

        Input:
6 3
aaaccc
abc

Output:
No
        → Reply
        • »
          »
          »
          »
          »
          12 months ago, # ^ |
          ← Rev. 3   Vote: I like it 0 Vote: I do not like it

          It's not the prettiest piece of code that I've written, but it works

          Spolier

          Here state 1 means that some suffix of $$$T$$$ has matched fully. If before some suffix hasn't matched fully — I need to start with a fresh prefix

          Not sure if I actually need the extra 0-1 dp state, maybe just checking that a prefix and a suffix have matched is enough

          → Reply
          • »
            »
            »
            »
            »
            »
            12 months ago, # ^ |
              Vote: I like it +1 Vote: I do not like it

            Ah, okay. Now I see why it works, it seems like your explanation before wasn't complete.

            I wouldn't suggest calling this knapsack dp since it isn't that — it's just dp. People will get confused and you'll need to explain further. And also, your solution didn't actually reduce to Word Combinations since you need the check with fully matched suffixes, but I admit that the solutions are still quite similar.

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              12 months ago, # ^ |
                Vote: I like it +10 Vote: I do not like it

              My bad, the explanation was incomplete indeed. The similarity with Word Combinations only occurred to me after the contest has ended and I was frustrated with myself that I didn't see the correlation earlier

              → Reply
»
12 months ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

1st Code: https://atcoder.jp/contests/abc329/submissions/47740404
2nd Code: https://atcoder.jp/contests/abc329/submissions/47740408
Why is the first code giving WA and Second code AC?
The only difference is the order of loop(forward in first and reverse in second).

→ Reply
  • »
    »
    12 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you explain your idea?

    → Reply
»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Passed ABCDF in 19min, but E was always WA x 1 :(

→ Reply
»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

The "swap" in question F is the key if you use map or set, otherwise it will TLE

→ Reply