### chokudai's blog

By chokudai, history, 3 weeks ago,

We will hold AtCoder Beginner Contest 187.

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

We are looking forward to your participation!

• +61

 » 3 weeks ago, # |   +36 For anyone interested, I'll be doing a post-contest stream on Twitch.
•  » » 3 weeks ago, # ^ |   0 Great!
•  » » 3 weeks ago, # ^ |   +3 Waiting for last one.
•  » » 3 weeks ago, # ^ |   0 It's on YouTube: https://youtu.be/CyAS9PbR-l8
•  » » 3 weeks ago, # ^ |   0 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?
•  » » » 3 weeks ago, # ^ |   0 I think if anything I'd expect the vector to be faster, the only thing is you need to make sure it's sorted.
 » 3 weeks ago, # |   +1 Bump. Contest Starting!
 » 3 weeks ago, # |   +11 How to solve F? Is the answer minimum number of clique in graph?
•  » » 3 weeks ago, # ^ |   0 How to pass all cases in D???
•  » » » 3 weeks ago, # ^ |   0 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
•  » » 3 weeks ago, # ^ |   0 Dynamic Programming !!
•  » » » 3 weeks ago, # ^ |   0 If you mean dp on subset I won't work since 3^18 is too big unless I am missing something
•  » » » » 3 weeks ago, # ^ |   0 O(3^n) is OK, because the constant is very low, my solution passed in 0.5s/6s
•  » » » » » 3 weeks ago, # ^ |   0 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 ?
•  » » 3 weeks ago, # ^ |   0 I solved it by bitmask DP with O(3^n). But I'm not sure whether it's the best solution.
•  » » 3 weeks ago, # ^ | ← Rev. 2 →   0 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)
•  » » 3 weeks ago, # ^ |   +10 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)
•  » » 3 weeks ago, # ^ | ← Rev. 2 →   +3 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.
 » 3 weeks ago, # |   0 How to solve D. I tried to sort on the basis of a[i]+b[i] value but kept getting WA.
•  » » 3 weeks ago, # ^ | ← Rev. 2 →   +3 you need to sort by 2*a[i]+b[i]
•  » » » 3 weeks ago, # ^ |   0 why ?
•  » » » » 3 weeks ago, # ^ |   0 Go check out AnandOza stream.
•  » » » » » 3 weeks ago, # ^ |   +16 Thanks!
•  » » » » 3 weeks ago, # ^ | ← Rev. 3 →   0 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
•  » » » » 3 weeks ago, # ^ |   0 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.
•  » » » 3 weeks ago, # ^ |   0 Could you please explain?
•  » » » » 3 weeks ago, # ^ |   0 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].
•  » » » » 3 weeks ago, # ^ |   +4 With every speech Aoki will lose a votes Takahashi will gain a + b votes. So total votes gained = a + b - (-a) = 2 * a + b
•  » » » » » 3 weeks ago, # ^ |   0 Thanks a lot.
•  » » » 3 weeks ago, # ^ |   0 What is proof of correctness for this greedy approach ?
•  » » » » 3 weeks ago, # ^ |   0 Cost of speech for each town is the same. As the cost is the same, choose greedily by gain as mentioned in previous comments.
•  » » » 3 weeks ago, # ^ |   0 Thank you so much for helping.
•  » » » 3 weeks ago, # ^ |   0 But why ?Why a[i]+b[i] is not working and why multiply by 2 working ?
•  » » » » 3 weeks ago, # ^ |   +3 In this case: 1 4 3 1 2 0 The correct answer is 1.(By giving speech on the 2nd city)But yours will output 2
•  » » » » » 3 weeks ago, # ^ |   0 1<=Ai,Bi<=1e9
•  » » » » » » 2 weeks ago, # ^ |   +1 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]
•  » » » » 3 weeks ago, # ^ |   +5 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.
•  » » » 3 weeks ago, # ^ | ← Rev. 3 →   +6 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 usWe need $A + B$ > $suma - A$$2A + B > suma$So, we need sort by 2*a[i]+b[i]
•  » » » » 3 weeks ago, # ^ |   0 link to your solution ?
•  » » » » » 3 weeks ago, # ^ |   0
•  » » 3 weeks ago, # ^ |   0 you need to sort it based on 2*a[i] + b[i]
•  » » 3 weeks ago, # ^ |   +4 sort according to 2*a[i] + b[i]
•  » » 3 weeks ago, # ^ |   +4 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.
•  » » 3 weeks ago, # ^ | ← Rev. 2 →   +3 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.
•  » » 3 weeks ago, # ^ | ← Rev. 5 →   0 Try this input: 2 1 8 7 1 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.
 » 3 weeks ago, # | ← Rev. 2 →   0 Please anyone point out the mistake in my code or logic? Task D https://atcoder.jp/contests/abc187/submissions/19154830
