### chokudai's blog

By chokudai, history, 2 months ago, We will hold AtCoder Beginner Contest 199（Sponsored by Panasonic）.

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

We are looking forward to your participation! Comments (66)
 » 5 hours to go! ALL THE BEST Everyone !
 » It felt like it was just the opposite of Last ABC198.
 » How to do D ?
•  » » The Editorial is out.https://atcoder.jp/contests/abc199/editorial
•  » » 2 months ago, # ^ | ← Rev. 6 →   Create a topological sort(or just some ordering) for the different components. The First vertex in the sorting of the component has 3 options and the rest have 2 options, so you can bruteforce in $O($$N$$2^N$).Submission
•  » » » How will it work for this test case 20 0 ?
•  » » » » 2 months ago, # ^ | ← Rev. 2 →   There will be 20 separate components and just the first vertex will have 3 options, so 3^20.
•  » » » » 2 months ago, # ^ | ← Rev. 4 →   I dont know why my solution fails...I have used the following logic :If any of the vertices of a component have degree 3 or higher so our total answer is 0 as there will be atleast one edge having same colored vertices by PHP.So now our graph will be of a chain form. Now this chain can be of 2 types: Case-1 : Connected on the 2 ends so there is exactly one cycle. - Contribution of such a component would be 3*2^(Size of component-2).Case-2 : Or this chain is just a normal chain. - Contribution of such a component would be 3*2^(Size of component-1).Total answer would be multiplication of all such individual components.It passes on some 35 cases.Code : D... //Think simple yet elegant. #include using namespace std; #define fast ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); #define ll long long #define all(v) v.begin(),v.end() #define F first #define S second #define pb push_back #define mp make_pair #define ar array #define pi pair #define REP(i,n) for(int i=0;i vis(25,false); vector> g(25); ll parent; bool ok=false; ll sz; void check_dfs(int v){ vis[v]=true; if(g[v].size()>2) ok=true; for(int to : g[v]){ if(!vis[to]) check_dfs(to); } } bool dfs(int v, int par) { // passing vertex and its parent vertex vis[v] = true; ++sz; for (int u : g[v]) { if(u == par) continue; // skipping edge to parent vertex if (vis[u]) { //cycle_end = v; //cycle_start = u; return true; } parent[u] = v; if (dfs(u, parent[u])) return true; } return false; } void run_case(){ int n,m,i,u,v; cin >> n >> m; for(i=0;i> u >> v; --u,--v; g[u].pb(v); g[v].pb(u); } ll ans=1; for(i=0;i
•  » » » » » 2 months ago, # ^ | ← Rev. 3 →   how about this 4 3 1 2 1 3 1 4 
•  » » » » » » Right got it i was thinking too much narrowly.
•  » » » » » If any of the vertices of a component have degree 3 or higher so our total answer is 0 as there will be atleast one edge having same colored vertices by PHP.That is incorrect. Solution would still exist if degree>=3. According to me solution wouldn't exist if and only if any node has at least three neighbours which are connected to each other.
•  » » » 2 months ago, # ^ | ← Rev. 2 →   what was the use of topo sort? why cant we do direct dfs?
•  » » » » Idk maybe you can use direct dfs but I used an ordering so I can represent the component as a list and assign the colors from left to right.
•  » » » » » by component, u mean disconnected component? or any thing else
•  » » » » » » I mean a connected component.
•  » » » What exactly you mean by topological sort here ? thee given graph is an undirected one
•  » » » Can you explain why are you returning 1 in your brute function when we reach the end of a list? Should we not return 0 there?
•  » » 2 months ago, # ^ | ← Rev. 2 →   We can fix a subset of vertexes that will be assigned a particular colour. After checking if that subset is valid, we can do bicoloring on the remaining vertexes, we can swap both the colours in the bicoloring, so if bicoloring is possible ,we have 2 ways to colour it, As we won't visit the nodes, whose colour has been already fixed, so we will get more than one components, we can multiply the result of each component. Overall Time Complexity will be O(N*2^N)
•  » » » To check for bipartiteness in $O(N)$, I converted the adjacency list of a vertex to bitmask and used bitwise operations. Did you do the same, and if not, how did you calculate bipartiteness in linear time of number of nodes (and not in linear time of number of edges)?
•  » » simply take a array named marked and mark all the vertex you encounter during input.The dfs(1) in the dfs function their are three base cases 1. If your currentt vertex(now)==n+1 simply increment ans and return 2. if you find a unmarked array just go for dfs(now+1) and return 3. else just loop from 1 to 3 set te colour of current vertex as i and check if any child has same colour if not go for next dfs HOPE THIS HELPS! Link to my solution
•  » » » Your solution link is taking to the problem.
•  » » » »
•  » » » what's the logic behind your approach?
 » 2 months ago, # | ← Rev. 2 →   Why is the editorial solution for D not 2^n * n^2? I have a similar algorithm, where I start a DFS and perform a 2-coloring. But I would think the DFS requires O(N^2) time, since there are O(N^2) edges.
