chokudai's blog

By chokudai, history, 5 weeks ago, In English,

We will hold AtCoder Beginner Contest 173.

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

We are looking forward to your participation!

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

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

Participate, we must.

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

Hope that C is not the killer this time :p

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

Starts in 15 mins :)

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

See you all on the scoreboard!

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

    Video editorial and screencast are being uploaded to my youtube channel now. There are lots of nice solutions described in the comments here (and the atcoder editorial is usually quite good), but if you would like to see stuff explained more visually, feel free to look out for that :)

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

      cant find atcoder 173 in ur channel... is it in the process of being uploaded as of now?

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

        Yeah it is being processed by Youtube right now.

        I hate to say this because it sounds so cliche, but there is a bell icon you can click if you subscribe if you want to get an email when YouTube decides to finish processing it.

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

          subscribed !! upload more and more tricks, tutorials and solutions of cf and atcoder rounds

          i guess u r the only cp channel in youtube with the clearest english accent!

          keep up the good work

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

        Looks like Youtube is finally done! Here’s it is :)

        The video quality will improve as it processes. Usually it is only 360p or something for a bit, even though it is recorded in 1080p.

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

          orz that F solution was so damn cool!!

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

not able to solve C again!!!

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

How to solve D?

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

    always try inserting new comer into two maximum existing values! Submission

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

      That was a good idea.

      Should have thought of that.

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

    Greedy, keep track of which element contribute to the answer and how many times, like the 1st one contribute only 1 time to the answer, rest of the numbers does it twice. So just take the (sum of largest n / 2 element — 1st largest).

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    I tried this approach
  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    I maintained a priority queue, if anyone is interested I can explain the solution , because I think people have posted better solutions.

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

    Mine was a O(nlogn) solution by sorting the given friendliness of each player in decreasing order. And Taking into account the cases:

    1. First element will contribute exactly one time to the answer.
    2. All the other elements will contribute exactly 2 times.

    So just take sum of them in the order mentioned till you reach exactly n-1 numbers.

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

      I also did using same approach but My Solution is failing some test case. Can you please point out the error and link your solution.

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

        Your code is not considering the case that other elements will contribute twice. Try to change your approach.

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

What the hell with me . can solve D but not c ..everytime stuck on c..

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

    Consider all 2^h subsets of rows and 2^h subsets of cols and then try every pair of subsets that is brute force for all 2^h*2^w subsets

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

      what is "Meet in the Middle"?

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

        Meet in the middle is a standard technique to divide the problem into two halfs and brute force over all the possible subsets of the problem. SOme problems on Meet in the middle: if you want to practice. Meet in the middle practice problems

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

          Thank you so much. I heard this technique for the first time.

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

            This is not at all meet in the middle, but just basic brute-force. Meet in the middle would be something like: iterate through all subsets of rows, all subsets of columns and somehow combine result from them in time complexity closer to $$$O(2^W + 2^H)$$$ then $$$O(2^{WH})$$$

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

              Ya you are right , I have to edit it as when I was writing my mind was out of my body, sorry if it disturbed someone.

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

              What if the constraints were somewhat bigger. What would be the efficient approach then?

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

                My first thought would be: iterate through all $$$2^H$$$ subsets of rows, for each column find number of black cells at intersevtions of given column and one of chosen rows, then use some basic dp to count subsets of those numbers adding up to $$$K$$$. Total complexity is $$$O(2^HWK)$$$

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

      I am sorry but where's the Meet in the Middle part in C, it's just plain brute force.

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

        Ya While writing it I was thinking of some other thing! Sorry !

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

        Yeah, exactly, LOL. This is a simple bruteforce solution.

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

          But try extending the problem to H<=20 and W<=20, I think then we have to go for that? or may be some other heuristic.

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

            how can be solved using Meet in the middle ?

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

    Same here Solved D but not C

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

    C is just BruteForces My submission

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

      Can you please explain??

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

        Iterate over all subsets of rows. Now for each subset of rows, iterate over all subsets of columns. Iterating over the subsets can be easily done by for (i = 0; i < 1<<N; i++) { ... } It will give us: $$$000, 001, 010, 011, 100, 101, 110, 111$$$ in binary if $$$N = 3$$$.

        This is the basic idea

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

    since it was only 6. I did the Bruuuuuuuute force. Generated all sized subsets then ran a loop for every row and every column and for each combination checked whether it's valid or not.
    My Submission-C

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

      It's better to be general, rather than doing all combination do all subset. To find all subsets just use integer from 0 to 2^n — 1.

      Btw felt the need to tell this because your code was a bit lengthy.

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

