Facebook Hacker Cup 1A

15 лет назад, скрыть # |

← Rev. 2 →

Turn on the Lights
It can be solved in O(R³C³) by solving a system of linear equations with Gauss method.

→ Ответить

15 лет назад, скрыть # ^ |

Even though it did appear to me that gauss works, I've chosen to do 2^n*n*m anyway. Since it seems to be much easier..

Also interedted in how to solve problem B.

→ Ответить

15 лет назад, скрыть # ^ |

← Rev. 2 →

B problem. I have only the basic idea and can't understand some points in it.
First, if we understand, what the answer is, we can see, that there is some sub - sequence a₁, a₂, ... a_nand in sorted way this array looks like a₁, a_n, a₂, ... Then the answer is a₁ * ( a₂ - 1 ) * ( a₃ - 2 ) * ... Also we can see that this subsequence can be separate to 2: a₁ <= a₂ <= a₃ ... and a_n <= a_n-1<= ...
Let's construct such dp_i,j,k which means - i-th number is the index in A such that number is the last number of the first part of subseq, j-th number is the same but for the second part ( we construct the subsequence from its ends ), k - is the length of each part. To calculate the transition in linear time we can add the 4th parametr l - what part we are adding (0 - left part, 1 - right part).
Also in transition we should be careful with the equal numbers (I used set).
This is my idea. Maybe it's wrong but I hope there are some right points

→ Ответить

slycelote

15 лет назад, скрыть # ^ |

> k - is the length of each part
But the parts may have different lengths.

> Also in transition we should be careful with the equal numbers (I used set).
Can you explain the details? For example, how do you make sure that in the sequence (1,3,2,1,3,2) the subsequence (1,3,2) is counted only once?

→ Ответить

15 лет назад, скрыть # ^ |

we have 2 variants of K in dp - both parts are equal ( L = 0 ) and left part is K+1 and right part is K ( L = 1 ). We can assume in dp that in second case both part are K (it's no matter, because we are looking for the addind of the right part by 1 ).

In (1,3,2,1,3,2) at first we are look for the left part - at first we take 1, then 3, then 2 and after that we won't take anything. Then we look for the adding for the right part - it's 2, 3, 1, and again - nothing after these. We don't need to take the number, because we took it before) Smth like that.

→ Ответить

15 лет назад, скрыть # ^ |

How does it handle case when left part is much longer than the right part?

1 2 3 4 5 6 7 8 9 10 3 for instance?

→ Ответить

15 лет назад, скрыть # ^ |

Maybe I didn't understand the statements but " if first K elements are non-decreasing sequence and last N-K+1 elements are non-increasing sequence" - I think that first K elements ans second K elements

→ Ответить

15 лет назад, скрыть # ^ |

Marked it as bold for you :o)

if first K elements are non-decreasing sequence and last N-K+1 elements are non-increasing sequence

→ Ответить

15 лет назад, скрыть # ^ |

oops) sorry) now I see it)

→ Ответить

15 лет назад, скрыть # ^ |

First of all,

a₁ * ( a₂ - 1 ) * ( a₃ - 2 )

During the contest, believing that two sequences which elements are the same, but indices are different, are different (which is wrong) I coded the following solution:

Meaning of i and j is the same as yours,

k is sum of lengths of left and right parts

z (z is from 0 to 1) is whether we ever moved right pointer or not. Since when left and right pointer meet, I cound solution if and only if either left pointer points to number strictly greater than the one right pointer points to, or if right pointer was never moved.

It gives answer=19 instead of 17 on the fourth sample, since it counts some 1 2 and 1 twice.

Have no idea how to handle equal sequences yet.

→ Ответить

slycelote

15 лет назад, скрыть # ^ |

I had the same line of reasoning. Would love to know the solution…

→ Ответить

Jughead

15 лет назад, скрыть # ^ |

We can handle this trouble like that: let's just take the first element a[l] that was not before (after i) in current segment i .. j. For right side we can do the same.

→ Ответить

15 лет назад, скрыть # ^ |

Yes, good point. Seems like it will work.

→ Ответить

cauchyk

15 лет назад, скрыть # ^ |

can you please explain the procedure in a bit more in detailed manner.

→ Ответить

Vashegin.Roman

15 лет назад, скрыть # ^ |

