ssi7415's blog

2014 Singapore National Olympiad in Informatics
By ssi7415, 11 years ago, In English

Hi all,

Singapore has recently concluded its 2014 National Olympiad in Informatics (on 8 March 2014), which is used to select the team to represent Singapore at 2014 IOI.

All tasks (4 of them) can be found here and all test data can be found here.

Edit: Just a note here, the time limits and memory limit of the problems can be found on the first page of the document (notes, point 5).

Enjoy the tasks!

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

»
11 years ago, # |
  Vote: I like it -31 Vote: I do not like it

lol, singaporeans know what computer is

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

Is Fibonacci heap expected for problem 2.4? Input seems to be extremely large. And it is not like IOI or topcoder, which are io-free, so your program must read more than 1M integers. (Maybe pascal code TLE only for reading, that's not fair!)

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

    As I know, in practice, Fibonacci heap is not much faster than binary heap, sometimes it's even slower.

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

    I think sorting the edges by the decreasing(non-increasing) order of the weight and using disjont-set data structure is enough to solve this. Iterate the edges in the sorted order, connect the edge, ans find if the vertex is in the same component with vertex 1. Then we will be able to answer all the queries

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

Last test (4.2) in the 'sightseeing' problem is incorrect — it contains edge 1 2 200000, while quality of the road should be not greater than 10^5.

→ Reply