PeterNaut's blog

Can this problem be solved?
By PeterNaut, history, 7 years ago, In English

In my icpc regionals they put this problem (link below), but no one came up with a correct solution that runs in time. Does anyone know a solution? The time limit is 60 seconds.

Do you think it can be solved in time? The official solution is a silly heuristic and it is easy to find test cases to make it give wrong answer.

http://localdoc.scusa.lsu.edu/problems-regional/prb.php?prob=10

  • Vote: I like it
  • +48
  • Vote: I do not like it

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

Auto comment: topic has been updated by PeterNaut (previous revision, new revision, compare).

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

What is the time limit(as you mentioned, run in time)?

→ Reply
  • »
    »
    7 years ago, # ^ |
    ← Rev. 4   Vote: I like it 0 Vote: I do not like it

    You have 60 seconds per input (but each input can contain up to 100 cases)

    → Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by PeterNaut (previous revision, new revision, compare).

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by PeterNaut (previous revision, new revision, compare).

→ Reply