chokudai's blog

By chokudai, history, 3 years ago, In English

We will hold AtCoder Beginner Contest 187.

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

We are looking forward to your participation!

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

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

For anyone interested, I'll be doing a post-contest stream on Twitch.

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

Bump. Contest Starting!

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

How to solve F? Is the answer minimum number of clique in graph?

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

    How to pass all cases in D???

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

      For D with every speech total votes gained will 2 * a + b. So just sort according to that value and keep taking maximum. Also take care of overflow. I got one penalty because of that.

      Code

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

    Dynamic Programming !!

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

      If you mean dp on subset I won't work since 3^18 is too big unless I am missing something

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

        O(3^n) is OK, because the constant is very low, my solution passed in 0.5s/6s

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

          While up-solving the problem , i also wrote same $$$O(3^n)$$$ solution . In my local computer whenever i run the case 18 0 it takes more than 2 seconds whereas on online judges it's only taking around 0.5s. What could be the reason for that ?

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

    I solved it by bitmask DP with O(3^n). But I'm not sure whether it's the best solution.

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

    My approach is calculating the size of the biggest sub-graph which every two vertice in it is not connected. However,I keep getting WA for one test case(that is really disappointing)

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

    The key idea is that if any two nodes are not connected by an edge in the given graph then they cannot be in the same connected component as they will not form a clique. Now the problem is equivalent to finding chromatic number of the compliment graph which can be found here and can be done in O(n * 2^n)

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

    I use Recursion and Backtracking, and add a optimization that stop recurse when current result is worse than previous answer.

    For more details: ac code — 7ms.

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

How to solve D. I tried to sort on the basis of a[i]+b[i] value but kept getting WA.

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

    you need to sort by 2*a[i]+b[i]

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

      why ?

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

        Go check out AnandOza stream.

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

        First assume that Takahashi is not giving any speech . then Aoki will get all of his own voters say "ans" . Now sort array of 2*A+B and subtract from ans until ans>=0 since place where Takahashi will give a speech , Aoki will lose his votes as well as Takahashi will gain his and Aoki votes . Number of times subtracted will be the answer .

        solution

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

        Let x be the answer i.e x is the minimum number of towns in which Takahashi needs to deliver a speech..Let (a[1],b[1]),(a[2],b[2]) ...(a[x],b[x]) be the vote pairs in these x towns.Also,Let A be the total number of votes Aoki would have received if Takahashi would not have given speech in any of the towns..Now under the given secnario,number of votes received by Takahashi is summation over j from 1 to x P = (a[j] + b[j])..and number of votes received by Aoki is Q = A — ((summation over j from 1 to x)a[j])..Now P has to be > Q.. Just transposing the equation we get ((summation over j from 1 to x)(2*a[j] + b[j])) > A...So if we sort the pairs according to decreasing order of (2 * a + b) the prefix of minimum length would simply be the answer.

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

      Could you please explain?

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

        because when we choose a town Aoki loses a[i] votes and we gain a[i]+b[i] votes. So the net change in 2*a[i]+b[i].

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

        With every speech

        1. Aoki will lose a votes
        2. Takahashi will gain a + b votes.

        So total votes gained = a + b - (-a) = 2 * a + b

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

      What is proof of correctness for this greedy approach ?

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

        Cost of speech for each town is the same. As the cost is the same, choose greedily by gain as mentioned in previous comments.

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

      Thank you so much for helping.

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

      But why ?Why a[i]+b[i] is not working and why multiply by 2 working ?

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

        In this case:

        1 4
        3 1
        2 0
        

        The correct answer is 1.(By giving speech on the 2nd city)

        But yours will output 2

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

          1<=Ai,Bi<=1e9

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

            I think if the last '0' is changed to one, it is still is a good testcase which serves the purpose of highlighting that 2*a[i]+b[i] is correct rather than a[i]+b[i]

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

        With a speech the one get a[i]+b[i] votes. Without a speech the other gets a[i] vots. So, the difference of both cases is 2*a[i]+b[i], so giving a speech at city i make exactly that difference.

        Of course we need to give speech in cities in order of these difference, biggest first.

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

      Proof: let suma = $$$a_1 + ... + a_n$$$, sumb = $$$b_1 + ... + b_n$$$. Let's imagine we will make a speech, which affect $$$A$$$, and $$$B$$$ people.

      So, $$$A + B$$$ people will be vote for us, and $$$suma - A$$$ against us

      We need $$$A + B$$$ > $$$suma - A$$$

      $$$2A + B > suma$$$

      So, we need sort by 2*a[i]+b[i]

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

    you need to sort it based on 2*a[i] + b[i]

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

    sort according to 2*a[i] + b[i]

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

    Sort according to maximum gain of votes for Takahashi. The gain while taking a city is $$$2a[i] + b[i]$$$. Here $$$a[i]+b[i]$$$ is vote added to Takahashi and $$$a[i]$$$ is vote taken from Aoki.

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

    You need to sort on the net increase in your votes, now realize that a decrease in votes for aoki is also indirectly an increase in votes for Takahashi. Thus the net increase in takahashi's votes is the total votes for that city + the extra decrease in votes for aoki, i.e. $$$2 \cdot a[i] + b[i]$$$. Now just sort on those and you're golden.

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

