We will hold AtCoder Regular Contest 150.

- Contest URL: https://atcoder.jp/contests/arc150
- Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20221009T2100&p1=248
- Duration: 120 minutes
- Number of Tasks: 6
- Writer: chinerist
- Tester: maspy, satashun
- Rated range: — 2799

The point values will be 300-500-500-700-800-1000.

We are looking forward to your participation!

Hope to solve three problems. And not get too happy just by solving two problems.

I only got 1 :(. Should have got C but not good with graphs/dijkstra's. :( :(

i also got 1 :(

:( :(

Hope you all have a good time in this competition!I just wonder who aaa1a is.

His speed is just unbelievable.

He is dmga44

Couldn't solve any :( I think A was too case-heavy for me

A was really straightforward. Very little case work. (Actually 0).

yeah... my code was a massive lump of spaghetti with probably 7~8 if-else statements, each containing a line of yes or no. :( I guess I get lost into nowhere more often on atcoder than on cf

it happens. :)

I got 3 WAs because I wrote

`s[i - k]`

instead of`s[i - k + 1]`

. But it was worth it, in the end.Is it only me that feels that Atcoder problems are more simple and interesting (even hard ones), as compared to codeforces.

I don't understand why this code for A doesn't work. I believe I have the same idea as the editorial, although I implemented it badly, or maybe did something wrong, but I can't find it even after searching for an hour. Could someone help me out?

Counter example1

4 2

0??0

Thank you so much. I am so dumb for not realizing this.

please explain solution of B

This is the code for starr(https://atcoder.jp/contests/arc150/submissions/35550331), which I think is TLE.

I write this solution during contest too and it passed. Maybe the tests are too weak.

Can problem — A Continuous 1 https://atcoder.jp/contests/arc150/tasks/arc150_a

be solved using DP ??

I tried dp but it couldn't get correct solution .

My idea :

Each '?'has 2 options to be replaced using '0' or '1' .

I formed this recursive logic

idx -> index , leftOne == K — alreadyPresentOne '1'

I'm asking from isPossible() , whether it's possible to have K consecutive 1's And for each True I increment counter , If counter > 1 return False.

But when I turned it into dp[index][leftOne] , I couldn't do I realise it's because let say I've 00?1???10? if at one instance like 001111010? dp[7][0] == No but then for 0001111100 dp[7][0] == Yes

Please verify if it's dp solvable or not ??

Can someone please explain how to solve problem B. How the range of X is fixed : X=max(0, ⌊(B−1)/k⌋+1−A) ? How to obtain this ⌊(B−1)/k⌋+1−A ? Is it through calculus ?

these lower bounds are obtained by applying conditions of x>=0 and y>=0 in obtained equations

I think my solution to problem C is a little weird, and I am not sure if it is correct (although get AC).

I use normal bfs, starting from node-1, but with k stages, where k is just the input in the statement. For each stage, we keep visiting all the unvisited nodes until we meet nodes-x, where a[x]=b[stage]. During the process, if node-n has been visited, then the answer is no, otherwise is yes.

By the way, problem B uses the sqrt-technique, which is somehow similar to problem B in ARC139. I feel very lucky that I realize this quickly.

That is essentially the same as editorial, just another way how to implement 0/1 bfs.The values in array $$$d$$$ are euqivalent to the amount of iterations before you discovered some value in your case.

Thank you for your kind reply. But after reading tutorial, I find that solution is more reasonable and formed in a systematic way, while mine seems a little bit unclear.

How I "solved" B:

First, notice that ans is at most min(b-a,a) so you can bruteforce for all x<=1 mil and this handles all cases with a<=1mil.

For the remaining cases(a>1mil): Suppose b+y = z(a+x), bruteforce for all z <= b/a and y<=b/a. Both loops are <= 1000 runs

I think this is WA solution but weak tests. If it happens to be correct, can anyone show proof?

Why would it be wa? also if you know z you don't need to bruteforce y. This is my solution

I thought there might be a case with y>1000, thats why. I guess the idea is AC, when you get y with math.

Will you please explain more what you are doing in

remaining cases(a>1mil)part? I am unable to understand only by watching your code.I've made it easier to understand: Here

Why is BFS wrong for problem C https://atcoder.jp/contests/arc150/submissions/35553054

maybe 01bfs

Let me know if you got the reason why using BFS is not working.Thanks in advance

because if n is 9, and a road is 1 -> 4 -> 8 -> 9, and another is 1 -> 3 -> 6 -> 7 -> 5 -> 8 -> 9, and 4 8 is b[2], b[3],3 6 7 5 in not in b[], then BFS with get dp[9] = 4,but the answer should be dp[9] = 2

4 8 is b[2], b[3],3 6 7 5 in not in b[]can you elaborate this part

In editorial of problem D — tester's solution:

"Not only bad vertices but also good vertices can be chosen.". Why doesn't that change the result?The outcome of the random variable $$$X_v$$$ depends on status of the parents of $$$v$$$. That is, it just needs to 'keep track' of the parents to know when $$$v$$$ has become good and it needs to stop performing operations. This intuition explains why we don't care about the operations which pick something apart from $$$v$$$ and its parents. Those operations neither change the state of $$$v$$$'s parents, nor do they directly change the value of the random variable (which would only be affected when we pick precisely $$$v$$$).

A similar argument holds for not caring about whether we pick good or bad vertices. Even if we pick a good vertex, it was already coloured black from earlier. So the status of none of the parents change. We know we didn't pick $$$v$$$ itself, since the process would have already stopped if $$$v$$$ was good beforehand. This operation doesn't affect the value of the random variable as well. And so we're free to consider them as valid moves.

I was lost while reading editorial of B. Someone save me please.

We want $$$B+Y$$$ to be a multiple of $$$A+X$$$, i.e., $$$B+Y = k(A+X)$$$ for some positive integer $$$k$$$.

If someone told you what $$$k$$$ you need to use, then part 1 of the editorial tells you how to find $$$X$$$ and $$$Y$$$ such that $$$X+Y$$$ is smallest. We have, $$$Y = kX+kA-B$$$ and $$$X+Y = (k+1)X+kA-B$$$. To minimize $$$X+Y$$$ is then same is to minimize $$$X$$$, because $$$k$$$, $$$A$$$, and $$$B$$$ are fixed. We choose smallest $$$X$$$ such that $$$Y \ge 0$$$ (recall $$$Y = kX+kA-B$$$). This value is $$$\max(0, \lfloor\frac{B-1}{k}\rfloor + 1 -A)$$$ (convince yourself of this).

Part 2 then tells you that for $$$k \le \sqrt{B})$$$ you can just compute this value, and the number of different values of $$$\lfloor\frac{B-1}{k}$$$ for $$$k > \sqrt{B}$$$ is at most $$$\sqrt{B}$$$. For example, if $$$B = 101$$$, then $$$\lfloor\frac{B-1}{k}\rfloor$$$ can take values $$$9, 8, 7, 6, 5, 4, 3, 2, 1$$$ if $$$k\ge 11$$$. So you compute minimizing $$$X$$$ using $$$k = 1, 2, \ldots, \sqrt{B}$$$ first then compute minimizing $$$X$$$ using $$$\lfloor\frac{B-1}{k}\rfloor = 1, 2, \ldots, \sqrt{B}$$$. (Maybe try 2 or 3 more values if I am missing some constants.)

Thanks for your explanation!

Y = kX + kA -B

Having Y >= 0, I get X >= floor((B-kA)/k)

How do I reach X >= floor((B-1)/k) + 1 -A from here?

This is just a hacky shortcut. You want $$$kX + kA - B \ge 0$$$, i.e., $$$X \ge \frac{B}{k} - A$$$. There are two cases.

Case 1. $$$\frac{B}{k}$$$ is an integer, so we can set $$$X = \frac{B}{k} - A$$$. You can see that, in this case, $$$\frac{B}{k} = \lfloor\frac{B-1}{k}\rfloor + 1$$$ (because $$$\lfloor\frac{B-1}{k}\rfloor = \frac{B}{k} - 1$$$).

Case 2. $$$\frac{B}{k}$$$ is not an integer, so the next higher integer is $$$\lfloor\frac{B-1}{k}\rfloor + 1$$$.

Thank you! This shall help me in the future as well

You're welcome!

I also couldn't understand the editorial of B. Then I looked at more editorials and found a better explanation from the official video editorial:

For

B + Y = k(A+X), there are two approaches to findX + Y:fromX0toA-1, we can get a value ofX + Yfor each case and keep the minimum.fromk1toB/A, we can get a value ofX + Yfor each case and keep the minimum.Note the range of

andX, when A is extremely small or extremely large, either Approach 1 or Approach 2 can be very slow. Therefore, pick a value ofkto determine to only use the faster of the 2 approaches.sqrt(B)Much cleaner! Just to add a tiny elaboration: if $$$A \le \sqrt{B}$$$, then Approach 1 uses $$$\le\sqrt{B}$$$ iterations, and when $$$A > \sqrt{B}$$$, Approach 2 uses at most $$$B/A \le\sqrt{B}$$$ iterations.

Edit: Actually, reasoning for why Approach 2 only checks until $$$B/A$$$ is not clear to me.

IF you go over the range, you will notice the Xs and/or the Ys computed by the formula can become negative. Negative Xs or Ys are not allowed.

Oh, so there is more argument needed. I had previously misunderstood it.

In problem B, he has not used the $$$\sqrt{N}$$$ algorithm but something else. Can someone explain his code please

In

`int r = (b + (a + x) - 1) / (a + x);`

and`int y = r * (a + x) - b;`

, he is just computing smallest`y`

for a given`x`

. If`r==1`

, then basically`a+x`

has become greater than or equal to`b`

, i.e., the resulting`r`

is going to be the same for subsequent`x`

s, i.e., the subsequent`y`

s are going to get only larger, so we break. Sorry to be incomplete and I am not 100% sure, but I suspect in`x = (b + (r - 2)) / (r - 1) - a;`

, he is trying to get the next`x`

value which willnotgive the same`r`

value as for this iteration. My guess is that this way, you would try at most $$$O(\sqrt{A+B})$$$ values for`x`

by a similar calculation as in the editorial.My approach to C is different from that of the editorial (and I don't know whether it is correct):

I computed some data by hand, and found out that for all the data given in the problem, I saw this feature:

SpoilerIf we disconnect all the points that say, $$$a_x=b_i$$$ (we want to find that $$$x$$$), from the graph.

Then, if there still exists a path from 1 to N, then the answer is

`No`

.Because first if there exists a path not containing either of the $$$x$$$, it is no, and second, if there is another order, it will be connected also.

Maybe we can use DSU to compute the answer? Or maybe this "feature" is wrong? Or is this right?

I have a small confusion regarding simple path

Simple path doesn't mean it is the shortest path right , it means path which doesnot contains two or more same vertices

Then in the sample test case 2 of problem C why we are not considering path (1,2,3,4,5) ?

In path every consecutive vertex is connected directly by an edge. 2 and 3 do not share an edge

2 and 3 have an edge right ?

This is the sample test case 2 :

5 5 3 1 2 2 3 3 4 4 5 2 5 1 2 3 5 2 1 3 2

3rd line of the test case represents there is an edge between 2 and 3

If we consider path (1,2,3,4,5) then yes the condition will be satisfied but the problem statement says that condition has to be satisfied for all simple paths. It is not satisfied for (1,2,5)

Since 2 out of 26 test case has been showing WA. Which edge cases I'm missing, please help me to find out?

Can anyone helped explain this code of Problem B? https://atcoder.jp/contests/arc150/submissions/35534665