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 =.=

@maroonrk

Why there's no partial score in Atcoder?

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

Thanks!!

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

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

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.

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

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.

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

For problem B , Can someone give me a testcase where this submission fails.

fkokxk

my code gives output 6. That's correct ig :/

7 fffooxa

fox

notfox

His code gives right output for the above two

Can someone explain D I couldnt understand the editorial.

I think the writer should swap E and F. Any way great contest!

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

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?