maroonrk's blog

By maroonrk, history, 2 years ago,

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!

• +120

| Write comment?
 » 2 years ago, # |   +41 Wow, delightful weekend Sat — 5:30PM atCoder ARC 8:05PM Codeforces Round Sun — 5:30PM atCoder ABC 9:30 PM Codechef CookoffIST Timings +5:30 UTC
 » 2 years ago, # |   0 10 seconds left =.=
 » 2 years ago, # |   0 Can someone give a case where this solution to B is wrong??https://atcoder.jp/contests/arc108/submissions/18263650
•  » » 2 years ago, # ^ |   +3 try 9 fofofoxxx your output :- 6 correct output :- 0
 » 2 years ago, # |   +3 How to solve D?
•  » » 2 years ago, # ^ |   +3 Here is the editorial: https://atcoder.jp/contests/arc108/editorial
•  » » 2 years ago, # ^ | ← Rev. 2 →   +6 you can use brute-force and you can find Some inferences
•  » » 2 years ago, # ^ |   +29 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, # ^ |   +10 But how do you know that the problem could be solved by a linear recurrence or is it just intuition?
•  » » » » 22 months ago, # ^ |   0 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, # |   +9 https://atcoder.jp/contests/arc108/editorial Thanks for quick editorial!
 » 2 years ago, # |   0 Can anyone help me where my code fails for B. Link:- https://atcoder.jp/contests/arc108/tasks/arc108_b
•  » » 2 years ago, # ^ |   +8 give link to your solution this link is for question.
 » 2 years ago, # | ← Rev. 2 →   +5 .
 » 2 years ago, # |   0 Why my C problem always WA on test 17?
•  » » 2 years ago, # ^ |   -6 We had tried many random ways,but failed on the same test
•  » » » 2 years ago, # ^ |   +1 Solution is not Random. You need to pick a tree and color based on parent node. Answer always exists.
•  » » » » 2 years ago, # ^ |   0 Can you explain how to 'pick' the tree?
•  » » » » » 2 years ago, # ^ |   0 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, # ^ |   0 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, # ^ |   0 Yes you are right. Guess I am just used to doing it with DSU.
•  » » » » » » » » 2 years ago, # ^ | ← Rev. 2 →   0 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, # ^ |   0 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, # ^ |   0 How is DSU a two liner?
•  » » » » » » » » » 2 years ago, # ^ | ← Rev. 2 →   +1 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, # ^ |   +28 "We" :thinking:
•  » » » » 2 years ago, # ^ |   +2 Oh man, I did not notice that. Cheating sucks.
•  » » » » » 2 years ago, # ^ |   +1 Oh man, I did not notice that. Cheating sucks.
 » 2 years ago, # |   +34 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, # ^ |   +6 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, # ^ |   0 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 →   0 For problem B , Can someone give me a testcase where this submission fails.
•  » » 2 years ago, # ^ |   +8 fkokxk
 » 2 years ago, # |   +3 Can someone explain D I couldnt understand the editorial.
 » 2 years ago, # |   +24 I think the writer should swap E and F. Any way great contest!