jeoj's blog

Old/Classical problems on a regional?
By jeoj, history, 6 years ago, In English

A time ago, I read this blog: aleigorithms — ICPC Latin American Regional – 2017

In that blog the author says "This is not an original problem. Is sad to see this kind of problems in an ICPC regional." when are explaining the solution to the problem (F — Fundraising).

A weeks ago I was talking with a friend about the 2017 Latin America Regional, and he told me that the problem I — Imperial roads is a classical/old question and not original and it's linked as a recomended problem on a tutorial.

I looked a while trying to find the "original" problems and the tutorial, but until now I cannot find it.

Somebody know where I can find the "original" problems?

  • Vote: I like it
  • -7
  • Vote: I do not like it

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I is a weighted version of the classic problem where you have to build bridges that do not cross eachother over a river. See https://people.cs.clemson.edu/~bcdean/dp_practice/ for example.

The cities are the people, on the northern bank sorted by beauty, on the southern by rich-ness. You also have to combine equal people, and sort people with the same rich-ness or beauty to make sure they can't both be in the solution.

However I wouldn't have a problem with I appearing in a contest, Especially since being weighted changes how I'd solve it.

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Thank you. The approach for problema I is LCA + MST.

    → Reply
»
6 years ago, # |
  Vote: I like it +3 Vote: I do not like it

This is so bad?

Seriously guys...I’m just asking about something that I read before.

→ Reply