chokudai's blog

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

»
2 months 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.

»
2 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Bump. Contest Starting!

»
2 months 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?

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    How to pass all cases in D???

    • »
      »
      »
      2 months 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

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Dynamic Programming !!

    • »
      »
      »
      2 months 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

      • »
        »
        »
        »
        2 months 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

        • »
          »
          »
          »
          »
          2 months 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 ?

  • »
    »
    2 months 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.

  • »
    »
    2 months 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)

  • »
    »
    2 months 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)

  • »
    »
    2 months 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.

»
2 months 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.

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

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

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      why ?

      • »
        »
        »
        »
        2 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Go check out AnandOza stream.

      • »
        »
        »
        »
        2 months 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

      • »
        »
        »
        »
        2 months 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.

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Could you please explain?

      • »
        »
        »
        »
        2 months 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].

      • »
        »
        »
        »
        2 months 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

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      What is proof of correctness for this greedy approach ?

      • »
        »
        »
        »
        2 months 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.

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thank you so much for helping.

    • »
      »
      »
      2 months 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 ?

      • »
        »
        »
        »
        2 months 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

        • »
          »
          »
          »
          »
          2 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          1<=Ai,Bi<=1e9

          • »
            »
            »
            »
            »
            »
            2 months 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]

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

          How are you able to find such corner test cases ? I was scratching my head for 30 minutes straight but couldn't figure out why it was getting wrong verdict. But your test case helped me understand where my code was failing. Thanks a lot for that :)

      • »
        »
        »
        »
        2 months 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.

    • »
      »
      »
      2 months 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]

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

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

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

  • »
    »
    2 months 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.

  • »
    »
    2 months 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.

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

    Try this input:

    2
    1 8
    7 1
    

    If you sort on the basis of (a+b) then (1,8) will come before (7,1).You will gain total (1+8)-(-1)=10 votes.

    If you sort on the basis of (2*a+b) then (7,1) come before (1,8). And you gain total (7+1)-(-7)=15 votes.

»
2 months 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

  • »
    »
    2 months 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.

  • »
    »
    2 months 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]

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

    try this input:

    2
    1 8
    7 1
    
»
2 months 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

  • »
    »
    2 months 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.

    • »
      »
      »
      2 months 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

    • »
      »
      »
      2 months 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
  • »
    »
    2 months 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.

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

How to solve Problem E ?

Thanks in advance!

  • »
    »
    2 months 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).

    • »
      »
      »
      2 months 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.

      • »
        »
        »
        »
        2 months 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.

  • »
    »
    2 months 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

  • »
    »
    2 months 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

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

is there any greedy solution for D?

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

    Yes

    Hint
  • »
    »
    2 months 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.

  • »
    »
    2 months 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";
    
»
2 months 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

  • »
    »
    2 months 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;
        }
    };
    
    • »
      »
      »
      2 months 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);`
          });
      
»
2 months ago, # |
  Vote: I like it +9 Vote: I do not like it

how to solve F?

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

how to solve Problem F? T_T

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Is problem E related to segment tree or DSU?

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone give a test case for problem D for which there is possibility of RTE. I am using long (IN JAVA) everywhere so overflow is not an issue i guess .

»
2 months 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.

»
2 months 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

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

    This is most likely not a python issue.

    • »
      »
      »
      2 months 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

      • »
        »
        »
        »
        2 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Why not switch to cpp for dfs problems?

        • »
          »
          »
          »
          »
          2 months 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

      • »
        »
        »
        »
        2 months 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

        • »
          »
          »
          »
          »
          2 months 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

  • »
    »
    2 months 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

»
2 months 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?

  • »
    »
    2 months 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.

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Me too;

  • »
    »
    2 months 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.

»
2 months 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.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve E? Thanks in advance!

  • »
    »
    2 months 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.

  • »
    »
    2 months 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!

»
2 months 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;
}
»
2 months 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

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    try this:

    1 5
    4 1
    3 0
    
    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Output is 2. It should be 1. I'll check. Thank you.

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      my code gives 1 for the above test case. I used something like Stark_3000 { I took suffix sum for first & prefix sum for second, and when v.[i].first > v[i-1].second, ans is counter j }, still getting WA for 'large.txt' test cases. thank you.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Approach for Problem D

The most difficult part of the algorithm is the fluctuating value of Aoki's votes. So, we'll try to convert it into a problem where the votes of one voter is fixed.

Aoki's initial votes is $$$\sum b_i$$$

Now, say, we add just the $$$i-th$$$ town to our list. This would decrease the votes of Aoki by $$$b_i$$$ and increase the votes for Takahashi by $$$a_i + b_i$$$. However, since in an election, if you grant equal votes to both the candidates, the situation does not change. So, we'll provide $$$b_i$$$ votes to both Aoki and Takahashi in order to balance things out.

So, the net gain for Aoki is 0, while net gain for Takahashi is $$$a_i + b_i + b_i$$$. Hence, each town contributes a factor of $$$2b[i] + a[i]$$$ to the winner while keeping the points of the loser fixed.

Hence, just create an array consisting of $$$2b[i] + a[i]$$$, sort it, and greedily take largest values until you exceed the total of $$$\sum b_i$$$ (the initial and final points of the loser).

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    2 months 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

  • »
    »
    2 months 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

    • »
      »
      »
      2 months 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?

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

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

        • »
          »
          »
          »
          »
          2 months 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.

          • »
            »
            »
            »
            »
            »
            2 months 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!)$$$.

            • »
              »
              »
              »
              »
              »
              »
              2 months 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.

»
2 months 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;
}

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Don't sort with a[i].x+a[i].y. Change it to a[i].s = 2*a[i].x+a[i].y.

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    testcase - 1 4 3 1 2 0 answer is only 3,1

»
2 months 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 .

»
2 months 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

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Check this case — 2 !a a.

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

    The problem is that you assume that strings without ! will appear first.

    Failed test case. 2 !a a

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

I tried to solve problem D via priority queue, but got WA on 9 test cases, however, my normal vector greedy solution got AC.

Using priority-queue(WA): https://atcoder.jp/contests/abc187/submissions/19163897

AC: https://atcoder.jp/contests/abc187/submissions/19170201

Can anyone give me a tough side case for which it might fail?

»
2 months 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.

»
2 months 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?

  • »
    »
    2 months 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.

  • »
    »
    2 months 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.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

apply DP in D and got 12 TLE

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

I didn't understand why Sample Output 2 in Problem F is 1. I think it supposed to be 0, because Sample Input 2 is already complete.

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I got it, the question is answer the minimum possible number of components, I misunderstood with the count of edges need to be removed...

»
2 months ago, # |
  Vote: I like it +9 Vote: I do not like it

My solutions + explanations can be found here :)

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    2 months 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

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can we solve D using DP?

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I'm stuck with Problem-D. My Code

  • »
    »
    2 months 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

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

for problem B, isn't the expression |x2−x1|≥|y2−y1| same as (y2-y1 >= x1-x2 && y2-y1 <= x2-x1) ?? Seems like it's not correct. How are they different ?? Thank you !

»
2 months 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

»
2 months 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.

  • »
    »
    2 months 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?)

    • »
      »
      »
      2 months 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. :)

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

How to solve B, in time complexity of NlogN ?