When submitting a solution in C++, please select either C++14 (GCC 6-32) or C++17 (GCC 7-32) as your compiler. ×

chokudai's blog

By chokudai, history, 4 years ago, In English

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!

  • Vote: I like it
  • +38
  • Vote: I do not like it

| Write comment?
»
4 years ago, # |
  Vote: I like it +62 Vote: I do not like it

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
4 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Good contest! :D

»
4 years ago, # |
  Vote: I like it +2 Vote: I do not like it

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

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      4 years ago, # ^ |
      Rev. 2   Vote: I like it +3 Vote: I do not like it

      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

      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it +1 Vote: I do not like it
        • »
          »
          »
          »
          »
          4 years ago, # ^ |
            Vote: I like it +3 Vote: I do not like it

          I believe you found smallest cycle right?

          • »
            »
            »
            »
            »
            »
            4 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            True

          • »
            »
            »
            »
            »
            »
            4 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

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

            • »
              »
              »
              »
              »
              »
              »
              4 years ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              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.

              • »
                »
                »
                »
                »
                »
                »
                »
                4 years ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

                The simple cycle must be one of the smallest cycles.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  4 years ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  I don't think that is necessary.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  4 years ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  But how to find the simple sycle

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  4 years ago, # ^ |
                    Vote: I like it +3 Vote: I do not like it

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

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  4 years ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  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.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  4 years ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  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 ?

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  4 years ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  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.

»
4 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Editorial ? how to solve E?

  • »
    »
    4 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    $$$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.

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      is it bit-masking or something Greedy will work

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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 ?

      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it +9 Vote: I do not like it

        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.

        • »
          »
          »
          »
          »
          4 years ago, # ^ |
          Rev. 14   Vote: I like it 0 Vote: I do not like it

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


          vector <long long> 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

        • »
          »
          »
          »
          »
          4 years ago, # ^ |
          Rev. 4   Vote: I like it +5 Vote: I do not like it

          Why a top-down would be hard to implement?

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

          Spoiler
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        Spoiler

        You can also precompute a mask for each c[i].

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      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<m;i++){
      		for(j=0;j<pow(2,n);j++){
      			dp[i+1][j] = dp[i][j-(j&barr[i])] + arr[i];//include
      			dp[i+1][j] = min(dp[i+1][j],dp[i][j]);//exclude
      		}
      	}
      	if(dp[m][(power(2,n)-1LL)]==INT_MAX)
      	cout<<-1;
      	else
      	cout<<dp[m][(power(2,n)-1LL)];
      
  • »
    »
    4 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    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 .

  • »
    »
    4 years ago, # ^ |
      Vote: I like it -13 Vote: I do not like it

    1D dp is enough.

    No need of 2D dp.

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

»
4 years ago, # |
  Vote: I like it +8 Vote: I do not like it

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.

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can somebody explain F? I got all testcases accepted except 2 of them...

»
4 years ago, # |
  Vote: I like it +17 Vote: I do not like it

Missing Geothermal's editorials :|

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to Solve D?

  • »
    »
    4 years ago, # ^ |
    Rev. 2   Vote: I like it +5 Vote: I do not like it

    Count the number of distinct common prime factors + 1

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    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

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

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

        • »
          »
          »
          »
          »
          4 years ago, # ^ |
            Vote: I like it +5 Vote: I do not like it

          what if the number is prime? greater then 1e6

          • »
            »
            »
            »
            »
            »
            4 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

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

          • »
            »
            »
            »
            »
            »
            4 years ago, # ^ |
              Vote: I like it +1 Vote: I do not like it

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

            • »
              »
              »
              »
              »
              »
              »
              4 years ago, # ^ |
                Vote: I like it +1 Vote: I do not like it

              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.

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

how to solve D??

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      is there any proof for this??

      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      prime divisor**

»
4 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
4 years ago, # |
  Vote: I like it +16 Vote: I do not like it

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

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

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

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      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

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    4 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    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

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    4 years ago, # ^ |
    Rev. 3   Vote: I like it +1 Vote: I do not like it

    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

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      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.

»
4 years ago, # |
  Vote: I like it +3 Vote: I do not like it
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Where can I find this kind of editorial??

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Why my code on problem D got TLE. I think the complexity is just $$$O(sqrt(n))$$$. Why I got TLE? My code

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It's all my fault, i set int*int to compare with ll and it caused me 1 hours :'(

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
15 months ago, # |
Rev. 2   Vote: I like it -8 Vote: I do not like it

In problem D : Link

What is the wrong with this code : Link ?

  • »
    »
    15 months ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    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