gKseni's blog

By gKseni, 3 weeks ago, translation, In English,

Innopolis University is organizing and holding Innopolis Open, an Olympiad in Informatics for high school students under 19 years old. The Olympiad consists of two stages — the online contest and the on-site competition (held in Innopolis, Russia).

Winners of the first stage will be invited to Innopolis to take part in the on-site competition. Accommodation, meals and transfer from Kazan to Innopolis are covered by the organizing committee. Winners of the second (on-site) stage will receive awards and opportunity to be enrolled in Innopolis University without any admission tests.

The first stage (online contest) will be held on:

  • December 2, 15:00 (UTC +3)
  • December 17, 10:00 (UTC +3)
    You may participate on both dates; the organizing committee will consider your best result. Registration is open until December 1, 2017. Participation is free of charge. The second stage (on-site contest) will take place in Innopolis city on February 24-25, 2018.

Click here to find out more and register for the Olympiad.

Stay in touch:

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

»
2 weeks ago, # |
  Vote: I like it +5 Vote: I do not like it

Hi everyone! Additionally, we would like to inform that Codeforces Round #402 (Div. 1) problems were the same as Innopolis Open 2016/2017 final problems. You may also solve the first (online) round from previous year Olympiad: gym.

»
9 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Where Do I have to login?

»
9 days ago, # |
  Vote: I like it +7 Vote: I do not like it

Why is the site down/when will it be up again?

»
9 days ago, # |
  Vote: I like it +16 Vote: I do not like it

PCMS is not working for >10 minutes! Please fix this and long queue.

  • »
    »
    8 days ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    Dear all, there were some problems with access to PCMS. We fixed it as soon as possible. Taking into account the lost time we add additional 30 minutes to the contest. We apologize for the technical problems.

    • »
      »
      »
      8 days ago, # ^ |
      Rev. 2   Vote: I like it +1 Vote: I do not like it

      It works well and fast now. Thanks.

      Also, please check my mail about personal information update.

»
8 days ago, # |
  Vote: I like it +4 Vote: I do not like it

How to solve D and E? I got 74 from D with O(n2) greedy solution, it was very easy to come up with solution, so I think 74 is much for this. Anyway, problems were nice, liked them.

  • »
    »
    8 days ago, # ^ |
    Rev. 2   Vote: I like it +1 Vote: I do not like it

    Someone solved D with suffix tree.

    • »
      »
      »
      8 days ago, # ^ |
        Vote: I like it +7 Vote: I do not like it

      Yeah, I thought it but tried some hashing-type things, then contest finished :P

      Actually, problem wants us to find maximum lexicographic substring of size k.

      • »
        »
        »
        »
        8 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        maximal lexicographic string of size (n — k + 1) is what you meant. You can prove that you can always pick a valid one, and you can find the maximal using a suffix array to compare substrings in O(1).

»
8 days ago, # |
  Vote: I like it +8 Vote: I do not like it

When should we expect results?

»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve C? I couldn't come up with anything.

  • »
    »
    8 days ago, # ^ |
    Rev. 2   Vote: I like it +1 Vote: I do not like it

    Greedy solution works. Just choose node with maximum number of distinct colored neighbors and update it.

    • »
      »
      »
      8 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Why does this work? I mean if we have many choices for a node what color do we choose to paint it?

    • »
      »
      »
      8 days ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      How about this one:

      6 6 3
      1 2 3 -1 -1 -1
      4 5
      5 6
      6 4
      4 3
      5 2
      6 2
      

      First, all the uncolored ones have exactly 2 possibilities so by your solution none have a priority. then, vertex 4 can only be colored with 2; if it's with color 1 there's no solution.

      • »
        »
        »
        »
        8 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        There is also little case for maintaining base colors — If uncolored node is not connected to some other uncolored node then I choose smallest unused color. Make graph from edges which connects 2 uncolored node for other cases, make set for each node to keep adjacent colors and check if it is possible to color node with found value after getting possible values with dfs. I didn't proved correctness this solution fully, but it intuitively seems correct.

»
8 days ago, # |
  Vote: I like it +1 Vote: I do not like it

Is the scoreboard student-only? If yes how many will qualify to the final?

  • »
    »
    8 days ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Last year it was around 40, you can see last year's results here (keep in mind there is another round on the 17th).

»
8 days ago, # |
  Vote: I like it +6 Vote: I do not like it

Will the qualification decided by max(point1, point2)?

If so I suppose the second round will have roughly same difficulity as this one, will it?

»
8 days ago, # |
  Vote: I like it +3 Vote: I do not like it

Anyone knows how to edit personal info in my Innopolis account? I wanna change my region as well as my password.

»
8 days ago, # |
  Vote: I like it +7 Vote: I do not like it

Can we submit the problems anywhere later?