Facebook Hacker Cup 1A

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

← Rev. 2 →

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

→ Ответить

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

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.

→ Ответить

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

← 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

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

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

→ Ответить

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

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.

→ Ответить

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

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?

→ Ответить

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

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

→ Ответить

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

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

→ Ответить

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

oops) sorry) now I see it)

→ Ответить

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

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

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

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

→ Ответить

Jughead

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

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.

→ Ответить

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

Yes, good point. Seems like it will work.

→ Ответить

cauchyk

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

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

→ Ответить

Vashegin.Roman

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

← 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

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

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

→ Ответить

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

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	14 лет назад, # ^ \| 0 Can you explain your solution? → Ответить

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

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	14 лет назад, # ^ \| 0 Nice =) → Ответить

cauchyk

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

← 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

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

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

→ Ответить

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

← 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

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

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

→ Ответить

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

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

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

← Rev. 2 →

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

→ Ответить

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

Thank you!
I've really failed :(

→ Ответить

it4.kp

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

Me too :)

→ Ответить

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

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

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

I think they are correct

→ Ответить

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

Thanks

→ Ответить

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

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

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

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

→ Ответить