But please, make it easier, as a person with <1600 rating,I can say, that at least 4-th problem was very and very hard for actual div3 participants.MrPaul_TUser Thank you anyway. ;)

Can you explain how transposing would give the same notion as m odd and n even? why are the values swapped?

After 9 days later

According to me you are assigning a occurrence of number same color assigned earlier.

Have u got the error in ur soln as i am also facing the same issue.

when ur are considering the nos having frequency less than k the order also matters suppose there are 4 colors. and 1,2,3 are having count less than 4. if the arrangement is like : 1 2 2 3 1 nos in array. 1 2 3 4 1 coloring . the no 1 is getting the same color.

I made the same mistake as you. For the testcase:

1
5 3
1 2 3 3 1

Your code outputs: 0 0 1 2 3 which is obviously wrong. The idea is that for the numbers where the number of it's occurrences < k you first color all instances of that number then move forward to the next number. Here's my solution, hopefully it's readable.

you are lucky

I misread the problem as you described during contest and was banging my head to get a solution :(.

Not sure whether this is correct, but here is what came to my mind.

We can calculate the maximum number of words we can take considering every character as the 'dominant' character.

Let us say we want to have 'a' as the dominant character. We iterate over all the words one by one, taking all of them in our collection (for now) and keeping track of the total frequency of every character till now. We also maintain separate sets for F(s, 'a', c2), where F(s, 'a', c2) represents this — In word s, frequency('a') — frequency(c2).

So now, suppose we encounter a word due to which 'a' is no longer our dominant character, but instead 'b' is. We refer to our set for F(s, 'b', 'a') and remove the the word s which has the largest F(s, 'b', 'a') from our collection (and also from other sets).

The idea is, take all words as you encounter them. But if a certain words causes 'a' to lose its dominancy to some other character (say 'b'), we will remove such a word which will reduce the total frequency of 'b' as much as possible while not hurting 'a' much, thus restoring dominancy of 'a'.

bro, just realized i read the problem wrong,thnks

Well done! Nice solution.

seems to be just

right?

In case odd we need to place one row of vert dominoes

I think there should be horizontal dominoes instead of vert..as in one row only horizontal dominoes can come.

Hey , I found your approach beautiful . But I know that I will never be able to find this kind of approach by myself. Can you show some lights on how you started thinking about the problem , and eventually came to this solution .

use this tc 1 6 3 1 2 5 3 3 3 your solution will output 1 1 2 2 3 0 but one of the correct ans will be in the form 1 2 3 1 2 3 I think your solution will also give tle for larger value of n. if you till have any doubt feel free to ask me.

Here's what I think. If you fixed the root, and then you fixed the depth of the nodes from the root, you want to find the number of ways to pick $$$k$$$ nodes from them so that their pairwise LCA is the root. Naturally, this splits up our set into some $$$m$$$ groups, from which we can fix $$$k$$$ groups and then the number of ways would be the product of the sizes of those groups. Let's say the group sizes are $$$g_1, g_2,...,g_m$$$. If we consider the polynomial $$$(x+g_1)(x+g_2)...(x+g_m)$$$, then the value we want is the $$$k^{th}$$$ coefficient starting from the largest term ($$$0$$$-indexed). Now, this product can probably be computed in $$$\mathcal{O}(n {\log}^2 n)$$$ with divide-and-conquer+FFT/NTT for an overall complexity of $$$\mathcal{O}(n^2{\log}^2 n)$$$. I haven't implemented it myself, so please point out the error if you think I'm wrong.

When the number of test cases is equal to 10000 your vectors hsh[200005] and prev[200005] initializations take too much time. Try the size of vectors N like in your v[] and ans[] vectors.
But your greedy idea to take the first vacant color is incorrect. Try test:
1
9 3
1 2 3 4 5 6 6 7 7
Your answer is:
1 1 1 2 2 2 3 3 0
The correct answer may be:
1 2 3 1 2 3 1 2 3

ty

Take k occurrences of the numbers whose frequency is greater than or equal to k. For all other numbers, take the total sum of frequencies of these numbers (let say the sum is s), and color a*k of these occurrences s.t. (a+1)*k>s .

Your idea to change only one color per one value is incorrect. Try test:
1
24 12
1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3
Your program gives answer
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
The correct answer may be
1 2 3 4 5 6 7 8 9 10 11 12 1 2 3 4 5 6 7 8 9 10 11 12
You may correct your program with changing as more colors for one value as you need. It will be a loop for your w variable.

Can you please elaborate your idea of binary search because I was trying to do it through binary search but got tle on tc5.Although B1 passes due to low constraints . Here's my submission https://codeforces.com/contest/1551/submission/124039451 Can I improve my code or do I need to think of solving it through another approach ?

The terms of the question are: i)each number should have different colors. i.e; a number cannot have the same color twice or more. ii)each color should occur the same number of times iii)the number of elements painted must be maximum. sol: let me explain with an example a=[3,1,1,1,1,10,3,10,10,2] and k=3.

