COCI 2016/2017 round 3

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

Can someone please share their approach for problem C?

→ Ответить

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

I used bitmask DP, each bit representing whether a bottle still has water or not. It runs in O((n²)(2ⁿ)).

→ Ответить

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

Thanks!

→ Ответить

pas.andrei

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

Yep, and at a given state you have to iterate trough all the pairs and try to pour water from a glass with water to the other glass with water

→ Ответить

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

Yeah, that's exactly what I did. Just realized I typed a variable name incorrectly and got 0!!! T0T

→ Ответить

i4018

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

can you share your code pls

→ Ответить

Kerim.K

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

Here is my solution for problem C.

→ Ответить

NirShalmon

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

Same, but I doubt it's fast enough when n=20

→ Ответить

https://ideone.com/klSTpa

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

It is fast enough; I tested with max case and it ran amazingly in like 0.05s. The server is just really fast.

→ Ответить

hiddentesla

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

i submitted a dp bitmask O(n^2 2^n), the max runtime is 1,91 s

could you tell me how to optimize the code?

→ Ответить

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

Sorry, just realized it worked fast because my solution skipped a lot of iterations (it was incorrect, but the correct version works in 0.85s). Maybe your solution is slower because of recursion. Bottom-up should work faster.

Here's my code.

→ Ответить

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

you can also use some bitwise tricks to optimize
my code runs at most 0.51s on the server in Test#9

→ Ответить

bciobanu

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

← Rev. 7 →

You can also achieve O(N * 2^N) if you precompute for each set bit of a mask his optimal pair (where you should pour the water to). The downside of this solution is the O(N * 2^N) memory complexity, which doesn't fit in the ML that easily. For each mask we are only interested in the set bits, so a part of the table will never be used. We will need only $\text{[math]}$ cells. Here is my sketch of this idea, however i didn't manage to fit the last 2 tests into ML.. maybe someone else will. The next idea which comes in mind is to only use the stricly needed number of bits for each table, with packed bit fields.

→ Ответить

determinism

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

My solution has O(N * 2^N) time complexity and O(2^N) space complexity.

→ Ответить

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

← Rev. 2 →

I used a greedy approach like Kruskal's Algorithm for Minimum Spanning Tree.
The difference is that I stop connecting vertices when there are K connected components left.
I'm not sure whether my solution is correct or not.

UPD: I'm wrong, just ignore me QAQ

→ Ответить

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

Maybe you didn't notice that c_ij doesn't necessarily equal c_ji...

→ Ответить

Laakeri

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

+15

The writer of the announcement The polygon is simple, but it's not necessarily convex so there is no point in providing points in some sort of ccw order. has no idea what he is talking about. In most of geometry tasks it is really useful to know if the vertex order is counterclockwise or clockwise. Also in this task I had to make sure that the vertices are in counterclockwise order by computing the signed area.

→ Ответить

DBradac

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

+10

Yes, you are right, the writer of the announcement made a mistake. Although, it isn't very difficult to check whether the points are given in ccw order.

But, again, I agree with you and would like to apologize for that in the name of the organizers.

→ Ответить

sqrtdecompton

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

Anyone know when results are generally released?

→ Ответить

GuralTOO

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

+16

Actually, it is ~1.5 hours, but sometimes, it could be half an hour or even tommorow.

→ Ответить

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

Results are out!

→ Ответить

Kerim.K

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

Can someone please share their approach for problem E?

→ Ответить

Mikester

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

← Rev. 2 →

The problem can be reformulated as: Label the numbers in [2..N] with either 0 or 1. The final array will be: the numbers labeled with 0 in reverse order, followed by the first number followed by the numbers labeled with 1 in the initial order. Now you need to count for every such configuration of 0 and 1 what is the number of maximum increasing subsequences. If you traverse the array from finish to start, then from start to finish in this order and maintain the classic Fenwick tree for keeping and counting maximum increasing subsequences, in the end you will have counted the number of ways to form a maximum increasing subsequence and label the numbers in your subsequence with 0 or 1. You don't need to worry about using a number twice(the subsequence is strictly increasing). Now you need to multiply this by the number of ways to label the elements that you didn't use in the subsequence. It will be 2^(N-M) if you have used the first element in your subsequence and 2^(N-M-1) otherwise, where M is the size the maximally increasing subsequence. So you should solve for these two cases separately.

→ Ответить

DBradac

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

For each position we can calculate the longest increasing subsequence (LIS) ending with that position, and the number of ways to achieve that maximum. We calculate the same thing for the longest decreasing subsequence (LDS) starting from a position.

Now, it can be seen that the solution is a union of an increasing and a decreasing subsequence such that the smallest number in the LIS is greater than the greatest number in the LDS. All the moves that don't involve those positions can be arbitrary. Also, in some implementations, it is necessary to treat the first position a bit differently, but those are just details.

→ Ответить

Laakeri

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

+13

The test 16d in Meksikanac has k = 66332 even though in both English and Croatian statements and in the messages it says that k ≤ 10000. Most of other tests in groups 11-16 have the same problem.

→ Ответить

DBradac

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

We are currently fixing the issue.

→ Ответить

ipaljak

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

Hi,

I made a mistake when generating test data for this task and would like to apologize. We are currently investigating to what extent did this influence other contestants and will swiflty decide on how to proceed. From what we have seen thus far, it is very likely that you had the only submission where this makes any difference and we know your code gets accepted even with the larger constraint.

Again, I'm really sorry for the inconvenience.

→ Ответить

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

For problem B I tested locally the test cases my program received SIGABRT and it works fine, however in the Test section of the contest it shows bad_alloc error.

My code: Clcik

→ Ответить

sqrtdecompton

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

← Rev. 3 →

Is java.awt never allowed? I tried using it in-contest but I was given a compile error after submission that said "package java.awt does not exist". Just wanted to make sure this was intentional since I'm fairly certain java.awt should work with javac 1.8.0_102 and I didn't see anything saying that it was not allowed.

→ Ответить

hiddentesla

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

how to solve problem D?

→ Ответить

Anuar

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

← Rev. 2 →

First observation: Suppose for some expression A we can obtain the maximum value C (considering the boundary Z), then we can choose the value for this expression any number in [0, C].

For expression B which has some inserted expressions A₁, A₂, ..., A_k, we, therefore, obtain the array C₁, C₂, ..., C_k which is the maximum values of these expressions: We have 2 cases:

Sum

It is quite trivial so if we can choose for expression with index i any number in [0, C_i], then for the sum of these expressiosn we can choose any value in $\text{[math]}$ , and the answer is $\text{[math]}$

Product

It is somehow tricky, and I don't know how to prove it, but I will try to explain:

The best case for the product of k terms whose sum is S is when all terms are equal to $\text{[math]}$ . So the best strategy is to equalize terms. My approach was sorting the array C and trying to make them equal by making each term equal to $\text{[math]}$ , so if I can't make some element the optimal value, I will try to equalize the remaining ones.

My code.

P.S. Would be grateful for someone posting the proof of product case for this problem

P.P.S. Sorry for such incomplete explanation

→ Ответить

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

Is AM–GM inequality what you need to prove it?

→ Ответить

Frank_15

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

How to solve B efficiently?

I have used 2d dp, going from (1, 1) to (N, M) in each position I've been choosing better alternative. Bottleneck of this approach is that string comparisons required at each step, so I was expecting to get TL and I got it. But I am still thinking how to solve this better.

Any ideas / hints ?

→ Ответить