We will hold AtCoder Beginner Contest 187.

- Contest URL: https://atcoder.jp/contests/abc187
- Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20210102T2100&p1=248
- Duration: 100 minutes
- Number of Tasks: 6
- Writer: kort0n, Kmcode, satashun, tatyam, tempura0224, tozangezan
- Rated range: ~ 1999

The point values will be 100-200-300-400-500-600.

We are looking forward to your participation!

For anyone interested, I'll be doing a post-contest stream on Twitch.

Great!

Waiting for last one.

It's on YouTube: https://youtu.be/CyAS9PbR-l8

I recently found that for strings, using set count function is faster( and more accurate) than vector binary_search. Like in problem C. Is it true?

I think if anything I'd expect the vector to be faster, the only thing is you need to make sure it's sorted.

Bump. Contest Starting!

How to solve F? Is the answer minimum number of clique in graph?

How to pass all cases in D???

For D with every speech total votes gained will

`2 * a + b`

. So just sort according to that value and keep taking maximum. Also take care of overflow. I got one penalty because of that.Code

Dynamic Programming !!

If you mean dp on subset I won't work since 3^18 is too big unless I am missing something

O(3^n) is OK, because the constant is very low, my solution passed in 0.5s/6s

While up-solving the problem , i also wrote same $$$O(3^n)$$$ solution . In my local computer whenever i run the case 18 0 it takes more than 2 seconds whereas on online judges it's only taking around 0.5s. What could be the reason for that ?

I solved it by bitmask DP with O(3^n). But I'm not sure whether it's the best solution.

My approach is calculating the size of the biggest sub-graph which every two vertice in it is not connected. However,I keep getting WA for one test case(that is really disappointing)

The key idea is that if any two nodes are not connected by an edge in the given graph then they cannot be in the same connected component as they will not form a clique. Now the problem is equivalent to finding chromatic number of the compliment graph which can be found here and can be done in O(n * 2^n)

I use Recursion and Backtracking, and add a optimization that stop recurse when current result is worse than previous answer.

For more details: ac code — 7ms.

How to solve D. I tried to sort on the basis of a[i]+b[i] value but kept getting WA.

you need to sort by 2*a[i]+b[i]

why ?

Go check out AnandOza stream.

Thanks!

First assume that Takahashi is not giving any speech . then Aoki will get all of his own voters say "ans" . Now sort array of 2*A+B and subtract from ans until ans>=0

since place where Takahashi will give a speech , Aoki will lose his votes as well as Takahashi will gain his and Aoki votes. Number of times subtracted will be the answer .solution

Let x be the answer i.e x is the minimum number of towns in which Takahashi needs to deliver a speech..Let (a[1],b[1]),(a[2],b[2]) ...(a[x],b[x]) be the vote pairs in these x towns.Also,Let A be the total number of votes Aoki would have received if Takahashi would not have given speech in any of the towns..Now under the given secnario,number of votes received by Takahashi is summation over j from 1 to x P = (a[j] + b[j])..and number of votes received by Aoki is Q = A — ((summation over j from 1 to x)a[j])..Now P has to be > Q.. Just transposing the equation we get ((summation over j from 1 to x)(2*a[j] + b[j])) > A...So if we sort the pairs according to decreasing order of (2 * a + b) the prefix of minimum length would simply be the answer.

Could you please explain?

because when we choose a town Aoki loses a[i] votes and we gain a[i]+b[i] votes. So the net change in 2*a[i]+b[i].

With every speech

lose`a`

votesgain`a + b`

votes.So total votes gained =

`a + b - (-a)`

=`2 * a + b`

Thanks a lot.

What is proof of correctness for this greedy approach ?

Costof speech for each town is the same. As the cost is the same, choose greedily by gain as mentioned in previous comments.Thank you so much for helping.

But why ?Why a[i]+b[i] is not working and why multiply by 2 working ?

In this case:

The correct answer is 1.(By giving speech on the 2nd city)