← Rev. 2 →

Make n*m equations. Each equation consist of 5 or few variables: x(i)(j) + x(i-1)(j)+x(i+1)(j)+x(i)(j-1)+x(i)(j+1) = y. y = 0, if lamp is lighting and 1 otherwise. Solve these equations and sum all numbers from solution. Sum is the answer.

→ Ответить

NALP

15 лет назад, скрыть # ^ |

← Rev. 2 →

Why is it correct?

Gauss method may be used, if there are unique solution (determinant != 0). In another case, there are multiple solution (maybe, no solution). How are you choose the minimal answer?

In my opinion, you're wrong.

So, I think bruteforce is correct way to solve.

→ Ответить

15 лет назад, скрыть # ^ |

I have compared my answer to the answer of the person who used gauss, and it was the same.

I used 2^n*n*m solution.

May be it can be proven that answer is alweys unique. Or facebook is lame enough to prepare only tests which have unique solution.

→ Ответить

NALP	15 лет назад, скрыть # ^ \| 0 Can you explain your solution? → Ответить

15 лет назад, скрыть # ^ |

Fix what lamps are switched in the first row (2^m), iterate over all the rows starting from second (n), for each row for each lamp (m) switch it if and only if lamp above is off.

Complexity is 2^m*m*n.

→ Ответить

NALP	15 лет назад, скрыть # ^ \| 0 Nice =) → Ответить

cauchyk

15 лет назад, скрыть # ^ |

← Rev. 2 →

I used the same approach :) it took around 1 min to answer the input file... i thought for a second that it would time out :P... but is brute force the only way??

→ Ответить

udalov

15 лет назад, скрыть # ^ |

It is not: for "1 2 XX" there are 2 solutions.

→ Ответить

15 лет назад, скрыть # ^ |

← Rev. 2 →

I can't be confident in my solution before official results
But, here in my input: http://pastebin.com/cxrkze5X
And output: http://pastebin.com/smP02J0Q

Upd.
Because of Facebook is not very fast to publish results, here my answers for problem A
It's interesting to compare them
Input:
20
30 7
14 1
97 86
83 4
34 27
23 11
51 43
32 7
4 2
86 2
24 3
62 39
15 8
82 59
75 1
1 1
73 9
66 46
19 4
66 19

Output:
948425733
405146859
229148997
552088028
875219463
268080562
253211239
402231981
7
299325777
654845005
80187174
13402248
390562784
862630060
1
141282623
596669446
380563847
488623143

→ Ответить

cauchyk

15 лет назад, скрыть # ^ |

yes i think your answer is right for the above input (it matched with mine) :)

→ Ответить

15 лет назад, скрыть # |

1) It is clear thar order of switching lights doen't matter
2) You can switch 0 or 1times, because if you switch 3 times for example it will be equal to switch once

Now x_i, j = {0, 1} - "switcher state" - variables of the system of equations

Every point on the grid can also be in state {0, 1}, so
y_i, j = {0, 1} - right column of the system of equations

Now consider point on the grid with neiborhoods
x_i, j + x_{i - 1, j} + x_{i + 1, j} + x_{i, j - 1} + x_{i, j + 1} = 1 - y_i, j, where '+' is taken by modulo 2

^This is the system to solve

→ Ответить

it4.kp

15 лет назад, скрыть # ^ |

← Rev. 2 →

What does your program answer on a test
1
1 5 XXX..
?

→ Ответить

15 лет назад, скрыть # ^ |

Thank you!
I've really failed :(

→ Ответить

it4.kp

15 лет назад, скрыть # ^ |

Me too :)

→ Ответить

15 лет назад, скрыть # ^ |

Can you check my answers for A problem?
http://mirror.codeforces.com/blog/entry/1152#comment-20334
I think, 1 problem is enougth for passing to the 2nd round

→ Ответить

it4.kp

15 лет назад, скрыть # ^ |

I think they are correct

→ Ответить

15 лет назад, скрыть # ^ |

Thanks

→ Ответить

15 лет назад, скрыть # ^ |

I checked my input file for that problem, and it contained only test cases where there's either unique answer or there's no answer. So likely both of you passed.

→ Ответить

freopen

15 лет назад, скрыть # ^ |

Why have you decided to post this comment in this place?

→ Ответить