•  » » But you wont visit all edges right ? Maximum visit is N ig cuz each dfs call takes you to a new vertex.
•  » » » well the complexity of dfs is O(N+M) so he is kind of right since u have a loop towards all the neighbours of a paticular vertex in dfs
•  » » Can you elaborate a bit more on how to use the 2-colouring DFS method to solve this problem?
•  » » » 2 months ago, # ^ | ← Rev. 2 →   My solution is almost the same as the editorial, except I implemented it a bit differently. One way to think about this problem is that if we fix the nodes of one color, you only have two other colors left to color with (which just corresponds to the number of two colorings of the graph).
•  » » I guess you could check if a certain coloring is valid in O(3*n) by using mask (actually it would divide the complexity by 32, which is bigger then n, which means O(1)). In more detail: for a certain coloring, for every color x, get the mask of nodes with color x. Also represent the neighbors of a certain node as a mask too. If the mask of neighbors of a node with color x has any common bit set with the mask of all nodes with color x, then it is not valid.
 » How to Solve D?My failed solution:- for a connected component assign the all node as 3 and run a dfs if the current node points towards x already visited mode then subract x from 3(note minimum value for particular node is 0) then multiply value of all the nodes.final ans = multiplication ans of each connected component
•  » » 2 months ago, # ^ | ← Rev. 2 →   .
•  » » » No sir I passed 41 cases but failed 7.No TLE
•  » » I did a similar approach and passing 41 test cases. Let me know if you can find a test case where it fails.
•  » »
•  » » » Thank you!
•  » » » what a beautiful solution. Thanks!
 » Can we solve D using bitmask DP?
•  » » Maybe, but since it is a graph with cycles it is hard to come up with states for the dp because of not a strict topological ordering of states.
 » what will be the complexity of DP with bitmask of E??
•  » » It would be ${O(N * (2 ^ N))}$ in the worst case.
 » MY submission for c Can anyone tell me why my submission for c did not tle?? I was swapping two strings in type two..
•  » » string.swap(string) actually does not copy the strings, but only pointers to them.
•  » » » OK, Thank you , didn't knew about this thing earlier :)
•  » » » » 2 months ago, # ^ | ← Rev. 2 →   It is same for other structures like vector, set and the like, they all support such a quick swap method.
 » Editorial of E seems more complecated than the problem itself. Can somebody explain?I have difficulties to understand any of the formulars.