Please anyone point out the mistake in my code or logic? Task D https://atcoder.jp/contests/abc187/submissions/19154830

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

    Maybe you should sort in basis of 2 * vp[i].ff + vp[i].ss.

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

    I guess sorting is wrong which leads to WA in some test cases, try it by sorting with 2*a[i] + b[i]

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

Can anyone tell me how to approach the problem E? https://atcoder.jp/contests/abc187/tasks/abc187_e

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

    The idea is that of segment tree instead of adding all the numbers just add to b[i] or a[i](In the second cases you should add the number to the root and subtract from a[i] b[i]) Now run a lazy propogation like operation(adding the value on the node to its childs) using dfs.

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

      Segment tree is overkilled here. Just using simple dfs as the comment below! My ugly code: https://ideone.com/PAEUDp

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

      Yes, we basically Find the case according to the distance of a and b from the root, and since a and b are connected by an edge we see if a is near root then we add to root subtract from b otherwise we simply add to a. And then we do DFS from the considered root in my case 1 to find all the final answers.

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

    Imagine a rooted tree with the root being any vertex (say, vertex 1). Now, consider a query $$$q_{i}$$$ such that $$$t_{i}$$$ = 1 and $$$e_{i}$$$ = ($$$u$$$, $$$v$$$). If $$$u$$$ is the parent of $$$v$$$ in the rooted tree, it means we can visit every vertex apart from vertices lying in the subtree of $$$v$$$. Otherwise, we can visit only the vertices lying the subtree of $$$u$$$. If $$$t_{i}$$$ = 2, the situation is the same with the vertices swapped. Rest is the implementation part of how to compute the overall values in $$$O(n+m)$$$ which can be done using a simple DFS.

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

How to solve Problem E ?

Thanks in advance!

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

    for processing queries assume 1 is root of tree if (u,v) is a edge and u need to update u. There are two cases if u is parent of v (in this case update root of tree with x and v with -x) and if v is parent of u (simply update u with x).

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

      I did the same thing, except when v is the parent of u, I updated the node below v that is the parent of u. My logic being:

      say the tree is like:

      v -> p -> q ->u -> r (rotate by 90deg)

      now if we need to update ci for all nodes reachable from u but not doing through v, the nodes are: p, q, u, and r. (that's what I did, and got WA) but if we just update u, only u and r are updated in end(that's what u did and got AC, I changed my code to this and got AC too) but I don't understand why am I wrong?

      Can you please point out the mistake here

      Edit: actually got it, it's because u and v are connected by 1 edge.

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

        first of all your test case is invalid as u and v will always be connected by an edge. Read the Question. I also thought like that and kept getting TLE until i figured this out.

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

    I made a euler tour array and just updated the suitable ranges with segment tree

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

    Select any node with 1 edge as root. Then use bfs and store level wrt root for every node. Now, idea is to use to prefix sums. For every query, you have to add cost of one side of a vertex. Now, parse the input as per the type and find which node's value gets incremented. Lets call this node "node1". Compare the two nodes now and if node1 is at a higher level, add cost to root and subtract it from node2, otherwise just add cost to node1. Now run dfs and for every node, cost[node] = cost[node] + cost[parent]. I wasnt able to implement it completely during contest tho.

    Submission

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