But yours will output 2

1<=Ai,Bi<=1e9

I think if the last '0' is changed to one, it is still is a good testcase which serves the purpose of highlighting that 2*a[i]+b[i] is correct rather than a[i]+b[i]

How are you able to find such corner test cases ? I was scratching my head for 30 minutes straight but couldn't figure out why it was getting wrong verdict. But your test case helped me understand where my code was failing. Thanks a lot for that :)

With a speech the one get a[i]+b[i] votes. Without a speech the other gets a[i] vots. So, the difference of both cases is 2*a[i]+b[i], so giving a speech at city i make exactly that difference.

Of course we need to give speech in cities in order of these difference, biggest first.

Proof: let suma = $$$a_1 + ... + a_n$$$, sumb = $$$b_1 + ... + b_n$$$. Let's imagine we will make a speech, which affect $$$A$$$, and $$$B$$$ people.

So, $$$A + B$$$ people will be vote for us, and $$$suma - A$$$ against us

We need $$$A + B$$$ > $$$suma - A$$$

$$$2A + B > suma$$$

So, we need sort by 2*a[i]+b[i]

link to your solution ?

https://atcoder.jp/contests/abc187/submissions/19129882

you need to sort it based on 2*a[i] + b[i]

sort according to 2*a[i] + b[i]

Sort according to maximum gain of votes for Takahashi. The gain while taking a city is $$$2a[i] + b[i]$$$. Here $$$a[i]+b[i]$$$ is vote added to Takahashi and $$$a[i]$$$ is vote taken from Aoki.

You need to sort on the net increase in your votes, now realize that a decrease in votes for aoki is also indirectly an increase in votes for Takahashi. Thus the net increase in takahashi's votes is the total votes for that city + the extra decrease in votes for aoki, i.e. $$$2 \cdot a[i] + b[i]$$$. Now just sort on those and you're golden.

`Try this input:`

If you sort on the basis of (a+b) then (1,8) will come before (7,1).You will gain total (1+8)-(-1)=10 votes.

If you sort on the basis of (2*a+b) then (7,1) come before (1,8). And you gain total (7+1)-(-7)=15 votes.

Please anyone point out the mistake in my code or logic? Task D https://atcoder.jp/contests/abc187/submissions/19154830

Maybe you should sort in basis of 2 * vp[i].ff + vp[i].ss.

I guess sorting is wrong which leads to WA in some test cases, try it by sorting with 2*a[i] + b[i]

`try this input:`

Can anyone tell me how to approach the problem E? https://atcoder.jp/contests/abc187/tasks/abc187_e

The idea is that of segment tree instead of adding all the numbers just add to b[i] or a[i](In the second cases you should add the number to the root and subtract from a[i] b[i]) Now run a lazy propogation like operation(adding the value on the node to its childs) using dfs.

Segment tree is overkilled here. Just using simple dfs as the comment below! My ugly code: https://ideone.com/PAEUDp

Yes, we basically Find the case according to the distance of a and b from the root, and since a and b are connected by an edge we see if a is near root then we add to root subtract from b otherwise we simply add to a. And then we do DFS from the considered root in my case 1 to find all the final answers.

CodeImagine a rooted tree with the root being any vertex (say, vertex 1). Now, consider a query $$$q_{i}$$$ such that $$$t_{i}$$$ = 1 and $$$e_{i}$$$ = ($$$u$$$, $$$v$$$). If $$$u$$$ is the parent of $$$v$$$ in the rooted tree, it means we can visit every vertex apart from vertices lying in the subtree of $$$v$$$. Otherwise, we can visit only the vertices lying the subtree of $$$u$$$. If $$$t_{i}$$$ = 2, the situation is the same with the vertices swapped. Rest is the implementation part of how to compute the overall values in $$$O(n+m)$$$ which can be done using a simple DFS.

How to solve Problem E ?

Thanks in advance!