•  » » +1
•  » » 2 months ago, # ^ | ← Rev. 2 →   We can do it in O(N*M*2^N). We can try to put each possible value at current position if current value satisfies all the given inequalities. we can implement it using a DP of dp[N][1<
•  » » 2 months ago, # ^ | ← Rev. 2 →   What I did was the following — For each $x$ store all the possible $(y, z)$ along with it. Calculate the answer using bitmask DP where $dp[i][mask]$ denotes that we have placed elements till $i^{th}$ position and the numbers already placed are represented by $mask$ When I am on a certain $i$ check whether the all the stored $(y, z)$ for that particular index are satisfied or not. If all are satisfied, transition into next state by setting one of the unset bit of $mask$ and increment $i$ Return 0 when $i = n$ Link to submission — https://atcoder.jp/contests/abc199/submissions/22030060
•  » » » 2 months ago, # ^ | ← Rev. 2 →   Note that you dont need dp[i][mask] cuz i == __builtin_popcount of the mask, therefore i is redundant, dp[mask] is enough
 » problem C is solvable if we just implement the query naively and ignoring any 2 consecutive query of type 2 i am not sure why this pass the time limit though
•  » » Yeah, it shouldn't because that's just $O(N^2)$ with an easy optimization. I guess the tests were just weak, but maybe that means someone can add a hack (not sure what it's called in Atcoder)
 » Can someone tell me whether my approach to problem D is wrong? I assumed that the maximum number of nodes coloured with a particular colour can't exceed N/2. So, i distributed the colours in such a way that the count of red , blue of green always remain less than N/2. It is giving WA on exactly three test cases. Code for Reference
•  » » Consider: 5 4 1 2 1 3 1 4 1 5 Nodes 1 through 5 form one component. We can color Node 1 with red and nodes 2 to 5 with blue.
•  » » » O ya, thanks for your countertest. I removed now this condition and got accepted!
 » Can anyone tell me a testcase where my solution fails for D? I am using dfs and at every node mutiplying (3 — neighbours which are not visited) with the answer till now and if I reach a node with 3 or more visited numbers, it becomes 0. Doing that for every connected component and multiplying all of their answers. My submission: https://atcoder.jp/contests/abc199/submissions/22038878
•  » » Try 5 6 1 2 1 3 1 4 5 2 5 3 5 4 gives 12, should be 30.
•  » » » 2 months ago, # ^ | ← Rev. 3 →   Here's an smaller case: 4 4 1 2 2 3 1 4 4 3 If we DFS from 1, and end up visiting in this order: 1 -> 2 -> 3 -> 4, when we are at 4, your solution would count that 4 can only have one color choice (since 1 and 3 have been visited), but since there is no edge between 1 and 3, nothing forbids them from having the same color.If this DFS algorithm worked, then k-coloring would be solvable in polynomial time :)
•  » » » » Thanks a lot man! This had been bugging me a lot. Now it makes sense.
 » https://www.youtube.com/watch?v=2y3stYERBAIThis is my screencast(rank 77) for the contest along with solutions for all problems, do check it out if you're interested.
•  » » 2 months ago, # ^ | ← Rev. 2 →   what was the use of dfs tree in problem D?
•  » » » My solution is same as this https://codeforces.com/blog/entry/89979?mobile=false#comment-784021The dfs tree just automatically defines a toposort, which is something i realised after the contest.
•  » » » » why can't we solve this without using a dfs tree? Can we simply use backtrack in dfs like you did just without defining that level thing?
•  » » » » Dfs tree approach is a nice one. Earlier I thought of a approach that had something to do with the cycles in the graph but wasn't able to conclude something with that. If you have any ideas that may help with such a approach it would be helpful to know. Peace
 » can anyone explain what problem E asked to do?
 » 2 months ago, # | ← Rev. 2 →   Hello, can someone explain how does this solution for E comfortably pass?https://atcoder.jp/contests/abc199/submissions/22041985Isn't the time complexity $O(mn2^n)$?For each available bit in the current bitmask we test all m conditions, and if this bit doesn't violate any condition we add it to our mask. n is up to 18 m is up to 100$O(mn2^n)$ would then mean about 2^29 operations...?
•  » » You don't visit all $N*2^N$ states of the dp table. The states that you end up visiting are of the form dp[popcount(MASK)][MASK]. Your first state is redundant, you can remove it and it still ACs:https://atcoder.jp/contests/abc199/submissions/22081874