keko37's blog

By keko37, history, 6 weeks ago, In English

Croatian Open Competition in Informatics — COCI 2021/2022

Internet online contest series

As part of the COCI series, we are hosting an Internet online contest with problems from the Croatian Olympiad in Informatics 2022. The contest is primarily intended for high school contestants, but is open to all interested!

This contest is used in Croatia to select members of the IOI 2022 team. There will be three to five tasks and the contest will be five hours long. The contestants will have full feedback with at most 50 submissions per task.

It will be held on Sunday, May 29, starting at 15:00 (GMT/UTC).

Check out your local times at https://hsin.hr/coci/next_contest.html

You may use Python, Pascal, C, C++ or Java as your programming language of choice.

The two relevant websites are:

https://hsin.hr/coci/ — information about the contest

https://evaluator.hsin.hr/ — judging system

We hope that you will join us or encourage your students to do so!

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

»
6 weeks ago, # |
  Vote: I like it +9 Vote: I do not like it

Reminder: the contest starts in less than 30 minutes.

»
6 weeks ago, # |
  Vote: I like it +11 Vote: I do not like it

When upsolving will be available?

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    The problems have now been added to the judging system.

    You can access them here under Srednje Škole / 2022 / HIO.

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

This contest is used in Croatia to select members of the IOI 2022 team

So there will be no Izborne pripreme 2022?

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +24 Vote: I do not like it

    This contest is added up with the Izborne pripreme, so technically it is used to select the IOI team, but yes there will be Izborne pripreme 2022.

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

My solutions, in case anyone is interested:

A
B
C
D
  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    In C I think I proved that each SCC has no odd cycle even if you make edges undirected, so you can paint each SCC as bipartite graph beforehand, then do steps 1 and 2, and if next SCC was not fully painted, paint remaining nodes in it with precalculated colors and continue with regular algorithm.

    Btw, your solution looks natural (steps 1 and 2 are the only way to solve for DAG, for SCC my approach takes advantage that the SCC is bipartite, but your approach is more or less the same).

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

      In C I think I proved that each SCC has no odd cycle even if you make edges undirected

      I agree.

      if next SCC was not fully painted, paint remaining nodes in it with precalculated colors and continue with regular algorithm.

      I don't think it's quite that simple, because it's not always possible to colour an SCC just according to its bipartite graph. Consider the following graph: 1->2->3->4->5->6->1 (cycle of 6 vertices), plus edges 1->7 and 4->7. The only valid committee is {3, 6, 7}. In this case everything was forced by steps 1 and 2, but I suspect it would be easy enough to find an example where not everything was forced but it was necessary to colour an SCC in a way that doesn't match the bipartite structure.

      • »
        »
        »
        »
        5 weeks ago, # ^ |
          Vote: I like it +18 Vote: I do not like it

        After applying rules 1 and 2, look at the graph formed by the unpainted vertcies. Every node points to at least one other node, and since the graph is bipartite it always goes to the other "side". Therefore painting one whole "side" of the bipartite graph is enough. So you can apply this process to the SCC which points nowhere and then remove it completely and all nodes from other SCCs which now point to a red node. You can repeat this recursively. This was my solution.

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

        The proof of why my solution works is above. Regarding your example, you actually have an odd cycle on undirected edges (1, 2, 3, 4, 7), which can't exist in SCC.

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

          I'd missed that you only wanted to paint the vertices that weren't already painted. In the example, 7 is one SCC, and 1..6 is another.