for processing queries assume 1 is root of tree if (u,v) is a edge and u need to update u. There are two cases if u is parent of v (in this case update root of tree with x and v with -x) and if v is parent of u (simply update u with x).

I did the same thing, except when v is the parent of u, I updated the node below v that is the parent of u. My logic being:

say the tree is like:

v -> p -> q ->u -> r (rotate by 90deg)

now if we need to update ci for all nodes reachable from u but not doing through v, the nodes are: p, q, u, and r. (that's what I did, and got WA) but if we just update u, only u and r are updated in end(that's what u did and got AC, I changed my code to this and got AC too) but I don't understand why am I wrong?

Can you please point out the mistake here

Edit: actually got it, it's because u and v are connected by 1 edge.

first of all your test case is invalid as u and v will always be connected by an edge. Read the Question. I also thought like that and kept getting TLE until i figured this out.

I made a euler tour array and just updated the suitable ranges with segment tree

Select any node with 1 edge as root. Then use bfs and store level wrt root for every node. Now, idea is to use to prefix sums. For every query, you have to add cost of one side of a vertex. Now, parse the input as per the type and find which node's value gets incremented. Lets call this node "node1". Compare the two nodes now and if node1 is at a higher level, add cost to root and subtract it from node2, otherwise just add cost to node1. Now run dfs and for every node, cost[node] = cost[node] + cost[parent]. I wasnt able to implement it completely during contest tho.

Submission

is there any greedy solution for D?

Yes

HintStore the input in vector of pairs and sort using 2*a+b

When you pick a town, you get all the A votes from it, and all the B votes from it, additionally you deprive the other from all of A votes he would otherwise get. So the value of picking a town is A+B+A = 2*A + B, sort the towns by it and keep picking until you have enough votes.

Yes, Let us assume initially she didn't go to any town. So Aoki score is sum of all A[i], let us denote it by s and Takahashi score is 0. So initial difference is s. Now consider if she chooses any city i to make a speech, what will be the new difference ?

SpoilerAoki score = s-a[i] , Takahashi score is a[i]+b[i] , so the difference now is reduced by 2*a[i]+b[i]

So, we want to choose cities in such a way, that we reduce this difference by selecting minimum cities. So, let's make a vector v, such that v[i] = 2*a[i] + b[i] , and sort it. Start by selecting the largest, second largest and so on, until this difference reduces to less than 0.

Pseudo Code

How to solve D problem? I sort the pairs according to this comparator always choose the maximum pair sum and if two pair sum is equal then choose the highest first element among these pair.

Then greedily choose the elements if it's strictly greater or not.What am I missing? my sub

can also do like this

how to solve F?

how to solve Problem F? T_T

Is problem E related to segment tree or DSU?

No you can use dfs,bfs with difference array and you can root the tree.

I used Lazy Segment Tree. My submission: E — Through Path

Can someone give a test case for problem D for which there is possibility of RTE. I am using long (IN JAVA) everywhere so overflow is not an issue i guess .

Any hints on D? Tried solving by taking maximum (a[i]+b[i]) but it gave WA.

sort according to $$$2*a[i]+b[i]$$$ instead $$$a[i]+b[i]$$$

see above comments

You should take maximum(2*a[i]+b[i])

It is so painful to solve the problem (E) but fail to get AC because it is python and you get three TLE

This is most likely not a python issue.

I'm pretty sure it is python issue

Solution is just a couple of dfss, O(n), there is not much to to optimize

Why not switch to cpp for dfs problems?

I hoped for the best

Hope is a dangerous thing, meh

Had the constraints were smaller or there was only one dfs it would've worked. That's what I didn't think about

Though it is possible to pass in python, a good reason to examine the bottlenecks

Truth be told though, I wouldn't have debugged it in time in cpp since I wasted too much time thinking about LCA missing the fact that both vertices always belong to the same edge

I once tried to write DFS in python and also got TLE. Then I checked others guys solutions and found that they launched dfs in particular thread and it worked. I used this code as an example: code

