NWERC 2014 - Codeforces

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

+21

There will be an online contest. I have updated my post above with the correct URL and start time.

→ Ответить

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

+26

Reminder: the online contest starts tomorrow. You can also watch the onsite contest live as well as watch the live feed.

→ Ответить

pllk

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

+13

Is it correct that the online contest starts one hour later than the actual contest?

→ Ответить

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

+13

Yes.

→ Ответить

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

Hm, so online participants will have an advantage, because they will see what is done in "one hour in future". But on the other side since online contest is (mainly) individual then it shouldn't be that much easier :D.

→ Ответить

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

Yes, but the online contest is a lower priority for us and for technical reasons starting both at the same time is impossible.

→ Ответить

klubxq316

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

a very good contest,i will take part in

→ Ответить

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

+11

Is it possible to create a team for online contest? If yes, please say how.

→ Ответить

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

Yes, but it's a manual process. Please send me your team name and logins of the team members.

→ Ответить

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

← Rev. 2 →

Thanks!
Team name: Flawless
Member 1: Dmytro Ignatenko
Member 2: Роман Фурко
Member 3: Andrii Mostovyi (didn't register yet)

→ Ответить

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

← Rev. 2 →

Now your team is in the scoreboard. Tell me the third username once you know it.

→ Ответить

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

His username is andrii-mostovyi

→ Ответить

M0sTik

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

andrii-mostovyi

→ Ответить

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

← Rev. 2 →

Will ranking in online contest include teams from onsite contest? Or will we have access to ranking of onsite teams at least?

→ Ответить

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

← Rev. 2 →

+13

The rankings will be separate, but you can watch the onsite contest here.

→ Ответить

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

← Rev. 2 →

The online contest starts in about two hours!

→ Ответить

faiyaz26

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

How to solve problem F, I , K ?

→ Ответить

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

← Rev. 2 →

I: meet in the middle on $\text{[math]}$ half-cycles, watch out for constants

I suppose F is divide and conquer while bounding the number of interesting lines in a subset of points. I'm not sure what kind of bounding works, though. (UPD: Nah, I'm probably just getting the due to counting the same line many times.)

K seemed like just efficient simulation when starting at any knapsack + computing sums for all positions from that (the time should increase linearly when moving away from a knapsack till encountering another one)... not sure, I didn't try to code it.

→ Ответить

faiyaz26

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

← Rev. 2 →

I thought about the Meet in the middle technique but could not figure it out for problem I. Can you explain your idea ?

→ Ответить

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

← Rev. 2 →

Edit: I explained F instead :D

Try all choices for the first N / 2 vertices of any path and remember (in a set) just the starting, ending vertex, set of vertices in the path and length of the path. The number of choices is $\text{[math]}$ . Backtrack, bitmasking, anything works (but the time limit is a bit tight).

Suppose that you have two halves of a path: one between u₁ and v₁ and containing vertices from a set S and with length l₁, the other between u₂ and v₂ containing all vertices not in S. Try all choices of u₁, v₁, u₂, v₂, S, l₁. Try to finalize the cycle by connecting u₁, v₁ and u₂, v₂; now, the cost of the second half-path is uniquely given, so you can just check if it exists in the corresponding set.

→ Ответить

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

He asked about problem I, not F ; p.

→ Ответить

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

Whoops. The principles are so similar that I didn't even notice.

→ Ответить

andrew.volchek

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

← Rev. 4 →

In F p is always > 20. If line that contais > p% of points exists, then pair of randomly choosen points lies on it with probality > 0.04. So we can pick random pair of points several hundred times and either find answer or find out that it doesn't exists.

→ Ответить

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

← Rev. 2 →

Oh, of course!

I'm not really used to trying to find something like a randomized algorithm. I think the divide and conquer should work, but my code is getting WA somewhere. I wonder when the tests will be public...

UPD: solved it using divide and conquer, I just missed the case when N = 1 *facepalm*

→ Ответить

hex539

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

+16

Why a random pair of points? Just pick a single point, which has a 20% chance of being in the line. Count up the number of other points in each direction to check it.

→ Ответить

I_love_Hoang_Yen

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

Because picking single point is much harder to code :p

→ Ответить

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

How to solve A?

→ Ответить

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

Though easy problems were pretty ok, I didn't enjoy problemset in general, because 3 hardest problems were geos, no problem demanded any deeper insight (I think I figured out tricky cases in A and B, though in geo you never know) and problem "I" was really bad — I came up with good solution really quickly, but it was hard for me to squeeze it in TL, I needed 11 attempts and they differed by small optimizations.

