### chokudai's blog

By chokudai, history, 6 months ago, ,

We will hold AtCoder Beginner Contest 142.

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

We are looking forward to your participation!

• +38

 » 6 months ago, # |   +62
•  » » 6 months ago, # ^ |   0 fixed! thanks!
 » 6 months ago, # |   0 Auto comment: topic has been updated by chokudai (previous revision, new revision, compare).
 » 6 months ago, # |   +3 Good contest! :D
 » 6 months ago, # |   +2 It's my first time to solve all the problem in ABC,How happy I am!
•  » » 6 months ago, # ^ |   0 But how to solve F,I guess if a graph has a cycle ,the answer is one of the smallest cycles.
•  » » » 6 months ago, # ^ | ← Rev. 2 →   +3 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
•  » » » » 6 months ago, # ^ |   +1
•  » » » » » 6 months ago, # ^ |   +3 I believe you found smallest cycle right?
•  » » » » » » 6 months ago, # ^ |   0 True
•  » » » » » » 6 months ago, # ^ |   0 But could you explain why the answer is one of the smallest cycles.
•  » » » » » » » 6 months ago, # ^ |   0 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.
•  » » » » » » » » 6 months ago, # ^ |   0 The simple cycle must be one of the smallest cycles.
•  » » » » » » » » » 6 months ago, # ^ |   0 I don't think that is necessary.
•  » » » » » » » » » 6 months ago, # ^ |   0 But how to find the simple sycle
•  » » » » » » » » » 6 months ago, # ^ |   +3 Consider the image :D https://imge.to/i/vcKAat
•  » » » » » » » » » 6 months ago, # ^ |   0 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.
•  » » » » » » » » » 6 months ago, # ^ |   0 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 ?
•  » » » » » » » » » 6 months ago, # ^ |   0 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.
•  » » » » » » » » » 5 months ago, # ^ |   0 rohit_goyal thanks dude
•  » » 5 months ago, # ^ |   0 could you explain problem c ?
 » 6 months ago, # | ← Rev. 2 →   0 Editorial ? how to solve E?
•  » » 6 months ago, # ^ | ← Rev. 2 →   0 $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.
•  » » » 6 months ago, # ^ |   0 is it bit-masking or something Greedy will work
•  » » » 6 months ago, # ^ |   0 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 ?
•  » » » » 6 months ago, # ^ |   +9 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.
•  » » » » » 6 months ago, # ^ | ← Rev. 14 →   0 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, SAnd set f(Mask) = min{f(Mask), f(Mask^S) + Cost(i)}  vector minimum_cost(complete_mask + 1, oo); minimum_cost[0] = 0; for(int i = 1; i <= no_of_keys; i++) { for(int m = 0; m <= complete_mask; m++) { if(is_submask(m,mask[i])) { for(int sub_m = 0; sub_m <= complete_mask; sub_m++) { if(is_submask(mask[i],sub_m)) { minimum_cost[m] = min(minimum_cost[m], minimum_cost[m^sub_m] + 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
•  » » » » » 6 months ago, # ^ | ← Rev. 4 →   +5 Why a top-down would be hard to implement?Edit: here's what I did (had to fix some mistakes after the contest) Spoiler//total is N^2 - 1 int dp(int key, int treasures){ if (key == M){ if(treasures == total) return 0; else return INF; } if(memo[key][treasures] != -1) return memo[key][treasures]; int a = dp(key+1, treasures | key_treasure[key]) + cost[key]; int b = dp(key+1, treasures); int ans = min(a,b); memo[key][treasures] = ans; return ans; } 
•  » » » » » » 6 months ago, # ^ | ← Rev. 5 →   0 what does dp(key,treasures) signifies ? can you explain or send your code...?Edit: got it... found your code: https://atcoder.jp/contests/abc142/submissions/7776682Thanks!
•  » » » » » » 6 months ago, # ^ |   0 Hey, I tried the same way but messed up in the base conditions . Can you explain the base condition at top ?
•  » » » » » » » 6 months ago, # ^ |   0 key is basically the index. key==m implies that you have tried m elements and no more are left so you need to check if the set of selected elements are equal to set {1,2,...n} if no then return infinity since that case is not possible, else return 0 which will add 0 to the total cost.
•  » » » » 6 months ago, # ^ |   0 Spoiler vector dp(MX, INF); dp[0] = 0; for (int i = 0; i < M; ++i) { vector nxt(dp); for (int mask = 0; mask < MX; ++mask) { int nmask = mask; for (int j = 0; j < b[i]; ++j) { nmask |= (1 << c[i][j]); } nxt[nmask] = min(nxt[nmask], dp[mask] + a[i]); } dp = nxt; } You can also precompute a mask for each c[i].
•  » » » 6 months ago, # ^ |   +1 Here's bottom up dp using different approach: cin>>n>>m; rep(i,0,m){ cin>>arr[i]; cin>>x; rep(j,0,x){ cin>>y; barr[i]|=(1<<(y-1)); } } for(i=0;i<=1001;i++){ for(j=0;j<=4900;j++) { if(i==0) dp[i][j]=INT_MAX; else dp[i][j]=INT_MAX; } } dp[0][0]=0; for(i=0;i
•  » » 6 months ago, # ^ | ← Rev. 2 →   0 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 .
•  » » 6 months ago, # ^ |   -13 1D dp is enough.No need of 2D dp.
•  » » » 6 months ago, # ^ |   0 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)
•  » » » » 6 months ago, # ^ |   -10 Wrong logic!!! You have to use bitmask for combinations.
•  » » » » » 6 months ago, # ^ |   0 Im just trying to cover all numbers starting from n to 1 by using the ranges
•  » » » » » » 6 months ago, # ^ |   0 But I can't understand what are you doing.
•  » » » » 6 months ago, # ^ |   0 remember we are using or operation for union of 2 sets.
 » 6 months ago, # |   +8 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/7755831Note: before every return of dfs, visit[v] should be reset to 0.
 » 6 months ago, # |   0 Can somebody explain F? I got all testcases accepted except 2 of them...