I know this trick and use it. Though it has nothing to do with TLE, it is needed to bypass python's stack limitations

Hmm, got it)

Funny thing btw. It TLEd in pypy, but passed in cpython. Too bad I didn't think about it during the contest

I was able to solve $$$a,b,d,e$$$ but couldn't figure out what the statement of $$$c$$$ mean. Statement could be better. By the way what does problem $$$C$$$ meant?

They asked if the query string is in the list, and also the query string with a pre "!" before it.

Me too;

Given N strings:S1,S2...SN.Among them,there are two types of strings:

1."!***..."

2."***..."

where * stands for a lowercase latin letter.

You are asked to find a string consisting of only lowercase latin letters that both the string itself,and the string obtained by adding a "!" before it(we can get "!abcde" from "abcde") are in the strings S1...SN.

The first thing I want to say is the problems are excellent! Some ABCs' problems are really easy and don't need to think. (I mean, A~D) But this one is different, I really like D.

By the way, how to solve F? I think about it for a long time but just can't fix it.

bitmask dp

How to solve E? Thanks in advance!

For solving E you can first think of a simpler case. If your have an array

`A`

and you are given`Q`

queries where in you have to add`x`

value to range`[L, R]`

then you can build another array`P`

and can perform operations like P[L] += x and P[R+1] -= x. Then you can do prefix sum on this array which will have the same effect as required by the question.Now you can think of same with this tree. For query of type 1 simply add

`x`

to root and subtract`x`

from`c[b]`

. For query of type 2 add`x`

to`c[b]`

. Then perform a dfs and simply push this accumulated value of`c`

in all the children and do it like prefix sum.Root the tree in the node $$$1$$$. For each query of type $$$1$$$; I denote $$$x$$$ like $$$a_{e_i}$$$ and $$$y$$$ like $$$b_{e_i}$$$. Then there are two possibles cases:

For solve the first case, note that I can reach to all vertices except the vertices of the $$$y$$$'s subtree

In the second case, I only can reach to the vertices of the $$$x$$$'s subtree.

For each query of type $$$2$$$ you can use the same approach.

Now, you can use Euler Tour Technique and solve the problem easily. You can learn it in the next link: USACO Guide :)

My submission for this problem: Submission #19155947. I hope that this is helpful!

Hi, guys. I defined comparator on problem D, but the first code keep giving me runtime error, I use $$$\leq$$$ in the

`return`

line.Then I try to use $$$<$$$(the code below), and then it magically passed. (All other parts of code are the same).

Anyone has a clue why $$$\leq$$$ get a runtime error, but $$$<$$$ gives AC?

