you jinxed it (at least for me) :(

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

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

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

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

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

C is just BruteForces My submission

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

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

It is similar to this question of codeforces

https://atcoder.jp/contests/abc173/submissions?f.Task=&f.Language=&f.Status=&f.User=Gary

F nice formular, but not understandable for those who did not solve it.

Problem D:

I have implemented it in the exact way that you mentioned, but it just happened to fail at only 2 test cases, can you help me in finding out the bug in my submission ?

can you explain F?

In solution F: My understanding:

1. X= contribution of all the nodes in total summation

2. Y=Contribution of each edge in the total summation

3. ans=X-Y

Kindly explain your recurrence(I understood Y ,kindly explain X)?

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.

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.

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.

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

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)

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

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

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

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]));

https://www.geeksforgeeks.org/maximum-product-subsequence-size-k/

Here is good implementation

E also makes me frustrated. :'(

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.

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

I can explain you if you need help for C

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

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.

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

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

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

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

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

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)

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

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

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

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

It is wrong logic. Among other things you totally ignore that there can be 0 in a[].

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.

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

Please help me its failing on 2 testcases. Submission

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)

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

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

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

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

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

Test: random_mz01.txt

The Output is 0. Expected is 649491334

prod=prod * a[i]%MOD * a[i+1]%MOD;

Won't this overflow?