maroonrk's blog

By maroonrk, history, 2 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

| Write comment?
»
2 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

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

10 seconds left =.=

»
2 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

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

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

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

How to solve D?

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

  • »
    »
    2 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.

    • »
      »
      »
      22 months 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?

      • »
        »
        »
        »
        22 months 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

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

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

    give link to your solution this link is for question.

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

.

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

Why my C problem always WA on test 17?

  • »
    »
    2 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

    • »
      »
      »
      2 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.

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

        Can you explain how to 'pick' the tree?

        • »
          »
          »
          »
          »
          2 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.

          • »
            »
            »
            »
            »
            »
            2 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

            • »
              »
              »
              »
              »
              »
              »
              2 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.

              • »
                »
                »
                »
                »
                »
                »
                »
                2 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.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  2 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.

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

                  How is DSU a two liner?

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  2 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.

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

      "We" :thinking:

»
2 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 :(

  • »
    »
    2 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?

    • »
      »
      »
      2 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.

»
2 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.

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

Can someone explain D I couldnt understand the editorial.

»
2 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!