What's the approach for F ?

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

    You can consider the nodes and edges independently if you count nodes as +1, and edges as -1

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

      Uhmm, can you elaborate a bit ? Thanks!

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

        If you have a forest, the total number of components is nNodes — nEdges.

        You can easily count the number of ranges a node is part of with combinatorics, and same for an edge (it is just nLeftRangeEndpoints * nRightRangeEndpoints). So you can count this contribution of each node and each edge as if it were the only thing in the graph.

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

      In fact it is exactly this question asked.

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

        Not exactly, the tree in codeforces question is linear. But we can convert a[i — 1] , a[i] logic to parent, child logic and it works same.

»
5 weeks ago, # |
Rev. 4   Vote: I like it +52 Vote: I do not like it

Brief Editorial :

A
B
C
D
E
F
»
5 weeks ago, # |
  Vote: I like it +7 Vote: I do not like it
  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Isn't this unfair, giving a question which is already available online, I mean the exact same question, most of the participants who googled something similar to find hints might have ended up copying the exact same code without any efforts of their own.

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

      The code provided doesn't have the mod 1e9+7 part, and that's a little bit tricky for negative numbers.

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

      In the last 2 contest I have seen happening this for C and now E.

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

How to solve E and F? Thanks in advance:)

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

    E: case out n==k, and when everything is negative.

    Otherwise, you can repeatedly remove the smallest two nonegatives and replace them with the largest two negatives as long the product of the two negatives is bigger.

    F: You can consider nodes and edges independently. Each node contributes +1 to the answer, each edge -1. You just need to count the number of ranges each node and each edge is part of.

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

      In E why after sorting both positive and negative numbers then repeatedly removing pair from the end which has maximum value(product) and if k is odd and there are only 2 positive numbers left then only removing pairwise from negative numbers didn't work?

      For odd K when i first removed the largest positive number separately and solve the rest for even k worked, why?

      WA AC

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

        Consider this testcase:

        5 3
        -2 -1 1 1 3
        

        The first method will select 3 and 1 since 3 x 1 > (-2) x (-1). Then it has to select 1, the only positive number left. However, 3 * 1 * 1 < 3 * (-2) * (-1)

        That problem can be remedied by ensuring that whenever two numbers are selected together at either end, another two numbers will be selected at either end unless no more element will be selected. It is easy to show that strategy cannot be wrong.

        That is why the second method works, because for even K, the maximum product, if it is greater than 0, must come from even number of positive numbers and even number of negative numbers.

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

      Your solution for E is just brilliant. Thank you

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

    For F for every segment think that every element is disconnected, and their contribution to answer is the length of segments. Now for each edge see in how many segments it can occur and subtract that number from answer.

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

Ok! can anybody tell me how to solve C? :)

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

    brute force, check all possibilities

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

    just look up all possible way to select rows and columns either by bitmasking or dynamic programming and check number of blacks for each combination

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

    Brute force

    Check for all possible subsets, if we exclude these then if the number of black cells is k or not.

    Max number of rows = 6

    Max number of subsets of rows = 64

    Max number of columns = 6

    Max number of subsets of columns = 64

    Total number of subsets = subsets of rows * subsets of columns

    Max total number of subsets = 64 * 64

    Complexity to check each subset = O(nm)

    Total complexity = O(2^n * 2^m * n * m)

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

    You can just brute force all the possible choices and for each choice count the number of remaning black squares. Check my submission for details: https://atcoder.jp/contests/abc173/submissions/15012234

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

E was on codechef as MMPROD.

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

Wow, E took me forever (and a lot of WA and lots of messy casework). Wondering if anyone has a cleaner solution.

