ACM-ICPC Финал 2017

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

+17

I think these were few reasons of only 1 ACd solution:
1) scary objective function, might create an impression of requiring hard math
2) actual solving of problem <=> realizing what is a set of reachable flows (F, W) (rectangle with cut corner). If you start solving this problem it is not obvious that this works this way, but as soon as you realize this it really is easier than it seemed to be 3) medium problems were harder than usual (at least in my opinion), they took more time to solve them, so not much time was left for harder ones (or at least, harder looking ones :p)

We got the right idea, but sadly apparently made some implementation bug along the way, got no time to debug

→ Ответить

SnapDragon

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

+48

Yup, rng's solution was pretty much the intended one, and it's relatively straightforward (as flow problems go). I was personally rather surprised how few teams attempted J. To your reasons I would add 4) the usual contest groupthink: nobody solved it early, so everyone assumed it was hard. :)

→ Ответить

ofi

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

Yes, but how exactly do I reconstruct the flubber and water flow?

→ Ответить

majk

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

Once you know how much flubber and water you need to send, you set the capacities from the super source to the flubber source and water source accordingly and construct a flow. Then you reduce the capacities of the edges to the value of this flow, and run flow once more, this time reducing the capacity of the edge (super-source, flubber source) to 0. This yields the water flow. Flubber can be found by substracting those two.

→ Ответить

ale

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

yeah, but how to know the direction of flubber for those edges with no water flowing at all?

→ Ответить

majk

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

From the first flow. It tells you how much stuff (water+flubber) goes in which direction. In particular, on every directed edge it holds

f_flubber(e) + f_water(e) = f_{water + flubber}(e)

→ Ответить

ale

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

ACC, thanks!!

→ Ответить

ofi

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

-8

ACC, Thanks!!

→ Ответить

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

I have a question

Chulalongkorn University, I remember that name from the previous year. This year they finished like 40. The last year they were the first team to solve a problem (First problem solved). After that they didn't solve anything (I don't remember if they attempted).

Does anybody know what happened there?

→ Ответить

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

+24

I think this was a very good chance to stop Russian domination on ICPC with Warsaw and seoul at their peak :D . Seems they will continue their domination for a little upcoming years before current chinese 17 years old lengendary grandmasters focus on ->

training on problemsets that consist in half of only ugly geometric problems and the rest somehow distributed between problems like "translate directly very chaotic statement into C++", some problems requiring backtracks filled with weird heuristics, some obvious problems requiring heavy library algorithms and one or at most two problems requiring some thinking Credits : Swistakk

→ Ответить

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

+39

Heh, I actually really liked this problemset, a lot of problems required really nice ideas, no library problems, just one geo problem that was on the easy side (however I personally would prefer more ;p). B falls into both reading complicated statement and backtracks with heuristics, but I heard it was not that painful (didn't read lol).

→ Ответить

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

This problemset contained some nice problems.(Of course I didn't solve all of these nice:v). I mean by nice something not belonging to the category above and you may see in an IOI or CF contest.

At the same time, some of them were unfair I think and gave advantage to some teams. I believe problem A was discussed\encountered by a lot of experienced contestants as I saw some variations of it before (even I am not a geometry fan but I saw). Problem D I believe is pasting from library.

→ Ответить

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

Yeah, A was kinda a fail, I solved exactly the same problem 1-2 months ago from old Petrozavodsk camp. That helped me getting first solve on this one xD.

I don't know why are you stating that D was pasting from library. It looked like it can be well known, but nobody from our team knew this. If you meant that main difficulty of D was writing D&C trick then I will definitely disagree (meaning that coming up with it was much harder). Inb4, if you ask then we don't have convex hull of hyperbolas in out library xD.

→ Ответить

I_love_Tanya_Romanova

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

Regarding problem D, does this one look familiar?

→ Ответить

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

+20

Yes, it does :). Funnily enough, mnbvnar gave me this problem few months ago and I couldn't solve it (he solved it, but I didn't learn solution), but today he hadn't got an idea and I came up with same weird trick with hyperbolas :pp. When I explained my solution to him he immediately recalled that problem and said it is basically same solution :p.

→ Ответить

http://codeforces.com/gym/100886/problem/I

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

← Rev. 3 →

+25

A problem mentioned in a blog is not that big deal. I mean every problem has a probability to be found on the internet in some chinese papers.

