chokudai's blog

By chokudai, history, 7 weeks 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

»
7 weeks ago, # |
  Vote: I like it +62 Vote: I do not like it

»
7 weeks 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).

»
7 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

Good contest! :D

»
7 weeks 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!

  • »
    »
    7 weeks 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.

    • »
      »
      »
      7 weeks 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

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

          I believe you found smallest cycle right?

          • »
            »
            »
            »
            »
            »
            7 weeks ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            True

          • »
            »
            »
            »
            »
            »
            7 weeks 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.

            • »
              »
              »
              »
              »
              »
              »
              7 weeks 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.

              • »
                »
                »
                »
                »
                »
                »
                »
                7 weeks ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

                The simple cycle must be one of the smallest cycles.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  7 weeks ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  I don't think that is necessary.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  7 weeks ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  But how to find the simple sycle

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

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

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  7 weeks 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.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  7 weeks 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 ?

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  7 weeks 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.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  5 weeks ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  rohit_goyal thanks dude

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

    could you explain problem c ?

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

Editorial ? how to solve E?

  • »
    »
    7 weeks 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.

    • »
      »
      »
      7 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      is it bit-masking or something Greedy will work

    • »
      »
      »
      7 weeks 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 ?

      • »
        »
        »
        »
        7 weeks 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.

        • »
          »
          »
          »
          »
          7 weeks 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

        • »
          »
          »
          »
          »
          7 weeks 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
          • »
            »
            »
            »
            »
            »
            7 weeks ago, # ^ |
            Rev. 5   Vote: I like it 0 Vote: I do not like it

            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/7776682

            Thanks!

          • »
            »
            »
            »
            »
            »
            7 weeks ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Hey, I tried the same way but messed up in the base conditions . Can you explain the base condition at top ?

            • »
              »
              »
              »
              »
              »
              »
              7 weeks ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              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.

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

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

    • »
      »
      »
      7 weeks 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)];
      
  • »
    »
    7 weeks 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 .

  • »
    »
    7 weeks 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

»
7 weeks 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.

»
7 weeks 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...

»
7 weeks ago, # |
  Vote: I like it +17 Vote: I do not like it

Missing Geothermal's editorials :|

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

How to Solve D?

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

    Count the number of distinct common prime factors + 1

  • »
    »
    7 weeks 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

    • »
      »
      »
      7 weeks 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⁶

      • »
        »
        »
        »
        7 weeks 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

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

          what if the number is prime? greater then 1e6

          • »
            »
            »
            »
            »
            »
            7 weeks 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

          • »
            »
            »
            »
            »
            »
            7 weeks 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

            • »
              »
              »
              »
              »
              »
              »
              7 weeks 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.

              • »
                »
                »
                »
                »
                »
                »
                »
                7 weeks ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

                Wow I like your logic, you reduced the time complexity by a great extend

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Can you explain what is wrong with my code? It is problem D. https://pastebin.com/tKRWLxif

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

how to solve D??

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      7 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      is there any proof for this??

      • »
        »
        »
        »
        7 weeks 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

    • »
      »
      »
      7 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      prime divisor**

»
7 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

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

»
7 weeks 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.

»
7 weeks 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

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

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

    • »
      »
      »
      7 weeks 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

»
7 weeks 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 ?

  • »
    »
    7 weeks 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

    • »
      »
      »
      7 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      7 weeks ago, # ^ |
      Rev. 2   Vote: I like it +1 Vote: I do not like it

      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 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

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

          Yes, I just realized that we can do it both ways. Its just the matter of approach you take. Thank you !!

»
7 weeks 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

  • »
    »
    7 weeks 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

    • »
      »
      »
      7 weeks 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.

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

    Where can I find this kind of editorial??

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone explain what is wrong with my code? It is problem D. https://pastebin.com/tKRWLxif

»
4 weeks 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 weeks 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 :'(