We will hold AtCoder Beginner Contest 142.

- Contest URL: https://atcoder.jp/contests/abc142
- Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20190928T2100&p1=248
- Duration: 100 minutes
- Number of Tasks: 6
- Writer: beet, Drafear, kort0n, ynymxiaolongbao
- Rated range: ~ 1999

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

We are looking forward to your participation!

fixed! thanks!

Auto comment: topic has been updated by chokudai (previous revision, new revision, compare).Good contest! :D

It's my first time to solve all the problem in ABC,How happy I am!

But how to solve F,I guess if a graph has a cycle ,the answer is one of the smallest cycles.

I think so too. I did it by finding a cycle, and then simplifying it to the point, so that no subset of nodes can form the cycle. My submission : https://atcoder.jp/contests/abc142/submissions/7764708

Mine :https://atcoder.jp/contests/abc142/submissions/7764999

I believe you found smallest cycle right?

True

But could you explain why the answer is one of the smallest cycles.

It's not actually the smallest cycle, answer can be found just finding a simple cycle, with no subcycle, because only in such a cycle degree could be (1,1) for each node, otherwise one node outside of cycle lacks indegree and if part of cycle, then a simpler cycle exists.

The simple cycle must be one of the smallest cycles.

I don't think that is necessary.

But how to find the simple sycle

Consider the image :D https://imge.to/i/vcKAat

Since all smallest cyles are simple, so I finding simple cycle is easier than any smallest cycle i believe. Find any cycle, keep removing vertices from it till , if after removal, you still have a cycle in that graph, and eventually you get a simple cycle.

rohit_goyal so what's the final answer? We just need to find a cycle ..right ? How to modify the DFS to do the same ?

I did 1 redundant thing in it,Finding 1 cycle before using dfs, and then finding shortest version of it. Instead you can remove a vertex from graph, check if the graph still contains cycle, if it does keep it removed, otherwise connect it back, O(n^2) should be fine here. At the end of all n iterations (of removing vertices ), you will have a final set of vertices that form a simple cycle.

Editorial ? how to solve E?

$$$O(2^N\times M)$$$ DP.

For $$$i<2^N$$$ and $$$j < M$$$,

`DP[i][j]`

should be the minimum cost for having exact treasures corresponding to $$$i$$$.Edit: using only first j keys of course.

is it bit-masking or something Greedy will work

I thought of the state but was having problem with transitions. Can you help how should one go about coding transitions of such bitmask dp ?

Let

`state[j]`

be bitmask encoding of $j$th key and`cost[j]`

be cost of $j$th key, then`DP[i | state[j]] = min(DP[i | state[j]], DP[i][j - 1] + cost[j])`

. It would be very hard to implement "top-down" DP in this problem.I didn't realise how to do a 'Forward' DP in this problem. So here is what I did.

Each of the keys has a mask associated with it.

For

`m = mask[i]`

, I look at all submasks of m,`S`

And set

`f(Mask) = min{f(Mask), f(Mask^S) + Cost(i)}`

In the 'Backward' DP, it is essential to visit all submasks of the current mask. Otherwise we might miss an optimal combination.

I now see the 'Forward' DP is much easier to understand and code

Why a top-down would be hard to implement?

Edit: here's what I did (had to fix some mistakes after the contest)

SpoilerSpoilerYou can also precompute a mask for each

`c[i]`

.Here's bottom up dp using different approach:

I had an idea but couldn't execute it cuz of time. We create bitmasks for every key based on the boxes it unlocks, for eg: if (j)th key unlocks box 6, turn on the (6)th bit of the (j)th mask. We need to find subset with minimum cost for which bitwise OR of all masks is ((1 << n)-1)<<1 .

1D dp is enough.

No need of 2D dp.

My solution:https://atcoder.jp/contests/abc142/submissions/7762980