→ Ответить

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

On the other hand, I think that NCPC problems were really nice :).

→ Ответить

I_love_Hoang_Yen

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

I also made 6 attempts (though 2 of them were WA 1 -_-). In my last optimization, I realized that since it is a cycle, we can fix 1 point at 0, thus gain 7x speed up. My last submission runs in 2.25s while TL is 10s

→ Ответить

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

For I there are plenty of solutions that passed well below the time limit. Your approach was probably not the fastest one.

In problem A one can come up with many "deeper inisghts" that simplify the coding. And I would also disagree on whether G was a geometry or not. It's Manhattan metric after all.

→ Ответить

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

← Rev. 3 →

I had complexity $\text{[math]}$ in problem I. Is there something significantly faster in terms of complexity?

And talking about A I agree that one probably should think much before starting coding it. I started, but I quickly realized that my approach is completely wrong, because I wasn't taking care of doing a lap, which was in fact main point here. I think that we should draw two half lines with equation x = x₁, y ≥ y₁ and x = x₁, y ≤ y₁ and consider crossing them in an appropriate order (of course creating a graph of admissible connections between them and doing some dp/Dijkstra). Is that right? Even if it is then I should think about many coding issues :P. And I have to admit that this problem is really taken from "real life", which is always a plus :).

→ Ответить

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

← Rev. 3 →

I did a Dijkstra but I was calculating winding number instead. Try solving this problem first and then modify that approach for A. Per Austrin thinks his convex hull solution is nice too.

The slides are up now, you can check your I solution.

→ Ответить

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

← Rev. 2 →

Hah, ternary search was essential/useful in 3 tasks (B, E, G) :D. And in B it was nested ternary search :P (after seeing the editorial I have to admit that I definitely didn't consider all cases and haven't thought about ternary :P). It reminded me of a problem when I ternary searched in ternary search in order to find place where is the best result and when fixing parameters I computed result in that place using binary search :P (problem B here: http://codeforces.com/gym/100491).

And model solution to I was essentialy the same as mine and resulted in exactly the same complexity. I would even say that my solution is more elegant, because it doesn't middle vertex and do that whole partitioning: http://ideone.com/cuWbcC It is basically Dfs considering all possible paths of length <=n/2.

Btw sorry that in previous post I asked about is there something faster than complexity which was an expression which couldn't be parsed xD. Codeforces got down for a while, so I didn't do a preview, now it's ok :pp.

→ Ответить

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

E? Pfft, binsearch on the derivative.

→ Ответить

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

Why? This is not a big difference between ternary and binary search and you do not have to do some not that nice computations about derivatives/any further thinking whether derivative is positive/negative.

→ Ответить

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

Why? Why not? :D

It's just that I have better skill in calculus than in coding ternary search, and if I express the original function as $\text{[math]}$ , with simple formulas for K, E, L, then I see immediately that the derivative is $\text{[math]}$ — and thinking about signs is a matter of seconds (large e: positive derivative, small e: negative).

I just pointed it out as "ha! but I'm different!" :D

→ Ответить

xennygrimmato

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

How to solve C and E?

→ Ответить

andrew.volchek

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

How to solve G?

→ Ответить

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

+16

I didn't code it, but I think this should work:

It is trivial, that if d = inf, then x * = med(x₁, ..., x_n), where med is a median function and analogous property holds for y * .

Firstly create circles with radius d for all points from input as their centers (in Manhattan metric, so in fact these are squares with sides parallel/perpendicular to y=x) and intersect them all, it will be a rectangle. If (med(X), med(Y)) lies within that field than we're done. If not, we should check all 4 sides separately (or even just 1 or 2, but doesn't matter). Each side can be checked in O(n) if we will divide it into intervals where we are not crossing x or y coordinate of any of the points.

→ Ответить

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

It's easier to do last step with ternary search by x.

→ Ответить

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

Good point, it surely simplifies code :) (this is not an irony, to be clear :p).

→ Ответить

ikatanic

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

← Rev. 2 →

You can also find rectangle in rotated plane in which solution must lie and then do 2D ternary search on it. You just have to be careful that not all points in that rectangle map to integer points in normal plane (only those with x%2==y%2 do), easiest thing to do is to do search twice, once for odd points and once for even points.

→ Ответить

xennygrimmato

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

← Rev. 2 →

+21

Videos of problem analysis.

→ Ответить