Codeforces Round #488 editorial

6 лет назад, # |

+15

В С точка лежит в диагональном квадрате, если манхэттенское расстояние от неё до центра квадрата меньше или равно половине диагонали квадрата

→ Ответить

shbhm_5301

6 лет назад, # |

← Rev. 2 →

AlexSkidanov Can you please upload the solutions(code) also. Thanks in advance :)

→ Ответить

RomaWhite

6 лет назад, # |

In F you are only considering gates that always return 0 in one of the configurations. Why is it impossible that all gates sometimes return 0 and sometimes 1 in both configurations but still all gates return 0 in one configuration for each input?

→ Ответить

6 лет назад, # ^ |

← Rev. 4 →

Edit: LHiC below challenged the author solution and the proof below. I will keep my incorrect proof here for history.

You can only use the 6 second-layer gate kinds described in the editorial (all other setups return 1 in both original and inverted configuration at least for one input).
If you have at least one of the first four kinds, such gate would return 1 for all inputs in one of the configurations, so you must have all gates return 0 in the other configuration for all inputs.
You must include at least one gate of the first four kinds, because if you only include the gates of the last two kinds, then for the input of all ones all the gates in the second layer will return 0 in both original and inverted configuration, and the output of the circuit will be different in two configurations.

Does it make sense?

→ Ответить

jinhaoxian

17 месяцев назад, # ^ |

my opinion(passed the problem but maybe incorrect):

it can be proven that,no gate always returns 0 in both(original,reversed) circuits,and if at a certain input,a gate returns 1 in both circuits,than it cannot be chosen.

divide remaining ones into two types:we can prove that,either (0,1) or (1,0)(original result,reversed result) cannot be archived,so divide them by that.Only circuits in one type may be chosen,so in one of the configurations(decided by the type we chosen),it always returns 0.

→ Ответить

vbobrov

6 лет назад, # |

← Rev. 2 →

+29

Another Div2C/Div1A solution: If there exists a point in squares intersection, it's also exists a point in squares intersection with integer coordinates. Then we can just bruteforce all points, because absolute values of their coordinates are small (<=100).

Solution.

→ Ответить

AnasAbbas

6 лет назад, # ^ |

how can you check if a point lies in the rotated square ?

→ Ответить

6 лет назад, # ^ |

+11

point lies in the rotated square if manhattan distance from it to square's center is equal or less to the half of square's diagonal

→ Ответить

Hossam

6 лет назад, # ^ |

Does this apply to a rectangle or a square with rotations other than 45 degrees? Can you also provide a proof of why does manhattan distance works? I've seen this method in Errichto solution here but couldn't prove it.

→ Ответить

6 лет назад, # ^ |

It applies only to square rotated by 45.
Proof, why it works:
If you look to its sides, you can see that the manhattan distance from any point on the side to the center of square is constant and equal to half of the diagonal. So if a point is farther than that distance, it is obviously not in the square.

→ Ответить

CodingKnight

6 лет назад, # ^ |

← Rev. 9 →

The Manhattan distance property should apply to any square if that square is rotated around its center using geometric transformation such that its two diagonals are aligned with the coordinates of the 2D plane.

The proof is a simple geometry exercise.

→ Ответить

vbobrov

6 лет назад, # ^ |

-7

I've checked only all points of rotated square, their coordinates are follows some uncomplicated regularities. For example, you can calculate length of diagonal and then start to bruteforce points one by one (first the higher one, then line of three points below, line of five etc.).

→ Ответить

I_love_Tanya_Romanova

6 лет назад, # |

+33

In Careful Maneuvering, my solution tries all possible meaningful positions for two spaceships, and then for each such combinations does simulation, so it is O(N⁵).

In Compute Power, I'm using the fact that values of b[i] are small to implement a solution that sorts tasks by power and then does knapsack dp[pref][i][j][sum_of_b] — where parameters are length of prefix, number of used computers with one task of higher power, number of used computers with one task of power equal to power of current task, sum of b[i] for first tasks on used computers so far, and the value of dp is total power used, so it is something like 50*50*50*5000.

