...starts in an hour. You're welcome!
# | User | Rating |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3831 |
3 | Radewoosh | 3646 |
4 | jqdai0815 | 3620 |
4 | Benq | 3620 |
6 | orzdevinwang | 3529 |
7 | ecnerwala | 3446 |
8 | Um_nik | 3396 |
9 | gamegame | 3386 |
10 | ksun48 | 3373 |
# | User | Contrib. |
---|---|---|
1 | cry | 164 |
1 | maomao90 | 164 |
3 | Um_nik | 163 |
4 | atcoder_official | 160 |
5 | -is-this-fft- | 158 |
6 | awoo | 157 |
7 | adamant | 156 |
8 | TheScrasse | 154 |
8 | nor | 154 |
10 | Dominater069 | 153 |
...starts in an hour. You're welcome!
Name |
---|
Anyone failed to log into the arena as me?
You are not alone, it happened to me quite often...
How to solve 550-problem?
For example you can reduce it to project selection problem, where white pieces are projects and empty cells adjacent to them are equipments.
It is equivalent to finding minimal vertex coverage in bipartite graph with on '.' and 'o' with edges between adjacent cells and answer is {number of '.' and 'o'} — {coverage size}.
How to solve 950? All people who submitted it have bugs?
I believe I had an almost correct solution, though I couldn't debug it in time.
We can notice that it's always better to leave fewer cells after the chosen one. So, DP: dk, x~--- minimal number of cells left after k moves if the chosen cell ends up in position x. The transitions are clear: we must take all possible rectangles not containing the chosen cell and very carefully count how many cells before and after chosen cells they contain. We can reduce number of transitions to O(n) via moving rectangles to some border when possible.
It suffices to notice that four moves are always enough to win. So, this solution is O(n2).
Can someone help me with Div2, 500 ?
Look at this thought:
If you have some
i,j
such that planet corresponds toA[i]
is exact same planet that toB[j]
, then there are have to be someratioA
andratioB
such thatratioA*A[i] == ratioB*B[j]
. Lets put all elemets ofA
multiplied byratioA
tosetA <- ratioA*A[i]
. And do the same for another array:setB <- ratioB*B[i]
.What you want to do? You want to find such
ratioA
andratioB
that merged-setResultSet = Merge(setA,setB)
have the smallest possible sizeSize(ResultSet) -> min
.Since size of
A
andB
is not more than 50 elements per each, you can check wiseratioA
andratioB
for alli
andj
forO(n^2)
and find size ofResultSet
inO(n)
[or even inO(log n)
, if you would use binary check of presence, which is not so important, but still is fun].So what
ratioA
andratioB
would be wise to choose for somei
andj
? Of course,ratioA = LCM(A[i],B[j]) / B[j]
andratioB = LCM(A[i],B[j]) / A[i]
.Final estimate is
O(n^3)
[orO(n^2 log n)
].Cheers.
Thanks a lot. I was heading in a similar direction initially, but I couldn't solve it. Thanks again :)
Editorial (Part 1)
Division 1 950's editorial is complete.