•  » » 3 weeks ago, # ^ |   0 Maybe you should sort in basis of 2 * vp[i].ff + vp[i].ss.
•  » » 3 weeks ago, # ^ |   0 I guess sorting is wrong which leads to WA in some test cases, try it by sorting with 2*a[i] + b[i]
•  » » 3 weeks ago, # ^ | ← Rev. 2 →   0 try this input: 2 1 8 7 1 
 » 3 weeks ago, # |   0 Can anyone tell me how to approach the problem E? https://atcoder.jp/contests/abc187/tasks/abc187_e
•  » » 3 weeks ago, # ^ |   0 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.
•  » » » 3 weeks ago, # ^ |   +16 Segment tree is overkilled here. Just using simple dfs as the comment below! My ugly code: https://ideone.com/PAEUDp
•  » » » 3 weeks ago, # ^ |   +5 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. Code#include #include #include #include #include #include #include #define REP(i,a,b) for (auto i = a; i != b; i++) #define maxheap priority_queue < ll, std::vector, std::less > #define minheap priority_queue < ll, std::vector, std::greater > // mxheap.push(), mxheap.top(), mxheap.pop() #define ll long long int #define ld long double #define vi vector #define vll vector #define vvi vector < vi > #define pii pair #define pll pair #define mod 1000000007 #define inf 1000000000000000001 #define all(c) c.begin(),c.end() #define mp(x,y) make_pair(x,y) #define mem(a,val) memset(a,val,sizeof(a)) #define eb emplace_back #define f first #define s second #define pb push_back #define SQ(a) (a)*(a) using namespace std; // using namespace FastIO; void read(int n,vector& x) { x.clear(); x.resize(n); for(int i = 0;i>x[i]; } } void read(int n,int m,vector>& x) { x.clear(); x.resize(n,vector(m)); for(int i = 0;i>x[i][j]; } } void read(int n,vector>& x,vector>& edges) { x.clear(); x.resize(n+1); edges.resize(n); for(int i = 0;i>a>>b; edges[i+1].first = a; edges[i+1].second = b; x[a].pb(b); x[b].pb(a); } } void read(int n,vector>& x,int m) { x.clear(); x.resize(n+1); for(int i = 0;i>a>>b; x[a].pb(b); x[b].pb(a); } } void read(int n,vector& x) { x.clear(); x.resize(n); for(int i = 0;i>x[i]; } } void DFS(int x,vector>& adj,vector&c,vector& vis){ vis[x] = 1; for(auto it : adj[x]){ if(vis[it] == 0){ c[it] += c[x]; DFS(it,adj,c,vis); } } } int main() { std::ios::sync_with_stdio(false); int T = 1; // freopen("mixmilk.in", "r", stdin); // freopen("mixmilk.out", "w", stdout); //cin>>T; for(int t = 1;t<=T;t++) { // cout<<"Case #"<>n; vector> adj; vector> edges; vector c(n+1); read(n,adj,edges); vector dis(n+1,-1); queue q; dis[1] = 0; q.push(1); while(!q.empty()){ int x = q.front(); q.pop(); for(auto it : adj[x]){ if(dis[it] == -1){ dis[it] = dis[x]+1; q.push(it); } } } int query; cin>>query; for(int i = 0;i>type; if(type == 1){ int ei; ll ci; cin>>ei>>ci; int a = edges[ei].first; int b = edges[ei].second; if(dis[a] < dis[b]){ c[1] += ci; c[b] -= ci; } else{ c[a] += ci; } } else{ int ei; ll ci; cin>>ei>>ci; int b = edges[ei].first; int a = edges[ei].second; if(dis[a] < dis[b]){ c[1] += ci; c[b] -= ci; } else{ c[a] += ci; } } } vector vis(n+1); DFS(1,adj,c,vis); for(int i = 1;i<=n;i++){ cout<
•  » » 3 weeks ago, # ^ | ← Rev. 2 →   0 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.
 » 3 weeks ago, # |   +4 How to solve Problem E ? Thanks in advance!
•  » » 3 weeks ago, # ^ |   +15 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).
•  » » » 3 weeks ago, # ^ | ← Rev. 2 →   0 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 hereEdit: actually got it, it's because u and v are connected by 1 edge.
•  » » » » 3 weeks ago, # ^ |   0 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.
•  » » 3 weeks ago, # ^ | ← Rev. 2 →   +8 I made a euler tour array and just updated the suitable ranges with segment tree
•  » » 3 weeks ago, # ^ |   0 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
 » 3 weeks ago, # |   0 is there any greedy solution for D?
