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?

How to pass all cases in D???

Dynamic Programming !!

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.

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

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.

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]

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.

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

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

Yes

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 ?

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

s = 0;
for i=0 to n-1
	s+=a[i];
	v.pb(a[i]*2 + b[i]);
sort(v.rbegin(),v.rend());
p =0;
ans = 0;
for i=0 to n-1
	p = p + v[i];
	if(p>s)
		ans = i+1;
		break;
cout<<ans<<"\n";

struct cmp {
    bool operator() (const pair<int,int> &a, const pair<int,int> &b) 
    const {
        return a.fr*2+a.sc==b.fr*2+b.sc?a.fr>b.fr:a.fr*2+a.sc>b.fr*2+b.sc;
    }
};

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

see above comments

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

This is most likely not a python issue.

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

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.

bitmask dp

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:

1. $$$x$$$ is parent of $$$y$$$
2. $$$y$$$ is parent of $$$y$$$

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!

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)

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!!!

try this:

1 5
4 1
3 0

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

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

• if $$$i = n + 1$$$, then $$$ans = \min(ans, |Cliques|)$$$.
• for each $$$clique$$$ in $$$|Cliques|$$$, if all vertexs in $$$clique$$$ has an edge to the $$$i$$$-th vertex, we could add $$$i$$$-th vertex to $$$clique$$$.
• the $$$i$$$-th vertex can form a new clique itself.

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

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

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

Check this case — 2 !a a.

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

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

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

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

If the testcase is like this:

3
1 100
10 1
10 1

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

It is supposed to mean that the total amount of time needed to check the completeness for all subgraph 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?)

Rotate the plane by 45 degrees. For each point, we want to count the number of points with greater x- and y- coordinates. If we inspect them in the increasing order of x-coordinates, we can manage how many points are there on each y-coordinates, and find the sum of them within specific range with BIT.