maroonrk's blog

AtCoder Regular Contest 108 Announcement
By maroonrk, history, 4 years ago, In English

We will hold AtCoder Regular Contest 108.

The point values will be 300-400-500-600-700-900.

We are looking forward to your participation!

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

Comments Comments (38)
| Write comment?
»
4 years ago, # |
  Vote: I like it +41 Vote: I do not like it

Wow, delightful weekend Sat — 5:30PM atCoder ARC 8:05PM Codeforces Round Sun — 5:30PM atCoder ABC 9:30 PM Codechef Cookoff

IST Timings +5:30 UTC

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

10 seconds left =.=

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone give a case where this solution to B is wrong??

https://atcoder.jp/contests/arc108/submissions/18263650

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

    try 9 fofofoxxx your output :- 6 correct output :- 0

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

How to solve D?

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

    Here is the editorial: https://atcoder.jp/contests/arc108/editorial

    → Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 2   Vote: I like it +6 Vote: I do not like it

    you can use brute-force and you can find Some inferences

    → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +29 Vote: I do not like it

    You can check if some string can be generated, in $$$O(N^3)$$$ time DP. So you can compute the first 10 terms with brute force, and use Berlekamp-Massey to find the $$$N$$$-th term of that sequence.

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

      But how do you know that the problem could be solved by a linear recurrence or is it just intuition?

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

        I was kinda trolling there lol, what I really did in the contest is to write brute-force and observed it was mostly some Fibonacci or powers of two. Then I have to decide what is what for $$$2^4$$$ cases, but I was lazy, and both I found were linear recurrence. So it has to be a linear recurrence :p

        → Reply
»
4 years ago, # |
  Vote: I like it +9 Vote: I do not like it

https://atcoder.jp/contests/arc108/editorial Thanks for quick editorial!

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone help me where my code fails for B. Link:- https://atcoder.jp/contests/arc108/tasks/arc108_b

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    give link to your solution this link is for question.

    → Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it +5 Vote: I do not like it

.

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Why my C problem always WA on test 17?

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it -6 Vote: I do not like it

    We had tried many random ways,but failed on the same test

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

      Solution is not Random. You need to pick a tree and color based on parent node. Answer always exists.

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

        Can you explain how to 'pick' the tree?

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

          You can always solve problem on any tree. There is no criterion for picking. Prerequisite to this problem: Disjoint Set Union Data Structure. If you don't know DSU, you should try Codeforces EDU.

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

            I don't need Disjoint Set Union Data Structure. Just a tree generated by DFS/BFS works.

            https://atcoder.jp/contests/arc108/submissions/18379180

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

              Yes you are right. Guess I am just used to doing it with DSU.

              → Reply
              • »
                »
                »
                »
                »
                »
                »
                »
                4 years ago, # ^ |
                ← Rev. 2   Vote: I like it 0 Vote: I do not like it

                I personally detest anything that uses too advanced stuff when simpler stuff works. It makes solutions more intimidating than they really can be.

                This being said, DSU is a very important data structure. It is worthwhile to learn it.

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

                  I think any solution is ok and learning lots of theoretical topics really opens your mind. If we are considering speed, DSU is a 2-liner, so in short contests it is very good to use.

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

                  How is DSU a two liner?

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

                  int rep(int u){return (u==foo[u]) ? u : foo[u]=rep(foo[u]);}

                  void join(int u, int v){foo[rep(u)] = rep(v);}

                  The basic functionality: getting representative and uniting two components take a line each.

                  → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +28 Vote: I do not like it

      "We" :thinking:

      → Reply
»
4 years ago, # |
  Vote: I like it +34 Vote: I do not like it

If you have erver seen the solution for this problem,you can solve problem F much more easily.

"White and Black" just like "Odd and Even".Though I found this easily,I didn't completed the code in 20 minutes :(

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    If I haven't seen that problem before, what would be the motivation for considering the diameter? More importantly, why might one guess that there is a white vertex whose distance from x is exactly X?

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

      In most cases, we will assume that there is a point in the diameter of the tree.And proof by contradiction.

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

For problem B , Can someone give me a testcase where this submission fails.

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

Can someone explain D I couldnt understand the editorial.

→ Reply
»
4 years ago, # |
  Vote: I like it +24 Vote: I do not like it

I think the writer should swap E and F. Any way great contest!

→ Reply
»
19 months ago, # |
  Vote: I like it -18 Vote: I do not like it

Question C makes me somewhat unhappy.. if there always exists a solution, why do you intentionally mislead the contestant by giving them the option to print No? The solution is quite easy, but I spent most of my time thinking for a counter example that produces the answer No.

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

D：The data range is too small and does not match the time complexity. It's very unusual strange, I kept doubting whether my approach was wrong before I submitted.

→ Reply