The full code of the runtime error one (https://atcoder.jp/contests/abc187/submissions/19147735)

The full code of the AC one(https://atcoder.jp/contests/abc187/submissions/19149284)

Read this: Why must std::sort compare function return false when arguments are equal?

bcoz in the first code,there exists a possibility that cmp(a,b) cmp(b,c) cmp(c,a) are all true,so the function cannot sort properly.

Never heard this rule before XD, learn something new today. Thank you both for giving me a hand!!!

For D, I sorted in decreasing order on basis of {aoki[i]+takahashi[i] , aoki[i]} and then took prefix sum for first and suffix sum for second. So, when i get prefix[i] > suffix[i+1], ans is (i+1). The logic seems to be correct but I got WA. Can someone point out the fault in this method? Thank you. My Submission

try this:

Output is 2. It should be 1. I'll check. Thank you.

my code gives 1 for the above test case. I used something like Stark_3000 { I took suffix sum for first & prefix sum for second, and when v.[i].first > v[i-1].second, ans is counter j }, still getting WA for 'large.txt' test cases. thank you.

Approach for

Problem DThe most difficult part of the algorithm is the fluctuating value of

Aoki'svotes. So, we'll try to convert it into a problem where the votes of one voter is fixed.Aoki's initial votes is $$$\sum b_i$$$

Now, say, we add just the $$$i-th$$$ town to our list. This would decrease the votes of Aoki by $$$b_i$$$ and increase the votes for Takahashi by $$$a_i + b_i$$$. However, since in an election, if you grant equal votes to both the candidates, the situation does not change. So, we'll provide $$$b_i$$$ votes to both Aoki and Takahashi in order to balance things out.

So, the net gain for Aoki is 0, while net gain for Takahashi is $$$a_i + b_i + b_i$$$. Hence, each town contributes a factor of $$$2b[i] + a[i]$$$ to the winner while keeping the points of the loser fixed.

Hence, just create an array consisting of $$$2b[i] + a[i]$$$, sort it, and greedily take largest values until you exceed the total of $$$\sum b_i$$$ (the initial and final points of the loser).

How to solve F in less than $$$3^{n}$$$?

We're trying to find the minimum clique cover of a graph. It's easy to see that an equivalent problem is finding the chromatic number of the complement of a graph. A bitmask DP / inclusion-exclusion algorithm exists for finding the chromatic number of a general graph in $$$O(n\cdot 2^n)$$$. More details can be found here

Can you please share the link of your ac submission?

Implementation

Thanks a lot!!

I just use recursion and backtracking, and a little optimization.

Assume we are processing the $$$i$$$-th vertex, and the first $$$i-1$$$ vertexs form a set of cliques. Note the set as $$$Cliques$$$.

so far, the solution is not good enough to get an AC.

Then I find that if $$$ ans \le |Cliques| $$$ ，it just no need to recurse any more, just cut it.

After adding this optimization, the solution is good enough to get an AC and my submission only execs about 7ms.

Submission #19164964

I finally did the same. But I have doubt that it is weak test data that makes it so fast.

What is the runtime complexity of our solution?

_Backl1ght or spookywooky did you found the complexity of the solution ?

Isn't the time complexity greater than $$$O(n!)$$$ in worst case ?

Suppose we can divide vertices (1,2,3,4,5,6) only like (1,2),(3,4,5),(6) i.e contiguously and not like (1,5),(2,3,4,5,6) then complexity would have been $$$O(2^n*n)$$$ by using binomial theorem. But that's not necessarily true because vertices can form group like (1,5),(2,3,4,5,6) and thus we need to consider all arrangements of $$$n$$$ vertices before partitioning and there are $$$O(n!)$$$ arrangements and thus in worst case it can be around $$$O(n!*2^n*n)$$$.

Not sure , but i think if such fast solution existed then they would mentioned in editorial because above solution is just brute force and writers must have thought about it.

I think actually it is better than brute force.

See two "extremes". If there are a lot of edges, then we most likely can form big components, leading quickly to good solutions.

On the other hand, if we got not much edges there are not much components we can create, so the size of the brute-force tree is fairly small.

Then, consider a single vertex. If it is completly disconnected (no edge) then the complexity is the same as that vertex would not exist. Else that vertex can be put into a component with at least one other vertex. This makes the complexity based on N in fact beeing based on n/2. Which makes a huge difference.

In spite of not beeing able to tell how the complexity is calculated I am fairly sure that in this case it is better than the O(3^n) of the bitmask solution.

I think that answer is made up by a lot of cliques with size 2 will be a bad case. So I write a generator to generate graph contains no clique of size 3 as subgraph. And it turn out to be a bad case I think.

On my PC, it still execs only a few ms when $$$n \le 18$$$ , and it will cost seconds when $$$n \le 25$$$, and for $$$n \ge 26$$$ I have no patience to wait it to complete running.

I still can not figure out what the time complexity exactly is, but I guess it will be something between $$$O(2^n)$$$ and $$$O(n!)$$$.

As I implemented it, I do basically a dfs construction all combinations of cliques possible.

But, I do create biggest possible cliques first, and I stop dfs if ans cannot get better.

So, the solution where biggest cliques are created is near to the optimal solution. There can be better ones.

Consider a graph where cliques possible of size [3,3,1,1,1,1], there could be a better solution with cliques of size [2,2,2,2,2]

In this case we fairly quick find 6 as ans, and then traverse the searchtree not deeper than level 6.

On problem D

I want to ask

Why is my greedy strategy wrong

Can anyone provide a set of hack samples

Don't sort with a[i].x+a[i].y. Change it to a[i].s = 2*a[i].x+a[i].y.

testcase - 1 4 3 1 2 0 answer is only 3,1

Thanks your test case

https://atcoder.jp/contests/abc187/submissions/19163293

Plz some java enthusiast find error in this submission for Problem D in java..i used long also , just getting RTE on 7 tests and all other AC .

The comparator you used to sort the array of pair causes the RTE. I correct your comparator and got AC. Submission: https://atcoder.jp/contests/abc187/submissions/19186929

What is the approach for solving C, I got 3 TC WA(so obviously WA), is there any corner case I'm missing, link to the submission: Link

Check this case — 2 !a a.

The problem is that you assume that strings without ! will appear first.

Failed test case. 2 !a a

I tried to solve problem D via priority queue, but got WA on 9 test cases, however, my normal vector greedy solution got AC.

Using priority-queue(WA): https://atcoder.jp/contests/abc187/submissions/19163897

AC: https://atcoder.jp/contests/abc187/submissions/19170201

Can anyone give me a tough side case for which it might fail?

Video Editorial, and also screencast.

You can also refer to the Source code and simple explanation.

My submission got runtime error on 3 tests for Problem D. Can someone help me with the reason for the Runtime error?

You have the same problem as me. you can look the previous post.

Got it. Thanks

Your comparator must return false when values are equal. I changed that it got AC.

Thank you. Didn't know such trivial mistakes can give a RE.

apply DP in D and got 12 TLE

DP doesn't always gives the fastest solution. Sometimes you need to be greedy.

I didn't understand why Sample Output 2 in Problem F is 1. I think it supposed to be 0, because Sample Input 2 is already complete.

I got it, the question is answer the minimum possible number of components, I misunderstood with the count of edges need to be removed...

My solutions + explanations can be found here :)

nice

Is there anyone who used segment tree in problem E??

I think that intended solution was flattening tree with segment tree

upd: code

upd 2: I think that solution by ScarletS is much better and easier, though it uses the similar idea, but segment tree solution may be helpful when we need to answer queries online

Can we solve D using DP?

I'm stuck with Problem-D. My Code

In your code, you sort vt in .first(aoki) order, this is the mistake.

If the testcase is like this:

Your code will output

`2`

(`1`

in fact)The right method is to sort it in 2*Atoi+Takahashi order.

You can see the detail here

I got it now. Thanks.

for problem B, isn't the expression |x2−x1|≥|y2−y1| same as (y2-y1 >= x1-x2 && y2-y1 <= x2-x1) ?? Seems like it's not correct. How are they different ?? Thank you !

Hint : $$$|-7| \geq |-5|$$$

If anybody is interested in watching a screencast of this contest you can have a lot at my YouTube video where I am solving the problems A to E. Link: ABC 187 Screencast

In F — Close Group Editorial, it is written that

`One can determine if each induced subgraph is complete in O ( 2^N*N^2 ) time for all S`

. Why so? I mean for any subgraph all I need to do is check if all there is an edge to other vertex or not. It will take O(N^2) only. Thank you for the help.It is supposed to mean that the

totalamount of time needed to check the completeness forallsubgraph is $$$O(2^N N^2)$$$, since it needs $$$O(n^2)$$$ time for each of $$$O(2^n)$$$ graphs. (Is the original statement confusing?)No. The editorials are just fine. I missed the context it was trying to build in 2-3 preceded lines & wrote the comment in a hurry. Thank you for replying. :)

Please point out my mistake, here's my solution

How to solve B, in time complexity of NlogN ?