is there any greedy solution for D?

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

    Yes

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

    When you pick a town, you get all the A votes from it, and all the B votes from it, additionally you deprive the other from all of A votes he would otherwise get. So the value of picking a town is A+B+A = 2*A + B, sort the towns by it and keep picking until you have enough votes.

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

    Yes, Let us assume initially she didn't go to any town. So Aoki score is sum of all A[i], let us denote it by s and Takahashi score is 0. So initial difference is s. Now consider if she chooses any city i to make a speech, what will be the new difference ?

    Spoiler

    So, we want to choose cities in such a way, that we reduce this difference by selecting minimum cities. So, let's make a vector v, such that v[i] = 2*a[i] + b[i] , and sort it. Start by selecting the largest, second largest and so on, until this difference reduces to less than 0.

    Pseudo Code

    s = 0;
    for i=0 to n-1
    	s+=a[i];
    	v.pb(a[i]*2 + b[i]);
    sort(v.rbegin(),v.rend());
    p =0;
    ans = 0;
    for i=0 to n-1
    	p = p + v[i];
    	if(p>s)
    		ans = i+1;
    		break;
    cout<<ans<<"\n";
    
»
3 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

How to solve D problem? I sort the pairs according to this comparator always choose the maximum pair sum and if two pair sum is equal then choose the highest first element among these pair.

(a.first+a.second)==(b.first+b.second))?(a.first>b.first):(a.first+a.second)>(b.first+b.second)

Then greedily choose the elements if it's strictly greater or not.What am I missing? my sub

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    struct cmp {
        bool operator() (const pair<int,int> &a, const pair<int,int> &b) 
        const {
            return a.fr*2+a.sc==b.fr*2+b.sc?a.fr>b.fr:a.fr*2+a.sc>b.fr*2+b.sc;
        }
    };
    
    • »
      »
      »
      3 years ago, # ^ |
      Rev. 2   Vote: I like it +1 Vote: I do not like it

      can also do like this

      sort(all(vo), [](pii a, pii b){`
              return make_pair(2LL*a.first + a.second, a.first) < make_pair(2LL*b.first + b.second, b.first);`
          });
      
»
3 years ago, # |
  Vote: I like it +9 Vote: I do not like it

how to solve F?

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

how to solve Problem F? T_T

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

Is problem E related to segment tree or DSU?

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

Any hints on D? Tried solving by taking maximum (a[i]+b[i]) but it gave WA.

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

It is so painful to solve the problem (E) but fail to get AC because it is python and you get three TLE

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

    This is most likely not a python issue.

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

      I'm pretty sure it is python issue

      Solution is just a couple of dfss, O(n), there is not much to to optimize

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

        Why not switch to cpp for dfs problems?

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

          I hoped for the best
          Hope is a dangerous thing, meh
          Had the constraints were smaller or there was only one dfs it would've worked. That's what I didn't think about

          Though it is possible to pass in python, a good reason to examine the bottlenecks

          Truth be told though, I wouldn't have debugged it in time in cpp since I wasted too much time thinking about LCA missing the fact that both vertices always belong to the same edge

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

        I once tried to write DFS in python and also got TLE. Then I checked others guys solutions and found that they launched dfs in particular thread and it worked. I used this code as an example: code

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

          I know this trick and use it. Though it has nothing to do with TLE, it is needed to bypass python's stack limitations

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

    Funny thing btw. It TLEd in pypy, but passed in cpython. Too bad I didn't think about it during the contest

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

I was able to solve $$$a,b,d,e$$$ but couldn't figure out what the statement of $$$c$$$ mean. Statement could be better. By the way what does problem $$$C$$$ meant?

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

    They asked if the query string is in the list, and also the query string with a pre "!" before it.

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

    Me too;

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

    Given N strings:S1,S2...SN.Among them,there are two types of strings:

    1."!***..."

    2."***..."

    where * stands for a lowercase latin letter.

    You are asked to find a string consisting of only lowercase latin letters that both the string itself,and the string obtained by adding a "!" before it(we can get "!abcde" from "abcde") are in the strings S1...SN.

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

The first thing I want to say is the problems are excellent! Some ABCs' problems are really easy and don't need to think. (I mean, A~D) But this one is different, I really like D.

By the way, how to solve F? I think about it for a long time but just can't fix it.

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

