maroonrk's blog

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

»
5 months 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

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

10 seconds left =.=

»
5 months ago, # |
  Vote: I like it -22 Vote: I do not like it

@maroonrk

Why there's no partial score in Atcoder?

»
5 months 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

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

How to solve D?

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

  • »
    »
    5 months 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.

    • »
      »
      »
      4 weeks 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?

      • »
        »
        »
        »
        4 weeks 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

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

What is the probable rating for Prob B? Atcoders say it's 400 what is the equivalent to Codeforces?

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

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

    give link to your solution this link is for question.

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

.

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Why my C problem always WA on test 17?

  • »
    »
    5 months ago, # ^ |
      Vote: I like it -6 Vote: I do not like it

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

    • »
      »
      »
      5 months 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.

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

        I also did that,but failed.I AC except text 17.That is what I puzzled.

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

        Can you explain how to 'pick' the tree?

        • »
          »
          »
          »
          »
          5 months 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.

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

            • »
              »
              »
              »
              »
              »
              »
              5 months 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.

              • »
                »
                »
                »
                »
                »
                »
                »
                5 months 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.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  5 months 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.

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

                  How is DSU a two liner?

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  5 months 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.

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

      "We" :thinking:

»
5 months 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 :(

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

    • »
      »
      »
      5 months 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.

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone tell me what test case can give wrong output for my submission for Problem B: https://atcoder.jp/contests/arc108/submissions/18281790

»
5 months 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.

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

Can someone explain D I couldnt understand the editorial.

»
5 months 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!

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

can someone please share the solution for C ..i amm getting runtime error in some cases!

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I wrote this O(1) solution(this made me wonder about the time complexity of sqrt() function) to problem A. Can someone please look at this solution. Is this implementation good enough or should I follow the editorial?