OnurSigirci's blog

Balkan Olympiad in Informatics 2014 (BOI 2014) — Turkiye
By OnurSigirci, 11 years ago, In English

BOI 2014 — Website (Turkiye)

boi2014.tubitak.gov.tr

"Welcome" article:

Dear participants,

It is our pleasure to express our warm welcome to all of you and thank you for coming and taking part in the 22th Balkan Olympiad in Informatics. The onsite contest will take place in Ankara, Turkey, from August 10th (arrival day) to August 17th (departure day) 2014.

At this website, participating countries will be able to find all the information about BOI 2014.

The Organizing Committee
  • Vote: I like it
  • +26
  • Vote: I do not like it

Comments Comments (22)
| Write comment?
»
11 years ago, # |
  Vote: I like it +6 Vote: I do not like it

What about age limit?

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

If someone needs information about Junior Balkan Olympiad in Informatics 2014 (JBOI 2014) , here is the official site http://jboi2014.dms.rs/index.php?action=show&data=home :")

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

I would like to participate this competition. But i couldn't pass the eliminations. :(

I wish luck to everyone. :)

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

Is there any schedule that describes detailed explanation ? (At least contest start time and finish time )

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

Hope all participants and team leaders would enjoy

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

Is there any feedback in this BOI?

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

    I received info that it will be the same format as the IOI. So full feedback and cms judge.

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

    Well, we had full feedback on JBOI 2014, so i hope that older ones are having it too. :)

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

No livescore, shame :(

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

First day finished, tough problems.

First is Hristo Venev with 225, Second is Mihai-iulian Andreescu with 200 and scores go down very fast. I got 6th place with 152, and 10th place is 87.

During the competition third problem was found to have wrong tests and was supposedly fixed, however I'm not certain that after the fix the tests were correct. Competition was extended by 45 minutes due to that.

Looking forward to the second day, hopefully I'll do better than today :)

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

    Good job. Can you post full results ?

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

      Well, I don't have them right now. However I can open the link OnurSigirci provided above while in Turkey (I'm batvanio's son if you wonder). Not sure if that's the final results though because when we got out Marko Stankovic had 155 and now he has 200. And it can be clearly seen that his last submissions are at 5:59h while the competition lasted 5:45h. They may have extended the competition for him only for some reason but I have no such information.

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

        Boi committee gave to Marko 20 minutes extra time, because there was a problem marko's computer.

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

          Thanks for info, now I can open the results. Can someone post tasks?

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

How to solve first problem(diameter)?

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

    Firstly you binary search the answer(we will call it D from now on) and then you test whether the answer is correct.

    To do so, you use several observations: — Each zone is a connected component — Each leaf is part of a component

    Therefore, we notice that it is ok to use a DFS algorithm and for every node compute the largest distance in each of it's subtrees. After doing so, we can sort the given distances and eliminate them from the array as long as the sum of the largest two exceeds D. We basically consider that we 'cut' the worst subtree and make it a partition of it's own.

    This solution gets 55 points.

    For the 100 points solution, when coming back from the DFS function, you notice that you don't need all the values from the subtrees. There are some more observations: — Any two values larger than D / 2 summed up will exceed D / 2, therefore one will be cut — Any two values less than D / 2 summed up will be less than D / 2

    Therefore, after cutting all, but one(the smallest subtree bigger than D / 2), and keeping all, but one(the largest subtree smaller than D / 2) you only have one thing to test: Are the subtrees left breaking the conditions(ie is their sum bigger than D)? If yes, you cut the one bigger than D / 2.

    → Reply