How to solve E? Thanks in advance!

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

    For solving E you can first think of a simpler case. If your have an array A and you are given Q queries where in you have to add x value to range [L, R] then you can build another array P and can perform operations like P[L] += x and P[R+1] -= x. Then you can do prefix sum on this array which will have the same effect as required by the question.
    Now you can think of same with this tree. For query of type 1 simply add x to root and subtract x from c[b]. For query of type 2 add x to c[b]. Then perform a dfs and simply push this accumulated value of c in all the children and do it like prefix sum.

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

    Root the tree in the node $$$1$$$. For each query of type $$$1$$$; I denote $$$x$$$ like $$$a_{e_i}$$$ and $$$y$$$ like $$$b_{e_i}$$$. Then there are two possibles cases:

    1. $$$x$$$ is parent of $$$y$$$
    2. $$$y$$$ is parent of $$$y$$$

    For solve the first case, note that I can reach to all vertices except the vertices of the $$$y$$$'s subtree

    In the second case, I only can reach to the vertices of the $$$x$$$'s subtree.

    For each query of type $$$2$$$ you can use the same approach.

    Now, you can use Euler Tour Technique and solve the problem easily. You can learn it in the next link: USACO Guide :)

    My submission for this problem: Submission #19155947. I hope that this is helpful!

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

Hi, guys. I defined comparator on problem D, but the first code keep giving me runtime error, I use $$$\leq$$$ in the return line.

bool cmp(pair<ll, ll> &a, pair<ll, ll> &b)
{
    ll first = a.second + 2 * a.first;
    ll second = b.second + 2 * b.first;
 
    return first <= second;
}

Then I try to use $$$<$$$(the code below), and then it magically passed. (All other parts of code are the same).

Anyone has a clue why $$$\leq$$$ get a runtime error, but $$$<$$$ gives AC?

bool cmp(pair<ll, ll> &a, pair<ll, ll> &b)
{
    ll first = a.second + 2 * a.first;
    ll second = b.second + 2 * b.first;
 
    return first < second;
}
»
3 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

For D, I sorted in decreasing order on basis of {aoki[i]+takahashi[i] , aoki[i]} and then took prefix sum for first and suffix sum for second. So, when i get prefix[i] > suffix[i+1], ans is (i+1). The logic seems to be correct but I got WA. Can someone point out the fault in this method? Thank you. My Submission

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

How to solve F in less than $$$3^{n}$$$?

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

    We're trying to find the minimum clique cover of a graph. It's easy to see that an equivalent problem is finding the chromatic number of the complement of a graph. A bitmask DP / inclusion-exclusion algorithm exists for finding the chromatic number of a general graph in $$$O(n\cdot 2^n)$$$. More details can be found here

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

    I just use recursion and backtracking, and a little optimization.

    Assume we are processing the $$$i$$$-th vertex, and the first $$$i-1$$$ vertexs form a set of cliques. Note the set as $$$Cliques$$$.

    • if $$$i = n + 1$$$, then $$$ans = \min(ans, |Cliques|)$$$.
    • for each $$$clique$$$ in $$$|Cliques|$$$, if all vertexs in $$$clique$$$ has an edge to the $$$i$$$-th vertex, we could add $$$i$$$-th vertex to $$$clique$$$.
    • the $$$i$$$-th vertex can form a new clique itself.

    so far, the solution is not good enough to get an AC.

    Then I find that if $$$ ans \le |Cliques| $$$ ,it just no need to recurse any more, just cut it.

    After adding this optimization, the solution is good enough to get an AC and my submission only execs about 7ms.

    Submission #19164964

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

      I finally did the same. But I have doubt that it is weak test data that makes it so fast.

      What is the runtime complexity of our solution?

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

        qqwrwwv or spookywooky did you found the complexity of the solution ?

        Isn't the time complexity greater than $$$O(n!)$$$ in worst case ?

        Suppose we can divide vertices (1,2,3,4,5,6) only like (1,2),(3,4,5),(6) i.e contiguously and not like (1,5),(2,3,4,5,6) then complexity would have been $$$O(2^n*n)$$$ by using binomial theorem. But that's not necessarily true because vertices can form group like (1,5),(2,3,4,5,6) and thus we need to consider all arrangements of $$$n$$$ vertices before partitioning and there are $$$O(n!)$$$ arrangements and thus in worst case it can be around $$$O(n!*2^n*n)$$$.

        Not sure , but i think if such fast solution existed then they would mentioned in editorial because above solution is just brute force and writers must have thought about it.

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

          I think actually it is better than brute force.

          See two "extremes". If there are a lot of edges, then we most likely can form big components, leading quickly to good solutions.

          On the other hand, if we got not much edges there are not much components we can create, so the size of the brute-force tree is fairly small.

          Then, consider a single vertex. If it is completly disconnected (no edge) then the complexity is the same as that vertex would not exist. Else that vertex can be put into a component with at least one other vertex. This makes the complexity based on N in fact beeing based on n/2. Which makes a huge difference.

          In spite of not beeing able to tell how the complexity is calculated I am fairly sure that in this case it is better than the O(3^n) of the bitmask solution.

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

            I think that answer is made up by a lot of cliques with size 2 will be a bad case. So I write a generator to generate graph contains no clique of size 3 as subgraph. And it turn out to be a bad case I think.

            On my PC, it still execs only a few ms when $$$n \le 18$$$ , and it will cost seconds when $$$n \le 25$$$, and for $$$n \ge 26$$$ I have no patience to wait it to complete running.

            I still can not figure out what the time complexity exactly is, but I guess it will be something between $$$O(2^n)$$$ and $$$O(n!)$$$.

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

              As I implemented it, I do basically a dfs construction all combinations of cliques possible.

              But, I do create biggest possible cliques first, and I stop dfs if ans cannot get better.

              So, the solution where biggest cliques are created is near to the optimal solution. There can be better ones.

              Consider a graph where cliques possible of size [3,3,1,1,1,1], there could be a better solution with cliques of size [2,2,2,2,2]

              In this case we fairly quick find 6 as ans, and then traverse the searchtree not deeper than level 6.

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

