### maroonrk's blog

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

 » 6 months 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
 » 6 months ago, # |   0 10 seconds left =.=
 » 6 months ago, # |   -22 @maroonrkWhy there's no partial score in Atcoder?
 » 6 months ago, # |   0 Can someone give a case where this solution to B is wrong??https://atcoder.jp/contests/arc108/submissions/18263650
•  » » 6 months ago, # ^ |   +3 try 9 fofofoxxx your output :- 6 correct output :- 0
•  » » » 6 months ago, # ^ |   0 Thanks!!
 » 6 months ago, # |   +3 How to solve D?
•  » » 6 months ago, # ^ |   +3 Here is the editorial: https://atcoder.jp/contests/arc108/editorial
•  » » 6 months ago, # ^ | ← Rev. 2 →   +6 you can use brute-force and you can find Some inferences
•  » » 6 months 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.
•  » » » 2 months ago, # ^ |   +10 But how do you know that the problem could be solved by a linear recurrence or is it just intuition?
•  » » » » 2 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
 » 6 months ago, # |   0 What is the probable rating for Prob B? Atcoders say it's 400 what is the equivalent to Codeforces?
 » 6 months ago, # |   +9 https://atcoder.jp/contests/arc108/editorial Thanks for quick editorial!
 » 6 months ago, # |   0 Can anyone help me where my code fails for B. Link:- https://atcoder.jp/contests/arc108/tasks/arc108_b
•  » » 6 months ago, # ^ |   +8 give link to your solution this link is for question.
 » 6 months ago, # | ← Rev. 2 →   +5 .
 » 6 months ago, # |   0 Why my C problem always WA on test 17?
•  » » 6 months ago, # ^ |   -6 We had tried many random ways,but failed on the same test
•  » » » 6 months ago, # ^ |   +1 Solution is not Random. You need to pick a tree and color based on parent node. Answer always exists.
•  » » » » 6 months ago, # ^ |   0 I also did that,but failed.I AC except text 17.That is what I puzzled.
•  » » » » 6 months ago, # ^ |   0 Can you explain how to 'pick' the tree?
•  » » » » » 6 months 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.
•  » » » » » » 5 months 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
•  » » » » » » » 5 months ago, # ^ |   0 Yes you are right. Guess I am just used to doing it with DSU.
•  » » » » » » » » 5 months 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.
•  » » » » » » » » » 5 months 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.
•  » » » » » » » » » 5 months ago, # ^ |   0 How is DSU a two liner?
•  » » » » » » » » » 5 months 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.
•  » » » 6 months ago, # ^ |   +28 "We" :thinking:
•  » » » » 6 months ago, # ^ |   +2 Oh man, I did not notice that. Cheating sucks.
•  » » » » » 6 months ago, # ^ |   +1 Oh man, I did not notice that. Cheating sucks.
 » 6 months 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 :(
•  » » 6 months 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?
•  » » » 6 months ago, # ^ |   0 In most cases, we will assume that there is a point in the diameter of the tree.And proof by contradiction.
 » 6 months ago, # |   0 Can someone tell me what test case can give wrong output for my submission for Problem B: https://atcoder.jp/contests/arc108/submissions/18281790
 » 6 months ago, # | ← Rev. 2 →   0 For problem B , Can someone give me a testcase where this submission fails.
•  » » 6 months ago, # ^ |   +8 fkokxk
•  » » » 6 months ago, # ^ |   0 my code gives output 6. That's correct ig :/
•  » » » » 6 months ago, # ^ |   0 7 fffooxa
•  » » 6 months ago, # ^ |   0 fox
•  » » 6 months ago, # ^ |   0 notfox
•  » » » 6 months ago, # ^ |   0 His code gives right output for the above two
 » 6 months ago, # |   +3 Can someone explain D I couldnt understand the editorial.
 » 6 months ago, # |   +24 I think the writer should swap E and F. Any way great contest!
 » 6 months ago, # |   0 can someone please share the solution for C ..i amm getting runtime error in some cases!
 » 6 months ago, # |   0 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?