(My messy solution: https://atcoder.jp/contests/abc173/submissions?f.Task=abc173_e&f.Language=&f.Status=&f.User=AnandOza)

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

    I was too getting wrong ans on 1 test case . Then I checked the modular operation I was doing and found the error in it

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

    I think it is less code if we separate the numbers into three groups, counting also the 0.

    https://atcoder.jp/contests/abc173/submissions/15010921

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

    I think mine is much cleaner. The idea is that you case out n==k and cases in which all numbers are negative.

    Otherwise, you can start with the positive numbers, and replace two positive numbers with two negative number repeatedly.

    That code is just:

    		int nPos=Math.min(pos.length, k);
    		int nNeg=k-nPos;
    		if (nNeg%2==1) {
    			nNeg++;
    			nPos--;
    		}
    		while (nNeg+2<=nNegs && nPos>=2 && 
    				pos[nPos-1]*(long)pos[nPos-2] < negs[nNeg]*(long)negs[nNeg+1]) {
    			nPos-=2;
    			nNeg+=2;
    		}
    		print(mul(posCS[nPos], negCS[nNeg]));
    
    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Nice solution!

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

      Ah, that is a lot nicer. Thanks! I'll try implementing it later.

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

      I was also approaching the problem in the similar manner. I was checking the two largest negatives not taken with two largest positives and whichever product is greater I was taking those two elements.But I got confused when the case when we will have to take odd number of negatives.So how to handle the product in such a case(i.e how to take the modulo in that case) or there won't be any case like that?

      UPD:Got it there was just a small mistake in implementation.I was printing the wrong value:(.

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

Defeated by Mod ;____;

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

can we see others submission? if yes then how?

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

    click on Results, then All Submissions

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

    If you want to see submission of a perticular person then, go to standing hover over the username and click on the searching symbol (magnifying lens). You can also do that by writing the username in all submissions. But I like the first one this way I can see the fastest submissions.

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

Can somebody guide me to an article(or anything for that matter) which has good theory on bitmasking? Couldn't solve C this time! (easy to read)Code for A, B, D, E @ https://atcoder.jp/contests/abc173/submissions/me

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

For D, getting WA on 9 test case , please help, what's wrong in my code. https://atcoder.jp/contests/abc173/submissions/15012383

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

For Problem E

First

Second

First code is not working for 2 testcases so i added one if for k==n that is second code and Second code is not working for 3 testcases. I can't understand how it is possible can anyone help me?

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

    because your if(k==n) part is wrong

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

      How Can you explain i can't get it still?

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

        Why are you doing mul=-mul? You are anyway multiplying the actual numbers.

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

I tried E by sorting all the numbers. If all the numbers in the array are positive the max product of k numbers is last k numbers. otherwise, we need to find the maximum of the first k numbers and the last k numbers and print the maximum. What is wrong with this logic.

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

    Consider this testcase:

    5 4
    2 1 0 -1 -2
    

    The product of first k numbers and the product of last k numbers are 0, but the correct answer is 4.

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

    Suppose the array is-
    -4 -3 -2 -1 0 1 3 4 and k = 4
    Product of first k numbers = 24
    Product of last k numbers = 0
    Your Answer = 24
    Actual Answer = (-4)(-3)(3)(4) = 144

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

can someone please help out with C?

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

    It can be solved with a simple brute force approach. Notice that h,w <=6, so just iterate over all possibilities and check.

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

I didn't even understand the problem statement of C.. xD

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

Anyone's comparing summation of log2()s failing for E?? can anyone explain how to overcome it??

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

What is wrong in this :

Try to take even number of negative numbers starting from descending order and multiply with even numbers left , again in descending order.

If the above is not possible, then check if a zero exists.

If a zero exists, ans is zero else answer has to be negative.

SO, try to take odd number of negative numbers in ascending order and choose remaining numbers as even, again in ascending order ?

https://atcoder.jp/contests/abc173/submissions/15018728

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

    A%mod > B%mod does not imply A >B

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

      I know, I haven't used that.

      Apparently,the mistake is overflowing of the product.

      Thanks anyway.

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

Can someone kindly explain the E problem https://atcoder.jp/contests/abc173/tasks/abc173_e

Here is a link to my solution and also give a test case where it fails. https://atcoder.jp/contests/abc173/submissions/15013047

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

Anybody used gfg's code for problem E?? If yes,please share your sol, i want to see my mistake!

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

    The Python code had an incorrect range for CASE II. Also, to avoid TLE, the mod had to be applied throughout.

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

    Yes, but got 26 AC and 11 WA. Maybe has some issue with modulo

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

Can anyone explain how to approach C ?

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

May somebody help me debug my code? Getting WA on one testcase. https://atcoder.jp/contests/abc173/submissions/15021212

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

My Solution

can anyone please check my solution and correct me?????

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

can anyone explain the approach of Problem C , I was able to solve A, B, D but not C. https://atcoder.jp/users/aniketakgec/history/share/abc173

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

    It is brute force .

    you can store count of no of black cell in rows and columns in an array . And then simply brute over all the possibilities of selecting row and column (i used bitmasking for it) . And can use above array to count number of black cell in each case ,if it is k , do ans++;

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

    Notice that the constraints for this problem are noticeably little, so all you need to do is to consider all possible combinations of rows and columns. Then, check how many of them have k remaining black cells.

    My Submission for this problem

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

    Simple brute force, try all possible combinations of rows and columns that are to be painted and simply count the no of black cells left in O(h*w) for a particular combination, total time complexity — O(2^h * 2^w * h * w)

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

Someone please help , why my logic is wrong in task D:

In D , i observed a pattern , suppose if we sort array , then :

Best optimal way to gain points is :
0 , a[n], a[n-1],a[n-1],a[n-2],a[n-2],a[n-3],a[n-3],etc... (k times)
But i got WA .
Code
  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    For n=1 your code gives the result a[n] but it's 0.

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

      In problem constraints n>=2 , btw i got my mistake , i forgot to put f=0 inside f==2 condition , Can't believe , i wasted 40+ minutes to find my bug , but was not able to observe it while in contest .

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

      Question says N >= 2

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

      in constrains 2 ≤ N ≤ 2×10^5

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

It was a nice contest. Thanks for sharing the link.

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

What is wrong with this code of E-

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

    Not sure if this is all but that block outputs negative numbers, the mod calculaton is not correct:

          if (A[n - 1] <= 0 && (k & 1)) { 
                for (ll i = n - 1; i >= n - k; i--) 
                    product =((product%mod)*(A[i]%mod))%mod; 
                return product%mod; 
            } 
    
  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    this code is from g4g

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

Initially, problem C had the constraint H, W <= 13 and needed DFS and pre-calculation :(

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

    Well, today's C was easy i.e. just briteforce. But was definitely much harder than regular ABC's

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

    How to do if H,W <=13, Can someone please explain the approach a little bit. I solved for the low constraints using bitmasking.

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

    can c be solved using recursion if yes can you please explain it? I am trying to solve it using recursion for hours but it's not working.

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

    Here is my DFS solution (O(2^{H + W} + H * W * 2^H)): https://atcoder.jp/contests/abc173/submissions/15031206

    Actually, the DFS part of the code can speed-up by using dynamic programming (like the knapsack problem) and solve the problem in O(H * W^2 * 2^H).

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

      Link is broken, could you correct it? I am very interested in reading it.

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

        Sorry, It’s now available.

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

In problem E-Multiplication 4 I was checking whether they have this kind of test case 5 4 1 2 3 -1 0 in their test set or not.

so, I removed one condition in my code and got AC instead of WA.

Output produced by AC code is 1000000001 ( -6 % (10^9 + 7) ) you can see here. Where the correct answer is 0.

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

OMG I misread problem E as maximum of all possible k length subsequences (a1*a2*a3*....ak)%(1e9+7). How to solve this task?

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

Got WA in B due to writing capital 'X' instead of small 'x'

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

My submission for E is giving WA for 5 tests. Actually I tried only limited cases:

First I sort array of absolute value of numbers descending order

  1. If first k have even number of negatives, we got our answer

  2. Otherwise we remove smallest negative and search for a positive among remaining n-k elements. If found positive, then this is an estimate.

  3. Another estimate is dont take one non negative among first k elements and search for a negative in remaining n-k elements. If negative is found then this is another estimate.

  4. If none of 2, 3 occurred then we know our answer must be negative so we chose last k elements as estimate. Otherwise we chose biggger of 2, 3.

Is this wrong? While writing this comment I realised that I havent checked which one of 2, 3 yields greater value. ;p submission link

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

I had a problem with E, most of the test cases passed but I don't know why I was not able to have AC on E. can anyone help me ? here is my the link to my code https://atcoder.jp/contests/abc173/submissions/15005580

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

English editorial may be helpful for all coders.

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

Can someone tell me why this solution is failing on certain cases.

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

    It is wrong logic. Consider the third and fourth being added to the circle.

    The third contributes min(a[0], a[1]), and the fourth, too. Because the fourth is placed on "the other side" of the second, which is between second and first, too.

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

      How third and fourth will contribute min(a[0],a[1])?? In the given example third is contributing min(arr[1],arr[4]) and fourth min(arr[3],arr[2])

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

        After third a[0], a[2], a[1], after fourth a[3], a[0], a[2], a[1]

        a[2] and a[3] where both placed between a[0] and a[1]. Its a circle.

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

I have submitted several times and still getting WA on three specific cases. https://atcoder.jp/contests/abc173/submissions/15025193

Is anyone stuck in the same cases to give me hand, because I have really no idea what is wrong. My main logic is to get the max K numbers and apply a replacement when the parity of negatives is an odd number.

Thank you !

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

In Atcoder the correct order must be A, B, D, C. Thrice in a row I was not able to solve C. Can anyone help pls. :(

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

ll solve(){ ll n; cin>>n;

if(n==1) return 0;

multiset<int,greater<int>> ms;
for(int i=0;i<n;i++){
    int a;
    cin>>a;
    ms.insert(a);
    ms.insert(a);
}

int sum=0;
int count=0;


for(auto x: ms){
    if(count>0) sum+=x; 

    //deb(sum);
    count++;
    if(count==n) break;
}

return sum;

} why this code is giving WA for D

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

please explain solution of C in easy language..

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

    Basically we have to pick a subset of rows and a subset of columns

    Then count the number of # character in those selected rows and columns say cnt if the (total # in matrix)-(cnt) equals k then increment the answer

    Do this for all combination of subsets of rows and columns i.e. 2^(W) * 2^(H) combinations

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

      Can there be cases where we have to choose 3 rows or 4 rows to get the desired number of black colors??

      I mean is there any restriction on how many rows or columns we can choose in a single time to get the desired number of black colors??

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

      oh now i understand what is going on.. thanks bro

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

    Since the constraints are small, we can use brute force. Notice that there are h rows and w columns. If we represent each row and each column by a bit, then we can use a bitmask of the form (1<<h+w) For eg: If h=4 and w=3, then 1101001 means we are considering the first row, the fourth row, the second column and the third column. Similarly consider every possibility, and subtract the number of # you encounter from the total. If this is equal to k increment your answer by 1.

    You can check out my submission here

    Submission

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

In D question, why can't the max element be added more than once? For example, consider the case :

5

2 2 3 3 3

Won't the max element be added more than once here??

UPD: I understood. Ignore this comment.

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

My code passes all the tests except one. I can't figure out any mistake. Please help. Link to my submission

Edit: I got my mistake. Here is my new submission

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

What is wrong with this approach for E? I covered the other cases such as only negatives and k=n. So when both positives and negatives are there, we take biggest elements by absolute value in our answer and count the number of negatives. If number of negatives is even, this is our answer. Otherwise, I am trading the least positive value in my taken numbers with biggest negative value among left out numbers or trading least negative value with the biggest positive value among left out numbers, whichever is better. Any counter test case for this ?

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

Can anyone help me understand why this code fails for a few testcases https://atcoder.jp/contests/abc173/submissions/15031526

i inserted the element as pair where first = absolute value and second value = 0 if positive else 1 and sorted the elements using abs value.In case of all negative elements i picked first k elements.Otherwise i picked the last k elements and noted the number of negative values(say nneg) and also kept track of the first negative value i picked(say firstneg).ifnneg is even then i print the product else in the first n-k elements i first look for maximum positive element and failing to do so i pick the least negative value and multiply it by product and multiply it by inverse of the firstneg.

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

    vkm23061998, your code fails for this TC. Maybe, this helps.

    Input:

    8 6

    1000000000 1000000000 -1000000000 -1000000000 -999999999 999999998 -999999997 999999996

    Correct Answer:

    192080

    (By taking the first 4 numbers and -999999999 and -999999997)

    Your Output:

    237699

    (By taking the first 4 numbers and 999999998 and 999999996)

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

    Also, I have done in a similar way, as yours. My code is passing all the testcases.

    You may like to view it : Link to my submission

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

Can anyone provide proof for the problem D.

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

    Same here. the proof in editorial is not sufficient imho.

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

    Here is my proof not depends on people arrived in the decreasing order. Consider all the n-1 comfort we can get. I will prove: If there are k numbers >= x, others < x, then among all comfort we can get, there are at most 2*k-1 comfort >= x.

    We note these k person as nice person, and the position between 2 nice person as nice position. also we note comfort >= x as nice comfort. 1. There are at most k-1 nice comfort we can get when these k nice person arrive(first nice person can not get nice comfort). 2. when a nice person arrive, nice position will increase at most one, when a not so nice person get a nice comfort, he must decrease a nice position. so not so nice persons can get k nice comfort at most.

    so we can get at most 1 comfort >= a[0], 3 comfort >= a[1], and so on...

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

    Think greedily

    1. Since we have to maximize the total comfort, so we'll try to get the maximum comfort possible every time.

    2. Maximum comfort using some i friends=Maximum comfort using some i-1 friends + maximum comfort from any remaining friend.

    3. By exchange arguments,step 2 will end up in maximum total comfort.

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

can any one explain me why this wrong in case of problem E ans=((ans*a)%mod+mod)%mod but this gives me AC ans=((ans+mod)%mod*(a+mod)%mod)%mod WA:https://atcoder.jp/contests/abc173/submissions/15038118 AC:https://atcoder.jp/contests/abc173/submissions/15038907

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

For E, what is the case 'after_contest_01.txt'? My code is getting 500 as it passes all the tests from the contest but fails on this one.

Note: It's also not in the TestCase Dropbox.

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

    I don't know if it will solve your problem but my code was failing for the same case only. Check this case.
    Input :
    7 5
    35 25 5 -25 -25 -25 -25
    Output :
    13671875

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

    I guess, maybe you've made pairs of positive/negative numbers and multiplied them. And if K is odd, then you multiply another positive number to the answer. I tried this as well and it got a WA on the case 'after_contest_01.txt'. You can multiply the only (not paired) positive number first if K is odd. It did solve my problem, hope it'll be helpful to you too.

    BTW, you can check the code since my English isn't good:

    AC: https://atcoder.jp/contests/abc173/submissions/15069072

    WA: https://atcoder.jp/contests/abc173/submissions/15068710

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

Can anyone check my submission for problem E : https://atcoder.jp/contests/abc173/submissions/15041696 it fails on just single case.Not able to figure out.

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

Please help in question E, why does this give WA????

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

Can someone look at this approach for C? Link to the post

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

What's wrong with my E submission? Submission

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

What wrong in my submission in E ,it's failing on 6 test cases https://atcoder.jp/contests/abc173/submissions/15042752 ?

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

    arpit_pro, vkm23061998, your code fails for this TC.

    Input:

    8 6

    1000000000 1000000000 -1000000000 -1000000000 -999999999 999999998 -999999997 999999996

    Correct Answer:

    192080

    (By taking the first 4 numbers and -999999999 and -999999997)

    Your Output:

    237699

    (By taking the first 4 numbers and 999999998 and 999999996)

    Hope, this helps.

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

Can anyone give a proper explanation of problem of C ? I didn't get the editorial.

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

Someone knows What's in "after_contest_01.txt"? (Problem E)

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

    I don't know if it will solve your problem but my code was failing for the same case only. Check this case.
    Input :
    7 5
    35 25 5 -25 -25 -25 -25
    Output :
    13671875

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

    Nuclear launch codes

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

For some (like me) who still couldn't figure out F

g(l,r): be graph of vertices[l,r]

e(l,r): count of edges in g(l,r)

f(l,r): count of connected components in g(l,r)

f(l,r) = count of vertices in g(l,r) — count of edges in g(l,r)

$$$\displaystyle\sum\limits_{l=1}^n \displaystyle\sum\limits_{r=l}^n f(l,r) = \displaystyle\sum\limits_{l=1}^N \displaystyle\sum\limits_{r=l}^n ((r-l+1) - e(l,r)) $$$ $$$=\displaystyle\sum\limits_{l=1}^n \displaystyle\sum\limits_{r=l}^n (r-l+1) - \displaystyle\sum\limits_{l=1}^n \displaystyle\sum\limits_{r=l}^n e(l,r) $$$

First part is easy O(n). For second part Let c(u,v) be number of ranges edge(u,v) contribute to

$$$c(u_i,v_i) = u_i*(n-v_i+1) $$$

Hence, $$$\displaystyle\sum\limits_{l=1}^n \displaystyle\sum\limits_{r=l}^n e(l,r) = \displaystyle\sum\limits_{i=1}^{n-1} c(u_i,v_i)$$$

PS: My first attempt at an explanation. I think there should be line-spacing option.

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

https://atcoder.jp/contests/abc173/submissions/15093804

Can anyone please check my solution? I am not getting anything wrong with my approach but getting wa continuously.

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

If anyone need Detail explanation (Not a video tutorial) for E Here