Pancake's blog

Croatian Olympiad in Informatics 2013 , Discussion
By Pancake, 12 years ago, In English

Hello all. Today , I participated in a contest with problems from the Croatian Olympiad in Informatics. The relevant contest environment is here. I had a perfect solution for the 3rd problem , and I was able to solve the first part ( finding the number of different values of the shortest path) of the first problem.My backtracking solution for the 2nd turned out to be buggy and scored 0. Since they take too long to publish the results along with codes and solutions on COCI , I'd appreciate if anyone who has participated ( specially those solving many tasks perfectly) can explain his algorithmic approaches for solving the problems.Thanks!

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

»
12 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Last problem: You can add one more vertex V0 to the graph. Put distances to other nodes as prices of sending spies on assignment. Then the answer if weight of this graph's MST. It is quite easy to prove :)

I didn't solve the first problem because I can't find the sum of the sorhterst distances for large cases. We can use binary search to find the largest X that makes the path shorter than without using hiperroutes at all and, of course, the shortest path will be disticnt for every value of X smaller than this, so the largest X is the first answer in this problem :)

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

How long did the exam last ?

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

SNJEGULJICA :

I use segment tree by this way, for every query (A, B) we will find smallest and largest position of numbers from A to B with segment tree, if largest pos — smallest pos == B — A then answer is YES else it's NO.

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

How to solve 1 problem ?

→ Reply