•  » » 3 weeks ago, # ^ |   +1 Yes HintStore the input in vector of pairs and sort using 2*a+b
•  » » 3 weeks ago, # ^ |   +1 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.
•  » » 3 weeks ago, # ^ |   +2 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 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<
 » 3 weeks ago, # | ← Rev. 2 →   0 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. (a.first+a.second)==(b.first+b.second))?(a.first>b.first):(a.first+a.second)>(b.first+b.second) Then greedily choose the elements if it's strictly greater or not.What am I missing? my sub
•  » » 3 weeks ago, # ^ |   0 struct cmp { bool operator() (const pair &a, const pair &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; } }; 
•  » » » 3 weeks ago, # ^ | ← Rev. 2 →   +1 can also do like this sort(all(vo), [](pii a, pii b){ return make_pair(2LL*a.first + a.second, a.first) < make_pair(2LL*b.first + b.second, b.first); }); 
 » 3 weeks ago, # |   +9 how to solve F?
 » 3 weeks ago, # |   0 how to solve Problem F? T_T
 » 3 weeks ago, # |   0 Is problem E related to segment tree or DSU?
•  » » 3 weeks ago, # ^ | ← Rev. 2 →   0 No you can use dfs,bfs with difference array and you can root the tree.
•  » » 3 weeks ago, # ^ | ← Rev. 3 →   0 I used Lazy Segment Tree. My submission: E — Through Path
 » 3 weeks ago, # |   0 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 .
 » 3 weeks ago, # |   0 Any hints on D? Tried solving by taking maximum (a[i]+b[i]) but it gave WA.
•  » » 3 weeks ago, # ^ |   0 sort according to $2*a[i]+b[i]$ instead $a[i]+b[i]$
•  » » 3 weeks ago, # ^ |   0 see above comments
•  » » 3 weeks ago, # ^ |   0 You should take maximum(2*a[i]+b[i])
 » 3 weeks ago, # |   0 It is so painful to solve the problem (E) but fail to get AC because it is python and you get three TLE
•  » » 3 weeks ago, # ^ |   +1 This is most likely not a python issue.
•  » » » 3 weeks ago, # ^ | ← Rev. 2 →   0 I'm pretty sure it is python issueSolution is just a couple of dfss, O(n), there is not much to to optimize
•  » » » » 3 weeks ago, # ^ |   0 Why not switch to cpp for dfs problems?
•  » » » » » 3 weeks ago, # ^ | ← Rev. 2 →   0 I hoped for the bestHope is a dangerous thing, mehHad 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 bottlenecksTruth 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
•  » » » » 3 weeks ago, # ^ |   0 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
•  » » » » » 3 weeks ago, # ^ |   0 I know this trick and use it. Though it has nothing to do with TLE, it is needed to bypass python's stack limitations
•  » » » » » » 3 weeks ago, # ^ |   0 Hmm, got it)
•  » » 3 weeks ago, # ^ | ← Rev. 2 →   0 Funny thing btw. It TLEd in pypy, but passed in cpython. Too bad I didn't think about it during the contest
 » 3 weeks ago, # |   0 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?
•  » » 3 weeks ago, # ^ |   0 They asked if the query string is in the list, and also the query string with a pre "!" before it.
•  » » 3 weeks ago, # ^ |   0 Me too;
•  » » 3 weeks ago, # ^ |   0 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.
 » 3 weeks ago, # |   0 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.
•  » » 3 weeks ago, # ^ |   0 bitmask dp
 » 3 weeks ago, # |   0 How to solve E? Thanks in advance!
•  » » 3 weeks ago, # ^ | ← Rev. 2 →   +1 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.
•  » » 3 weeks ago, # ^ |   +4 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: $x$ is parent of $y$ $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!
 » 3 weeks ago, # |   +1 Hi, guys. I defined comparator on problem D, but the first code keep giving me runtime error, I use $\leq$ in the return line. bool cmp(pair &a, pair &b) { ll first = a.second + 2 * a.first; ll second = b.second + 2 * b.first; return first <= second; } 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? bool cmp(pair &a, pair &b) { ll first = a.second + 2 * a.first; ll second = b.second + 2 * b.first; return first < second; } 
•  » » 3 weeks ago, # ^ |   0 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)
•  » » » 3 weeks ago, # ^ |   +1
•  » » 3 weeks ago, # ^ |   +1 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.
•  » » 3 weeks ago, # ^ |   0 Never heard this rule before XD, learn something new today. Thank you both for giving me a hand!!!
 » 3 weeks ago, # | ← Rev. 2 →   0 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
•  » » 3 weeks ago, # ^ |   0 try this: 1 5 4 1 3 0 
•  » » » 3 weeks ago, # ^ |   0 Output is 2. It should be 1. I'll check. Thank you.
•  » » » 3 weeks ago, # ^ |   0 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.
 » 3 weeks ago, # |   0 Approach for Problem DThe most difficult part of the algorithm is the fluctuating value of Aoki's votes. 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).
 » 3 weeks ago, # |   0 How to solve F in less than $3^{n}$?