But I have seen the problem of pairs (a , b) and queries (x , y) and asking for max ax + by like three times. One of them is in this petrozavodsk camp [problem:http://codeforces.com/gym/100886/problem/I]

and another variation in our region and another one in a chinese regional (I don't remember unfortunately). It's really unfair to pick problems just found that easy way. Even petrozavodsk version is slightly different, But I don't think it will make that big difference. (anyway my friend solved this back in the virtual and I am just too lazy to think of these stuff) :D

Another thing that I came across

http://codeforces.com/gym/101047/problem/F

This is from a 2015 regional and exactly the same problem (even harder) as ICPC 2016 problem L (If not mistaken , it was easy anyway but still). It's from a regional qualifying to 2016 and surprise , same problem.

Like I have seen a lot of problems in ICPC that just requires a straight forward approach of something. Not a variation , the really straight one.2015 , 2016 was no difference.There are some things that I don't understand, Why problems in ICPC are different than stuff we see in IOI/POI/CF. I bet like most of teams in the contest spent their time sweating and debugging and arguing with each other. and nobody felt like he had fun solving the problems. Like POI problems for example or even CERC even are much more fun than ICPC problems and hard the same. Even though , you need simple stuff to solve the problem and so much creativity. It's just more fun than solving linear programming and a geometry problem that any code with less than 69 if statements is wa and still missing tests.

I haven't solved a really hard problem of past ICPCs but most of (easy->medium) problems are just like this.

→ Ответить

Riatre

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

Having creative challenges is nice, but the point of those Easy->Medium problems might be different. It's a problem solving contest after all, not a "hey I'm smarter!!" contest.

→ Ответить

mogers

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

+10

Also, given the speed of some Japanese teams solving G, it was probably similar to some local contest.

My utmost concern as a judge in an ACM regional was 'what if one of our problems exists elsewhere?'. I don't believe the judges knew about those problems, it's impossible to be sure that a problem never existed elsewhere.

I think this keeps coming up every year. This is basically unavoidable given the thousands of existing contest problems.

→ Ответить

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

It's not about existence of a problem. 2 problems were "traditional" problems. I don't know if there was more. Same thing every year.

The same situation of giving a maximum bipartite matching problem in a beginners qualifying contest in your university.

→ Ответить

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

+76

I'm Japanese but I've never seen similar problem to G. The only cause that Keio University took FA of G is this team contained me:D

The problem G seemed interesting and actually it was very interesting. I like others in this problem set too (except A). Thank you very much for problem setters! Also, thank you very much for all who supported this wonderful contest!

→ Ответить

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

+20

Heh, it was kinda suspicious to see that first accepted solution to G came from a team whose first accepted submission was on that very problem (before E and I) and which places around ~120th spot :P. Such situations usually mean that they managed to get away with some naive heuristics and maybe our team was first one to "really solve" this problem, but on the other hand this problem didn't look like one that could be solved using approaches that are not fully correct, so I was a bit confused. When after contest I noted that Keio team has snuke everything became clear :).

→ Ответить

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

+10

Sorry to confuse you & congratulations for gold medal!

→ Ответить

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

+10

Haha, no need to be sorry :D. Thanks to you we started thinking about that problem pretty quickly instead of being stuck on D which turned out to be a good decision ;).

→ Ответить

animeshf

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

snuke, what strategy did you use during WF? I am confused...

→ Ответить

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

I guess he used strategy "Screw overall result, let's have some fun solving nice problems and maybe getting some cash for First To Solve's" ;p

→ Ответить

http://myicpc.icpcnews.com/World-Finals-2017/scoreboard

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

+15

Yes. We ignored time penalty and aimed to FA in problems of my favorite genre (graph theory or some kind of puzzles).

The problems in the World Finals need much more thinking than Asia Regionals. The computer becomes vacant while I'm thinking because our team contains only one active competitive programmer. peryaudo was a blue coder but not so active now. So we are no match for the other teams at World Finals (especially in time penalty). This is the reason of my strategy.

In the contest, I read J and G at first. I misread J and it seemed impossible one. (I thought v is given for each edge. Without misreading, I would try to solve J instead of B.) I read G next and thought of solution for some minutes and got FA. I tried to solve B next. The written rule seemed almost same as a board game "Cluedo" but solution was not so obvious. (the intended solution seems using pruning in brute force... all writers must read this blog. I'll post about my solution.) I thought of solution for few minutes and implemented/debugged for long time. However I could not get FA. Finally we switched to solve easier problems but I was too tired to solve more problems. In parallel, my teammate solved E,I by himself and F with my hint.

As a result, we solved 4 problems and got WA/RE on B and C. To be honest, I think this result is lower than I expected. But I'm satisfied that we could complete our first goal "get FA" because I know it's difficult to perform perfectly in the crucial contest. Anyway the World Finals was very exciting. I wanna go next year too but I'm already not a student now(;_;) See you again at some contests!

→ Ответить

xuanquang1999

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

How to solve G?

→ Ответить

meeeep

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

← Rev. 2 →

This came partially from my own attempt at the problem and partially from listening to the solution on the livestream, so it might be corrupted, but I hope it's close enough and easy to follow.

Firstly, a little mathy rant: we can treat the state of the 300*300 squares as a column matrix C of size 1*(300^2). Then the reproduction without errors is simply multiplying by some (mostly 0) matrix M over Z_2 (just take mod 2 after multiplication). Hence, we have some sort of homomorphism: if f() brings us to the next state, then we have f(a+b) = f(a) + f(b), where a and b are states.

So now we can think of errors as toggling the state of 1 square, and hence 1 generation later, this will toggle the state of exactly 9 squares. This gives rise to a crucial observation that gives a trivial polynomial time solution: if a configuration has a possible previous state, then that state is unique.

Justification: Let E() denote possibly a mutation of 1 square. Suppose on contrary that E(f(a))= E(f(b)). Then E(E(f(a) — f(b))) = E(E(f(a-b))) = 0 (possibly), but (proof omitted, but loosely speaking I think considering 'corners' can prove this) there is no nonempty state s such that f(s) has less than or equal to 2 cells.

Furthermore, the bounding box of a figure increases by 2 in each dimension each iteration, so the question is just to find f^-1 of a state repeatedly, if it exists. Also, we need to do this at most 150 times, so this admits a trivial polynomial solution contingent on how fast we can find f^-1 of a state.

Let A be the current state we are given. We want to find (if exists) B=f^-1(E(A)).

It turns out we can easily check whether the top row of A contains a mutation: if there is no mutation, then we can recover the row from the top left corner onwards. Then, there is an error iff the top right hand corner has an invalid parity checker. Through a similar process, we may check the second row next and so on. Repeating for columns, we can find the row and column of the mutation, and once we know the location of the mutation, finding f^-1 is easy. (I'm rushing for time, maybe someone else can furnish a more coherent explanation for this part later?)

Since this process takes O(N^2), we have overall algorithm time O(N^3) and we are done.

→ Ответить

xuanquang1999

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

I think you meant "Then, there is an error iff the top right hand corner has a invalid parity checker", or did I miss something?

→ Ответить

meeeep

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

Whoops. Fixed.

→ Ответить

sanket407

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

← Rev. 2 →

Final ranklist ?? https://icpc.baylor.edu/scoreboard/ is frozem

EDIT : GOT IT !! https://icpc.baylor.edu/worldfinals/results

→ Ответить

redocyz

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

Thanks. How about scoreboard with time penalty?

→ Ответить

Azret

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

+10

→ Ответить

__ivan__

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

+10

Где-нибудь можно проверить решение задач?

→ Ответить

Azret

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

+10

https://icpc.kattis.com/problems

→ Ответить

Marco_L_T

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

← Rev. 2 →

Could anyone tell me the solution to Problem E?Thanks! UPD：I was confused by the data range n<=1000 and now I got it.Please ignore.

→ Ответить

lsiddiqsunny

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

Can you share your idea?

→ Ответить

Marco_L_T

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

Just do binary search on the answer,and you can pass in O(nlogn) time.

→ Ответить

lsiddiqsunny

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

Actually I did it.But it got tle on some cases. code

→ Ответить

chintu

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

In binary search on doubles, limit the number of steps to say 100, cause there will be precision issues comparing doubles.

→ Ответить

300iq

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

-16

How to solve H?

→ Ответить

yassin_

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

How to solve C?

I tried moving the max in a row/column to cover a row and a column (simultaneously) if possible, but I get WA test 7.

→ Ответить

itu

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

The only constraints are:

Every 0 must stay a 0
Every nonzero must stay nonzero
Every row must have its maximum somewhere
Every column must have its maximum somewhere

The first two are easy to satisfy by placing 0s and 1s. For 3 and 4, you want to satisfy both with the minimum amount of "placements" of values. You can save a value if you use it for both a row and a column. So try matching as many as you can!

→ Ответить

yassin_

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

Thank you for the hint :)

→ Ответить

haris471

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

+83

http://www.csc.kth.se/~austrin/icpc/finals2017solutions.pdf

All solutions

→ Ответить

SaveVMK

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

+10

There are also video solutions on the ICPC News YouTube channel.

https://www.youtube.com/user/ICPCNews/videos

→ Ответить

amsen

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

Why sharif fut didn't participate?

→ Ответить

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

+10

I guess visa issues.

→ Ответить

amsen

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

So why Tehran University participated?

→ Ответить

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

+28

I have no idea, probably because they got visas :P. For every number in set {0, 1, 2, 3} there was at least one team that had that many participants because of visa issues. Sad, but true.

→ Ответить

RedNextCentury

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

+38

There were teams with 3 members because of visa issues? :P

→ Ответить

hoangtun0810

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

-22

Give me some of your's ACM world finals t-shirts

→ Ответить

dalex

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

How much can you afford to pay for it?

→ Ответить

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

+18

My solution for B (without pruning and its time complexity can be estimate easily):

Brute force search for "which cards are removed" and "for each people/weapon card who has it". There are at most (6^2 * 9) * ((3^5)^2) ≒ 20,000,000 cases.

Before fix the distribution of people/weapon, the clue '*' is ambiguous. After fix, the clue '*' can be regarded as "if the player has suggested people/weapon card, this clue is no more information, otherwise the player has suggested room card".

Then for each pair of (player,card) can have one of three state "player has card", "player doesn't have card" or "player can have card". The distribution is possible if there exists an assignment for "can" state (to "has" or "doesn't"). The existence of assignment can be calculated by simple maxflow.

TL was tight so it was needed to implement carefully. source code (3.37s on Kattis)

→ Ответить

godmar

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

+13

I'm wondering how teams solved problem A. The computations regarding whether lines cross the polygon boundaries need to be done exactly, which — I believe — requires the use of exact arithmetic. The input coordinates are given with 21 bits. I think that means that you can, for instance, compute intersection points (42 bits), but not for instance midpoints between intersection points (84 bits).

What is the general technique for implementing these calculations exactly using only 64 bit integers?

(PS: I have a "naive" AC solution that uses C++'s "__int128" type and computes midpoints — but I'm certain it's not necessary).

→ Ответить

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

I don't know why are you so afraid of (long) doubles here, they work well. General setting when doubles can be bad is when perturbing slightly can change answer a lot in a not continuous way (here for example "does this point lie on this line?"), but here all points involved in such questions have integer coordinates, so it is very unlikely doubles will give significant errors.

→ Ответить

godmar

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

Can you explain this a little more?

Are you saying that using long doubles (with a 64-bit mantissa) would allow you to compute the line between any two vertices exactly (using 42bits), and it would also allow you to determine exactly whether another polygon vertex lies on that line (using 42+21 = 63 bits?)? But that if the other polygon vertex does not lie on the line then you'll conclude it's either not touching or crossing a polygon boundary anyway? And if crosses, it'll only influence the distance you report as answer, so rounding error does not matter? You determine whether it crosses using the sign of the result of the incidence test?

→ Ответить

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

Are you familiar with concept of using epsilons in geometry tasks? Since non-integer computations show up all the time in geometry we need to operate on real numbers and we can't expect doubles to satisfy conditions like a==b even if they are really the same number. If you want to check that A, B, C lie on same line you can check whether CrossProd(A, B, C) = = 0 if you have everything implemented on integers, but you can't do it like that if they have real coordinates and in such case we check whether abs(CrossProd(A, B, C)) < ε, where epsilon is chosen wisely, for example ε = 10^- 9.

Here is my code for reference that gets accepted on Kattis: http://ideone.com/08pisZ

→ Ответить

mmaxio

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

+53

wisely

LOL

→ Ответить

godmar

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

Thank you. I'll take a deeper look at your code.

I note that the only place where you require the epsilon check in this problem is your ptOnSegment (due to the use of the sqrt() function.) If you remove the epsilon check from the other tests, your program will still pass. That said, this version of ptOnSegment was new to me, thank you.

For fun, I tried my solution (which avoids division and sqrt) with double and long double, and __int128 — it passes with all three choices: http://ideone.com/zy3uG9 (and no epsilon).

→ Ответить

SnapDragon

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

← Rev. 2 →

+13

IMO, it's reasonable to be scared of using doubles on a question like this, despite the integral coordinates. You identified the main issue: that a candidate line could just barely work or not work depending on how close a polygon vertex gets to it. The problem is inherently unstable (that is, there are valid input cases for which permuting the vertices by a small epsilon leads to a large delta in the answer). Thus care is warranted.

Unfortunately, it's not trivial to see what the worst-case epsilon is. With coordinates bounded by 10^6, how close can a lattice point get to a lattice line without lying on it? If I remember correctly, the actual answer is 7*10^-7, for the simple case of (1,1) and (0,0)-(10^6,10^6-1). But it's not obvious (to me, anyway) why another less-simple example couldn't come closer. EDIT: I guess Pick's Theorem is the way to prove it. :)

So for this problem you need an epsilon on the order of 10^-7, for coordinates ranging up to 10^6. 13 decimal digits of precision are required, and doubles have 15, so they're good enough. But it's close. In a contest I'd still try to use integer arithmetic (well, doubles guaranteed to be integral) whenever possible.

→ Ответить