Was any of these solutions considered during round preparation? What was the intended verdict for them? I'm confused because constraints look weird in both problems: it's like they aren't high enough to make it challenging to get AC with such solutions, but at the same time they are high enough to make it clear that intended solution is most likely different. Both of the solutions which I mentioned are not so hard to transform into right ones — but, at the same time, they are not so hard to cut off as well :)

Or is it about JavaBlitz thing, and they indeed don't pass in Java? :)

→ Ответить

hell_hacker

6 лет назад, # ^ |

← Rev. 2 →

How did you simulate in O(n)? I had to write a binary search resulting in O(n^5log(n)) which gave tle. for each spaceship I found if the resulting spaceship it hits is present or not and its range of indices so that I mark them hit. (I guess it is more than n^5logn, maybe n^6)

→ Ответить

I_love_Tanya_Romanova

6 лет назад, # ^ |

Coordinates are small, so we can keep an array of flags to answer query "do we have a ship at position P?" in O(1) instead of doing binary search.

→ Ответить

WolfBlue

6 лет назад, # |

+37

O(1) solution to Div2C without having to check for any intersections or handling many cases: Fix the center square, and see what locations the center of the diagonal square can be at. An octagon with 45 degree sides emerges. See below picture. The square in the middle is what is given to us, it has side length 2s. The diagonal square has a diagonal of length 2d. I drew 2 diagonal squares so you can see, if it is inside the octagon, then it intersects, otherwise it does not. We can represent this octagon as the union of two squares centered at the center of the first square, one parallel to the coordinate axes with side length s+d, and one at 45 degrees with side length 2s+d. Resulting code is short and clean: http://codeforces.me/contest/994/submission/39320205

→ Ответить

sunnylancoder

6 лет назад, # |

can someone explain how this solution works: http://codeforces.me/contest/994/submission/39313692

thank you!

→ Ответить

CodingKnight

6 лет назад, # |

← Rev. 5 →

My approach for solving problem 994C - Two Squares was:

Intersect the bounding box of the diagonal square [the smallest square whose sides are parallel to the X and Y axes and contains the diagonal square] with the first square whose sides are already parallel to the X and Y axes.
Search inside the resulting intersection rectangle if it is non-empty for a point that the diagonal square contains. If such point exists, then the answer is "YES". Otherwise, the answer is "NO".

Since all the given integer numbers are between -100 and 100, the intersection rectangle can contain at most 40,000 points.

39333649

→ Ответить

LHiC

6 лет назад, # |

+122

Don't last two kinds return 1 on all ones? nand(nand(1, 1), or(1, 1)) = 1. That makes author's solution incorrect on test:

3 6 6
nor xx. nor x.x nor .xx and xx. and x.x and .xx
and x...x. and x....x and .x.x.. and .x...x and ..xx.. and ..x.x.

All gates are of kind 5 (both participants' solutions return 0).

→ Ответить

6 лет назад, # ^ |

+35

Yep, this is a major mess up. I both misinterpreted the output of my script that was searching for the gate configurations, and evidently when I was stressing the solution against the naive, didn't get all the way up to 6 gates in both layers...

Would be interesting then to hear how Um_nik and Errichto solved it.

→ Ответить

6 лет назад, # ^ |

+84

And damn, should have listened to those guys and thanked MikeMirzayanov in the announcement...

→ Ответить

ko_osaga

6 лет назад, # ^ |

+44

So what happens afterwards? Is it rated at all?

→ Ответить

KAN

6 лет назад, # ^ |

+20

Yes, because there is a solution and the tests are not affected.

→ Ответить

Um_nik

6 лет назад, # ^ |

+30

My solution:

There are two types of bad situations: on some input first circuit returns 1, but second returns 0 and vice versa.

First type means that there is an input on which some gate in second layer of first circuit returns 1 and some (maybe other) gate in second layer of first circuit returns 1. Let's iterate over all ordered pairs of gates and check if there is such input. A pair of gates depends only on 8 variables, so we can check all possible values. If there is such input, we will draw an edge between these two gates. To satisfy first condition the set of remaining gates in our circuit must be an independent set in this graph.

Second type means that there is an input on which all gates in second layer of both circuits return 0. Let's suppose (for now) that we only want to check if this condition is satisfied for the whole circuit. Let's say that outputs of two gates in the first layer which are inputs for some gate in second layer are X1, X2. So we want OP(X1, X2) = NOT(OP(NOT(X1), NOT(X2))) = 0. It is easy to see that if OP is OR/AND then we want X1 = X2 = 0, and if OP is NOR/NAND then we want X1 = X2 = 1. So, our condition is "some gates in first layer should be equal to given values". Since gates are only OR/AND/NOR/NAND it is some instance of 2-SAT problem.

Now let's notice that that for second type some subset of a set is always worse than the whole set (we have less restrictions). So if we have some set on which there are no bad situations of first type than there is no need to check its subsets.

So, the whole solution is: find all maximal independent sets (using Bron-Kerbosch algorithm), then for each of them check if 2-SAT has a solution.

Yeah, it probably should be TL :)
Initially I thought that we only need 2-SAT once in the beginning, wrote the solution, it doesn't work on second sample. I have like 20 minutes left, so have to come up with some tweaks.