•  » » 3 weeks ago, # ^ |   +22 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
•  » » » 3 weeks ago, # ^ |   0 Can you please share the link of your ac submission?
•  » » » » 3 weeks ago, # ^ |   0
•  » » » » » 3 weeks ago, # ^ | ← Rev. 2 →   0 Thanks a lot!!
•  » » 3 weeks ago, # ^ | ← Rev. 5 →   0 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
•  » » » 3 weeks ago, # ^ |   0 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?
•  » » » » 3 weeks ago, # ^ |   +3 _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.
•  » » » » » 3 weeks ago, # ^ |   +3 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.
•  » » » » » » 3 weeks ago, # ^ | ← Rev. 4 →   0 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!)$.
•  » » » » » » » 3 weeks ago, # ^ |   0 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.
 » 3 weeks ago, # | ← Rev. 3 →   0 On problem DI want to askWhy is my greedy strategy wrongCan anyone provide a set of hack samples struct node { ll x,y,s; } a[maxn]; bool cmp(node x,node y) { return x.s>y.s; } int n; int main() { cin>>n; ll num = 0; for(int i=1 ; i<=n ; i++) { cin>>a[i].x>>a[i].y; a[i].s=a[i].x+a[i].y; num+=a[i].x; } sort(a+1,a+1+n,cmp); ll s=0; for(int i=1 ; i<=n ; i++) { s+=a[i].s; num-=a[i].x; if(s>num) { cout<
•  » » 3 weeks ago, # ^ |   0 Don't sort with a[i].x+a[i].y. Change it to a[i].s = 2*a[i].x+a[i].y.
•  » » 3 weeks ago, # ^ |   0 testcase - 1 4 3 1 2 0 answer is only 3,1
•  » » » 3 weeks ago, # ^ |   0 Thanks your test case
 » 3 weeks ago, # |   0 https://atcoder.jp/contests/abc187/submissions/19163293Plz 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 .
•  » » 3 weeks ago, # ^ |   0 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
 » 3 weeks ago, # |   0 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
•  » » 3 weeks ago, # ^ |   0 Check this case — 2 !a a.
•  » » 3 weeks ago, # ^ | ← Rev. 2 →   0 The problem is that you assume that strings without ! will appear first.Failed test case. 2 !a a
 » 3 weeks ago, # | ← Rev. 3 →   0 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/19163897Can anyone give me a tough side case for which it might fail?
 » 3 weeks ago, # | ← Rev. 2 →   +3 Video Editorial, and also screencast.You can also refer to the Source code and simple explanation.
 » 3 weeks ago, # |   0 My submission got runtime error on 3 tests for Problem D. Can someone help me with the reason for the Runtime error?
•  » » 3 weeks ago, # ^ |   +3 You have the same problem as me. you can look the previous post.
•  » » » 3 weeks ago, # ^ |   +1 Got it. Thanks
•  » » 3 weeks ago, # ^ |   +3 Your comparator must return false when values are equal. I changed that it got AC.
•  » » » 3 weeks ago, # ^ |   0 Thank you. Didn't know such trivial mistakes can give a RE.
 » 3 weeks ago, # |   0 apply DP in D and got 12 TLE
•  » » 2 weeks ago, # ^ |   0 DP doesn't always gives the fastest solution. Sometimes you need to be greedy.
 » 3 weeks ago, # | ← Rev. 3 →   0 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.
•  » » 3 weeks ago, # ^ |   0 I got it, the question is answer the minimum possible number of components, I misunderstood with the count of edges need to be removed...
 » 3 weeks ago, # |   +9 My solutions + explanations can be found here :)
•  » » 3 weeks ago, # ^ |   0 nice
 » 3 weeks ago, # |   0 Is there anyone who used segment tree in problem E??
•  » » 3 weeks ago, # ^ | ← Rev. 3 →   -7 I think that intended solution was flattening tree with segment treeupd: codeupd 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
 » 3 weeks ago, # |   0 Can we solve D using DP?
 » 3 weeks ago, # |   0 I'm stuck with Problem-D. My Code
•  » » 3 weeks ago, # ^ | ← Rev. 3 →   0 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
•  » » » 3 weeks ago, # ^ |   0 I got it now. Thanks.
 » 3 weeks ago, # |   0 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 !
•  » » 3 weeks ago, # ^ |   0 Hint : $|-7| \geq |-5|$
 » 3 weeks ago, # | ← Rev. 2 →   -8 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
 » 2 weeks ago, # |   0 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.
•  » » 2 weeks ago, # ^ | ← Rev. 2 →   0 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?)
•  » » » 2 weeks ago, # ^ |   +8 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. :)
 » 2 weeks ago, # |   0