hello HARSH got stuck finding the issue with my code.would be really grateful if u could suggest any fault........(http://atcoder.jp/contests/abc142/submissions/7776427)

Wrong logic!!! You have to use bitmask for combinations.

Im just trying to cover all numbers starting from n to 1 by using the ranges

But I can't understand what are you doing.

The test cases for F was weak, my $$$O(N^3)$$$ solution got accepted because I made some brave assumption.

https://atcoder.jp/contests/abc142/submissions/7755831

Note: before every return of

`dfs`

,`visit[v]`

should be reset to 0.Can somebody explain F? I got all testcases accepted except 2 of them...

Maybe you fail on such testcase:

2 2

1 2

2 1

(Just maybe)

Missing Geothermal's editorials :|

yupp

How to Solve D?

Count the number of distinct common prime factors + 1

First we make the observation that all common factors of A and B must be a factor of their gcd. The gcd of A and B can be computed very quickly (in about log(A) time) using the following formula: gcd(A, B) = {A if B = 0, gcd(B, A % B) if B != 0} Then, we observe that there is a greedy algorithm. It is always optimal to take all of the prime factors of gcd(A, B) (and 1). This can be proven with exchange argument. Suppose it is optimal to take some K = x * y, where x, y > 1. There exists no other item L we took that have gcd(K, L) > 1, or it would violate the constraints. Thus, gcd(x, L) = gcd(y, L) = 1, and it is more optimal to take x and y instead of K. So just prime factorise gcd(A, B) and add 1 to the number of distinct prime factors. This can be done in roughly O(sqrt(A)) time, which passes.

Sample Code: https://atcoder.jp/contests/abc142/submissions/7751965

I just didn't understand why the max prime number you will need will be less than 10⁶

because biggest prime factor of a number n can be maximum sqrt(n) ; sqrt(10^12)=10^6

what if the number is prime? greater then 1e6

when the number doesn't divide the numbers upto 1e6,than it's prime

if one of the two numbers is Prime then the gcd will always equal to 1

Not necessarily. Firstly, the biggest prime factor can be larger than 10^6, consider for example 2000000014, which is (10^9 + 7) * 2. As you can see, in my code, when I check against a prime number and it is divisible, I divide the gcd by the prime number until it is no longer divisible. After I check against all prime numbers under 10^6, if the remaining number is not 1, then it must be a prime greater than 10^6 as gcd(A, B) is at most 10^12, and thus has AT MOST one prime factor greater than 10^6. If it is not 1, I add 1 again to account for that prime factor.

how to solve D??

the number of divisor of gcd(a,b) + 1

is there any proof for this??

yeah cause if u have let's say x as divisor n times u can just take one from it cause the anyone from rest will not be coprime with it

prime divisor**

Can someone tell me the recursive DP solution to the problem E??

Here is my solution

Can E be solved with any shortest path algo? I tried to solve it with priority_queue but it doesn't pass 3 tests.

For Problem F, we just claim that any smallest cycle in the graph is a possible answer.

First of all, if there is no cycle in the graph, the answer is obviously -1. Otherwise, assume we find a smallest cycle in the graph. We can show that if it isn't a simple cycle, then any extra edge in the subgraph will make there exists a smaller cycle.

Then we simply find the smallest cycle in the graph. My solution runs BFS from each vertex to find the smallest cycle containing it, and among all the possible cycles output the smallest one.

My Submission

Can we improve this solution to O(n)??

Well, I think "minimum cycle" should be a classic problem, so I did some search. The optimal way I could find is to do some modification on all pairs shortest path algorithms, like the classic cycle-detection Floyd-Warshall algorithm. I think the problem should have the same complexity as APSP algorithms. Since all edges have side length 1 here, the best we can achieve is $$$O(N(N+M))$$$.

However, I tried another way to solve this problem, to find the "minimal cycle". The following solution is inspired by Tarjan's algorithm to detect strong connected components, and I think it solves this problem in $$$O(N+M)$$$. In simple words, I try to find a vertex with back edge (if multiple back edges, choose the one with maximum depth of head) in the DFS tree, that means we find a strongly connected component with only one back edge. Since the SCC must be a DAG plus a back edge, we can find the minimum cycle which is a subgraph of this SCC in one pass.

This algorithm does not give the minimum cycle in the graph, but it does give a minimal cycle.

My Submission

I didn't get E can any one explain it to me and it's solution ?

You have N treasure chests you want to open. There is a shop that sells M keys. Each key has a cost to buy and each may open different chests. What is the minimum cost to buy keys that make it possible to you to open all the chests?

It is a DP solution, where in each state of the DP[K][chests_bitwise] you see if it is cheaper to buy the Kth key and open the chests, or skip the key and check for the next one.

Hope I explained well enough

Here's my solution Edit: updated solution so it has English friendly variables

Thank you now I got it ! in the begin i was confused by the input format.

Nice solution. I managed to remove 2nd state using the fact that taking again any key again would just increase the cost, Here's my solution if anyone want to see : https://atcoder.jp/contests/abc142/submissions/7754799 Edit :By second, I meant key state, your 1st state used.

Hello, can someone tell me why I'm getting WA on two test cases in problem F? Here's my submission: https://atcoder.jp/contests/abc142/submissions/7777079

Try this case:

9 12 1 5 5 2 2 7 7 3 3 8 8 4 4 9 9 1 1 2 2 3 3 4 4 1

In this case your program gives a wrong answer. The case even if its big it is symmetric and easy to understand if you draw it in the paper.

I assume that you are doing wrong what I did initially as well. When you are at node=1, then you are moving at node=5 but from node=5 you can't move to node=2 because node=2 was neighbor of node=1, but your source-code is moving there and its wrong.

So the way I fixed it was to mark as visited all the neighbors of a node, but keep a vector of "goodNeighbors" so as to be possible to go from node=1 to node=2, but not from node=5 to node=2.

This is my submission: https://atcoder.jp/contests/abc142/submissions/7785403

I see, it looks like some sort of DFS/BFS hybrid. Thanks a lot for the help, been trying to figure out the bug since the contest ended.

editorial: https://img.atcoder.jp/abc142/editorial.pdf

Where can I find this kind of editorial??

Why my code on problem D got

`TLE`

. I think the complexity is just $$$O(sqrt(n))$$$. Why I got TLE? My codeIt's all my fault, i set

`int*int`

to compare with`ll`

and it caused me 1 hours :'(The test cases for F was weak.

For example, https://atcoder.jp/contests/abc142/submissions/9838374 This solution thinks that searching from any point must find the answer, but it is actually wrong.

case: 6 9 1 5 1 2 2 6 2 3 3 4 3 1 6 3 4 1 5 2

output: 5 1 5 2 6 3

answer: 3 1 2 3

In problem D : Link

What is the wrong with this code : Link ?

In the primes vector, you are pushing elements only till 1e3 at max, i.e. in the p*p<=1000000 loop, which goes for p=1e3 at max. Instead of pushing elements in the sieve itself, you can iterate over the bitset and check which elements are set. In this way you will get all primes till 1e6 and not just till 1e3. Below is the accepted code with the required change.

Soln