→ Ответить

vosptu

6 лет назад, # ^ |

+10

What if all maximal independent sets do not satisfy the 2-SAT? Do you need to check smaller independent sets?

→ Ответить

Um_nik

6 лет назад, # ^ |

+10

Maybe I used incorrect word. By 'maximal' I mean maximal by inclusion (I know that there are 'maximal' and 'maximum' but I don't know which is which :) ). If all of them do not satisfy then the answer is -1.

→ Ответить

6 лет назад, # ^ |

← Rev. 2 →

+10

If I understand Um_nik's solution right, 2-sat is used to find an input that would result in all the gates in some maximal set return zero in both configurations. If 2-sat finds such input, then such maximal set doesn't satisfy the condition from the problem statement, and naturally all its subsets do not satisfy it either (so no need to check them).

Otherwise such a maximal subset is an answer candidate.

→ Ответить

6 лет назад, # ^ |

+33

I think that the number of maximum sets will be at most two. My reasoning:

Let's split all the setups of gates in the second layer into four categories:

['nand(nand(a, b), and(a, b))', 'nand(or(a, b), nor(a, b))', 'or(nand(a, b), and(a, b))', 'or(or(a, b), nor(a, b))']

All these setups return 1 for all inputs in the original configuration, and 0 for all inputs in the inverted.

['and(nand(a, b), and(a, b))', 'and(or(a, b), nor(a, b))', 'nor(nand(a, b), and(a, b))', 'nor(or(a, b), nor(a, b))']

All these setups return 0 for all inputs in the original configuration, and 1 for all inputs in the inverted.

['and(and(a, b), nor(a, b))', 'nor(nand(a, b), or(a, b))', 'and(and(a, b), nor(a, c))', 'nor(nand(a, b), or(a, c))']

All these setups return 0 for all inputs in the inverted configuration, and something that depends on the input in the original

['and(and(a, b), nor(a, b))', 'nor(nand(a, b), or(a, b))', 'and(and(a, b), nor(a, c))', 'nor(nand(a, b), or(a, c))']

All these setups return 0 for all inputs in the original configuration, and something that depends on the input in the inverted

All other setups return 1 in both original and inverted configuration for at least one input, and as such can't be in the resulting set.

Now the maximal set might be one of the two forms:

All the gates from the first category and all the gates from the third category. If there's at least one gate from the first category, such set satisfies the condition from the problem statement (since such gate return 1 for all the inputs in the original config). If there's no gate from the first category, then we need to run 2-sat to see if for every input there's at least one gate from the third configuration that returns 1 (this step was missing in my original incorrect solution)
All the gates from the second category and all the gates from the fourth. Similar reasoning -- if at least one gate of second category exists, it's a good set, otherwise run 2-sat to check it.

Now we need to show that no other maximal set exists.

Gates from the first category can't possibly be with gates from the fourth, because gates from the first category always return 1 in the original configuration, and gates from the fourth return 1 for some inputs in the inverted, thus there's at least one input for which one of them returns 1 in one configuration, and one in another.

Similarly gates from the second category can't be with gates from third.

Finally, to show that the gates from the third can't be with the gates from the fourth, it is enough to show that if the input is all ones, the gates from the third category return 1 in the original configuration and the gates from the fourth category return 1 in the inverted configuration.

If I haven't messed up anything above, your solution fits into TL since it will consider at most two maximal sets.

→ Ответить

Motarack

6 лет назад, # ^ |

Is it possible to add that test to the main tests for upsolving? if I hadn't read this comment I would have probably thought that my wrong solution is correct and never went back to it.

→ Ответить

ghoshsai5000

6 лет назад, # |

Please take this constructively — all the problem statements other than C could have been written in a much clearer way.

→ Ответить

pk842

6 лет назад, # |

can someone please explain me the last sample test of Div2 D.

what i have understand : second person is sharing (1, 2) and (1, 3) so, it must have either (x,1) or (2, 3) and third time he is sharing (2, 3) and as this pair doesn't contain the both the numbers of second player. so, he must have (x, 1) but for (2, 3) to contain a number from his own pair (i.e(1,x)) he must have either (1, 2) or (1, 3) which will contradicts the first two pairs. so, how the given pairs are valid?

PS: sorry if someone finds this silly. but i'm really confused.

→ Ответить

6 лет назад, # ^ |

I can't understand you explanation . In this test , first player showed(1,2),(4,5) , which means one of them is real and the other one is a "made-up" pair . The same for the second player . if (1,2) in first and (1,3) in second is true , the common one is 1 . If (1,2) in first is true and (2,3) in second is true , the common number is 2 . So the observer could not determine the common number . For players , the second player could determine the number because he know which of the (2,3) and (1,3) is true . But for first player , he only knows his (1,2) is true , but he could not determine the second player's pair . So the answer is "-1" . Note pair(4,5) couldn't be the true one because there's no common number in the second player's pairs . The same for the second player's (1,2) because there's either two common numbers(if the first player's pair is (1,2) ) or no common numbers(the first player's pair is (4,5) ).

→ Ответить

pk842

6 лет назад, # ^ |

thanks a lot for this explanation.

→ Ответить

Hazyknight

6 лет назад, # |

← Rev. 2 →

I solved E by using divide and conquer and FFT that is O(nlog^2). FFT solution : http://codeforces.me/contest/993/submission/39324259 And I get TLE by using NTT instead of FFT. NTT solution(TLE) : http://codeforces.me/contest/993/submission/39317762 Can only body explain why there are so much difference between these two solutions?

→ Ответить

6 лет назад, # ^ |

← Rev. 2 →

NTT uses a lot of / and % operations, so it is slower than FFT.

→ Ответить

Hazyknight

6 лет назад, # ^ |

thanks Next time I'll try to avoid using NTT

→ Ответить

cwy

6 лет назад, # |

div1B can be solved in O(n*m) Why n,m<=12? During the contest,I thought I misunderstood the problem at first because n,m was so small.

→ Ответить

6 лет назад, # ^ |

+21

Maybe it's just for confusing you. :)

→ Ответить

thehumbleguy

6 лет назад, # |

RTE CODE my code shows RTE for some reason. can someone please tell why. When I replaced b[i] with variable t. It passed all test cases. this is so weird AC CODE

→ Ответить

djm03178

6 лет назад, # ^ |

You accessed from b[0] to b[m — 1], but the size of b is set to n, and m can be larger than n.

→ Ответить

njw1204

6 лет назад, # |

My approach for Div2B was using dynamic programming.

First, sort the knights by the power in ascending order.

Then, let them
dp[n][k] : the maximum number of coins the n-th knight has after he kills k other knights.
coin[n] : the number of coins the n-th knight initially has.

Finally,
dp[n][0] = coin[n]
dp[n][k] = MAX(dp[n - 1][k] - coin[n - 1], dp[n - 1][k - 1]) + coin[n]

→ Ответить

6 лет назад, # |

+18

In Div1 D , I saw the word"rounded up" . The google translation told me it means"1.4 -> 1 , 1.6->2" . Then I got wronganswer on test 8 and it turns out that we need to find the smallest integer which is bigger or equal than the answer .

→ Ответить

Ralsei

6 лет назад, # ^ |

I actually believe it's a translation mistakes, cause author is (I guess) russian. "Round up" is a literall translation from russian, which in russian means "to round UP", so there is no ambiguity. Author just didn't notice it's a phrasal verb in English.

→ Ответить