We will hold AtCoder Regular Contest 108.
- Contest URL: https://atcoder.jp/contests/arc108
- Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20201121T2100&p1=248
- Duration: 100 minutes
- Number of Tasks: 6
- Writer: camypaper
- Tester: satashun tempura0224
- Rated range: — 2799
The point values will be 300-400-500-600-700-900.
We are looking forward to your participation!
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
10 seconds left =.=
Can someone give a case where this solution to B is wrong??
https://atcoder.jp/contests/arc108/submissions/18263650
try 9 fofofoxxx your output :- 6 correct output :- 0
How to solve D?
Here is the editorial: https://atcoder.jp/contests/arc108/editorial
you can use brute-force and you can find Some inferences
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.
But how do you know that the problem could be solved by a linear recurrence or is it just intuition?
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
https://atcoder.jp/contests/arc108/editorial Thanks for quick editorial!
Can anyone help me where my code fails for B. Link:- https://atcoder.jp/contests/arc108/tasks/arc108_b
give link to your solution this link is for question.
.
Why my C problem always WA on test 17?
We had tried many random ways,but failed on the same test
Solution is not Random. You need to pick a tree and color based on parent node. Answer always exists.
Can you explain how to 'pick' the tree?
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.
I don't need Disjoint Set Union Data Structure. Just a tree generated by DFS/BFS works.
https://atcoder.jp/contests/arc108/submissions/18379180
Yes you are right. Guess I am just used to doing it with DSU.
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.
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.
How is DSU a two liner?
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.
"We" :thinking:
Oh man, I did not notice that. Cheating sucks.
Oh man, I did not notice that. Cheating sucks.
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 :(
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?
In most cases, we will assume that there is a point in the diameter of the tree.And proof by contradiction.
For problem B , Can someone give me a testcase where this submission fails.
fkokxk
Can someone explain D I couldnt understand the editorial.
I think the writer should swap E and F. Any way great contest!
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.
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.