Can someone help me with Sereja And Table please.
PS: I didn't understand the editorial.
№ | Пользователь | Рейтинг |
---|---|---|
1 | tourist | 3993 |
2 | jiangly | 3743 |
3 | orzdevinwang | 3707 |
4 | Radewoosh | 3627 |
5 | jqdai0815 | 3620 |
6 | Benq | 3564 |
7 | Kevin114514 | 3443 |
8 | ksun48 | 3434 |
9 | Rewinding | 3397 |
10 | Um_nik | 3396 |
Страны | Города | Организации | Всё → |
№ | Пользователь | Вклад |
---|---|---|
1 | cry | 167 |
2 | Um_nik | 163 |
3 | maomao90 | 162 |
3 | atcoder_official | 162 |
5 | adamant | 159 |
6 | -is-this-fft- | 158 |
7 | awoo | 156 |
8 | TheScrasse | 154 |
9 | Dominater069 | 153 |
10 | nor | 152 |
Can someone help me with Sereja And Table please.
PS: I didn't understand the editorial.
Название |
---|
Case 1: After change the table, there is at least row unchanged:
Iterate that row, then use this row to calculate minimal cost of other rows.
Case 2: After change the table, every rows changed:
There is at most k rows changed => m<=k => try 2^m state of first column => other column is same with first one or same with the inverted first column.
Thank you for your response. But i still don't understand your solution completely. What do do you mean after change of the table for example. Please try to give some small cases that illustrate your ideas, that will be very helpful.
Do you have trouble about Case 1 or Case 2?
Before showing you some example, we will talking about some properties.
Property 1: After executing operators (our table becomes expected table), suppose that we have row X[] and row Y[] (consider X and Y as arrays), there are only two cases: (1): X==Y or (2): X==^Y (^Y means change Y[i] into 1-Y[i]).
For example:
Notes that Property 1 is still right with columns, not only rows.
Property 2: If we "invert" a row on table (choose a row X and let X=^X), our table is still meet required conditions.
For example, invert row 2 in above example:
Note that Property 2 is right not only with rows, but also columns.
Now, let's talking about Case 1 and Case 2.
Example for Case 1:
Case 1 means there is some row is unmodified through operators.
Iterate i from 1 to row count, assume that i=2 (Row[i] = 010001). Choose Row[2] as a unmodified row.
Row[1] has two choices, (1): ==Row[2] and (2): ==^Row[2]. First choice is better (Cost=1). And second choice is worse, Cost=5. So if Row[2] is not modified, Row[1] must be 010001.
It is the same idea with Row[3], and Row[4].
Example for Case 2:
Try all possibility for Column[1], use Property 1, we have Column[2]==Column[1] || Column[2]==^Column[1], choose the better choice, then do the same with Column[3], Column[4].
Thank you so much. I now understand how to approach it. What a wonderful problem.