We will hold AtCoder Beginner Contest 199（Sponsored by Panasonic）.

- Contest URL: https://atcoder.jp/contests/abc199
- Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20210424T2100&p1=248
- Duration: 100 minutes
- Number of Tasks: 6
- Writer: evima, kyopro_friends, QCFium, satashun, YoshikaMiyafuji
- Rated range: ~ 1999

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

We are looking forward to your participation!

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

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`

?There will be 20 separate components and just the first vertex will have 3 options, so 3^20.

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.

Case-2 : Or this chain is just a normal chain.

Total answer would be multiplication of all such individual components.

It passes on some 35 cases.

Code :

D...

how about this

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.

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?

Hey madlogic, I am quite confused with "the rest have 2 options", I don't understand how it goes with the sample test 1 in the problem statement. I read your solution; nicely written, and understood it quite well. But I am not able to understand how it goes with "the rest have 2 options". Where am I going wrong?

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.

try this

what's the logic behind your approach?

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?

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

.

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.

TRY THIS APPROACH

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

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

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<<N]. https://atcoder.jp/contests/abc199/submissions/22031532

What I did was the following —

Link to submission — https://atcoder.jp/contests/abc199/submissions/22030060

Note that you dont need dp[i][mask] cuz i == __builtin_popcount of the mask, therefore i is redundant, dp[mask] is enough

Regarding:

What about the order of the added elements? Isn't that important in the permutation?

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:

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

gives 12, should be 30.

Here's an smaller case:

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=2y3stYERBAI

This is my screencast(rank 77) for the contest along with solutions for all problems, do check it out if you're interested.

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

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

Hello, can someone explain how does this solution for E comfortably pass?

https://atcoder.jp/contests/abc199/submissions/22041985

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