On problem D

I want to ask

Why is my greedy strategy wrong

Can anyone provide a set of hack samples

struct node {
	ll x,y,s;
} a[maxn];
bool cmp(node x,node y) {
	return x.s>y.s;
}
int n;
int main() {
	cin>>n;
	ll num = 0;
	for(int i=1 ; i<=n ; i++) {
		cin>>a[i].x>>a[i].y;
		a[i].s=a[i].x+a[i].y;
		num+=a[i].x;
	}
	sort(a+1,a+1+n,cmp);
	ll s=0;
	for(int i=1 ; i<=n ; i++) {
		s+=a[i].s;
		num-=a[i].x;
		if(s>num) {
			cout<<i;
			break;
		}
	}
	return 0;
}

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

https://atcoder.jp/contests/abc187/submissions/19163293

Plz some java enthusiast find error in this submission for Problem D in java..i used long also , just getting RTE on 7 tests and all other AC .

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

What is the approach for solving C, I got 3 TC WA(so obviously WA), is there any corner case I'm missing, link to the submission: Link

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

Video Editorial, and also screencast.

You can also refer to the Source code and simple explanation.

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

My submission got runtime error on 3 tests for Problem D. Can someone help me with the reason for the Runtime error?

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

    You have the same problem as me. you can look the previous post.

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

    Your comparator must return false when values are equal. I changed that it got AC.

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

My solutions + explanations can be found here :)

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

Is there anyone who used segment tree in problem E??

  • »
    »
    3 years ago, # ^ |
    Rev. 3   Vote: I like it -7 Vote: I do not like it

    I think that intended solution was flattening tree with segment tree

    upd: code

    upd 2: I think that solution by ScarletS is much better and easier, though it uses the similar idea, but segment tree solution may be helpful when we need to answer queries online

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

I'm stuck with Problem-D. My Code

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

    In your code, you sort vt in .first(aoki) order, this is the mistake.

    If the testcase is like this:


    3 1 100 10 1 10 1

    Your code will output 2(1 in fact)

    The right method is to sort it in 2*Atoi+Takahashi order.

    You can see the detail here

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

If anybody is interested in watching a screencast of this contest you can have a lot at my YouTube video where I am solving the problems A to E. Link: ABC 187 Screencast

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

In F — Close Group Editorial, it is written that One can determine if each induced subgraph is complete in O ( 2^N*N^2 ) time for all S. Why so? I mean for any subgraph all I need to do is check if all there is an edge to other vertex or not. It will take O(N^2) only. Thank you for the help.

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

    It is supposed to mean that the total amount of time needed to check the completeness for all subgraph is $$$O(2^N N^2)$$$, since it needs $$$O(n^2)$$$ time for each of $$$O(2^n)$$$ graphs. (Is the original statement confusing?)

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

      No. The editorials are just fine. I missed the context it was trying to build in 2-3 preceded lines & wrote the comment in a hurry. Thank you for replying. :)

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

How to solve B, in time complexity of NlogN ?

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

    Rotate the plane by 45 degrees. For each point, we want to count the number of points with greater x- and y- coordinates. If we inspect them in the increasing order of x-coordinates, we can manage how many points are there on each y-coordinates, and find the sum of them within specific range with BIT.