i)you have k colors, so for a particular number the maximum number of colors you can have is k. then a number can only be painted k number of times. in the above example since k is 3 and there are four '1's . '1' can be painted only k(3) times. remaining ones are unpainted.
ii)for the second condition, each color should appear the same number of times. so for n numbers, each color can appear (floor(n/k))(i.e; (n-(n%k))/k). the total number of tiles that can be painted respecting the second condition is (n-(n%k)) or floor(n/k)*k. for the example above since there are 10 numbers 10-(10%3)=9 elements can be painted.
iii) to obey both of the above conditions, first you calculate the number of elements that obey first condition i.e; if the occurrence of the number is less than or equal to k, you count it if it is higher than k you only count k occurrences. then according to the second condition you take only the (n-(n%k)) elements of the counted elements. in the above example '3': 2, '1':4, '10':3, '2':1.
so the count is 9. then 9-(9%3)=9. so you can use these 9 elements for painting which satisfies all the three conditions. the tricky part here is the order in which you paint them, so you don't end with two numbers painted in the same color.
iv) create an array of n numbers and initialize all the elements to 0. then take note of the indices and count of all the numbers that satisfy the first condition. then only consider the first n-(n%k). then paint each number completely then move on to the next in a loop of the k colors.
example: a=[3,1,1,1,1,10,3,10,10,2] and k=3.

number:indices number:colors
'1':2,3,4      '1':1,2,3
'2':10         '2':1
'3':1,7        '3':2,3
'10':6,8,9     '10':1,2,3
answers may vary due to implementation!!!!

You see your vector initialization takes more time then memset() for an array. You don't need so big vector, length of n+1 is enough.

Your idea to start color numeration p from the same beginning color number c is incorrect. Try test
1
6 3
1 1 2 2 3 3
Your program answer is:
2 1 2 1 0 3
Correct answer may be:
1 2 3 1 2 3
Try to wrap color numeration p to 1 after color number == k and start with p for the next value. To prevent same values of one color don't push excess position numbers in your forward_list ls.

Try the test:
1
6 3
1 1 2 2 3 3
Your program answer is:
3 2 3 2 1 0
The correct answer may be:
1 2 3 1 2 3

Try test
1
15 6
17 1 2 3 4 5 2 3 4 5 6 9 11 12 14
Your answer is
-1
Correct answer is 1. It's enough to delete 17 from first position.

You have a very good idea of dynamic programming: dp[i] stores max quantity of fixed points, when the end of subsequence is exactly in the point i. Your corrected solution https://codeforces.com/contest/1551/submission/124053894

Same here, I have three comments in this thread. Hopefully, someone points out what's wrong here.

Your code got stuck in the same test case as mine did, buddy! Let's have a look at each other's code and discuss.

If you look at the output, you have a situation where two vertical dominos, sharing a side have same color. This is not allowed, as mentioned in problem as well.