•  » » 6 months ago, # ^ | ← Rev. 2 →   +1 Maybe you fail on such testcase:2 21 22 1(Just maybe)
 » 6 months ago, # |   +17 Missing Geothermal's editorials :|
•  » » 6 months ago, # ^ |   0 yupp
 » 6 months ago, # |   0 How to Solve D?
•  » » 6 months ago, # ^ | ← Rev. 2 →   +5 Count the number of distinct common prime factors + 1
•  » » 6 months ago, # ^ |   +4 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.
•  » » » 6 months ago, # ^ |   0 I just didn't understand why the max prime number you will need will be less than 10⁶
•  » » » » 6 months ago, # ^ |   +1 because biggest prime factor of a number n can be maximum sqrt(n) ; sqrt(10^12)=10^6
•  » » » » » 6 months ago, # ^ |   +5 what if the number is prime? greater then 1e6
•  » » » » » » 6 months ago, # ^ |   0 when the number doesn't divide the numbers upto 1e6,than it's prime
•  » » » » » » 6 months ago, # ^ |   +1 if one of the two numbers is Prime then the gcd will always equal to 1
•  » » » » » » » 6 months ago, # ^ |   +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.
•  » » » » » » » » 6 months ago, # ^ |   0 Wow I like your logic, you reduced the time complexity by a great extend
•  » » » 6 months ago, # ^ |   0 Can you explain what is wrong with my code? It is problem D. https://pastebin.com/tKRWLxif
 » 6 months ago, # |   0 how to solve D??
•  » » 6 months ago, # ^ |   0 the number of divisor of gcd(a,b) + 1
•  » » » 6 months ago, # ^ |   0 is there any proof for this??
•  » » » » 6 months ago, # ^ |   0 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
•  » » » 6 months ago, # ^ |   0 prime divisor**
 » 6 months ago, # |   +1 Can someone tell me the recursive DP solution to the problem E??
•  » » 6 months ago, # ^ |   +3
 » 6 months ago, # |   0 Can E be solved with any shortest path algo? I tried to solve it with priority_queue but it doesn't pass 3 tests.
 » 6 months ago, # |   +16 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
•  » » 6 months ago, # ^ |   +5 Can we improve this solution to O(n)??
•  » » » 6 months ago, # ^ |   +3 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
 » 6 months ago, # |   0 I didn't get E can any one explain it to me and it's solution ?
•  » » 6 months ago, # ^ | ← Rev. 2 →   0 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 enoughHere's my solution Edit: updated solution so it has English friendly variables
•  » » » 6 months ago, # ^ |   0 Thank you now I got it ! in the begin i was confused by the input format.
•  » » » 6 months ago, # ^ | ← Rev. 2 →   +1 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.
•  » » » 5 months ago, # ^ |   0 Great Solution!! But one thing I couldn't understand, why are you running the recursion till (key==M)? Why not terminate it every time (treasures == total) and then return the current cost.
•  » » » » 5 months ago, # ^ |   0 My idea was: run until I've checked the last key. When I reach that I then check if all chests were opened. If not, then the solution is not valid, so I return INF.I didn't really understood you suggestion. Is it to remove the if (key==M) and leave just the if (treasures == total) ?
•  » » » » » 5 months ago, # ^ |   0 Yes, I just realized that we can do it both ways. Its just the matter of approach you take. Thank you !!
 » 6 months ago, # |   0 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
•  » » 6 months ago, # ^ | ← Rev. 3 →   +1 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 1In 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
•  » » » 6 months ago, # ^ |   +3 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.
 » 6 months ago, # |   +3
•  » » 5 months ago, # ^ |   0 Where can I find this kind of editorial??
 » 6 months ago, # |   0 Can anyone explain what is wrong with my code? It is problem D. https://pastebin.com/tKRWLxif
 » 5 months ago, # |   0 Why my code on problem D got TLE. I think the complexity is just $O(sqrt(n))$. Why I got TLE? My code
•  » » 5 months ago, # ^ |   0 It's all my fault, i set int*int to compare with ll and it caused me 1 hours :'(
 » 4 months ago, # |   0 Could someone explain what these are about?Seem like special-treated solutions for testing purposes only (kind of cheat codes).https://atcoder.jp/contests/abc142/submissions/7825341https://atcoder.jp/contests/abc142/submissions/7826607
 » 2 months ago, # |   0 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 2output: 5 1 5 2 6 3answer: 3 1 2 3