Best of COCI #1
Разница между en3 и en4, 40 символ(ов) изменены
Since a new season of COCI (Croatian Open Competition in Informatics) started [last saturday](https://codeforces.me/blog/entry/96022), here is the first in a series of COCI appreciation posts (I will post one after each COCI round, so six in total!). For my coaching, I went through all COCI contests since 2006 to gather tasks and selected some of my favorite ones. ↵

### Notes↵
- I skipped a lot of the really hard tasks because they weren't useful for my students. I kept a list of these tasks, if someone wants it, they can PM me. Also, I only considered COCI, not COI. This current season is not being considered.↵
- There are many great tasks outside of the 48 shown (throughout the series), so it's worth it to go through other tasks as well. I have selected just my favorite ones.↵
- These tasks are maybe not always the most innovative, I have selected the tasks that are most useful for coaching and learning new ideas, so for people who already know the idea, the difficulty might be much lower. Still, there are some really interesting tasks.↵
- You can do these tasks either individually or as a virtual contest. There is a lot of them, so I wouldn't recommend less than 3h.↵
- The notes are meant for coaches, to know if they can use that task for a lecture that they are preparing. They can also serve as hints for competitors (but sometimes they just give out the solution). **Both the tags and the notes should be considered spoilers**.↵
- The given difficulty ranges might be completely wrong as I might be out of touch with the easier grades, they are just given as a loose guide.↵
- Most solutions can be found on the [official site](https://hsin.hr/coci/) by looking up the appropriate season and contest. If not, I'll try to provide the best resource I can.↵
- Let me know if you know some missing info (author/author cf handle).↵

### Tasks↵

#### [A: 2015/2016, Contest 4: Deathstar](https://evaluator.hsin.hr/tasks/HONI151645deathstar/)↵
Author: Dominik Gleich ([user:Dgleich,2021-10-23])↵

Tags: ↵

<spoiler summary="Spoiler">↵
bitwise operations↵
</spoiler>↵

Note: ↵

<spoiler summary="Spoiler">↵
Introductory task linking AND/OR.↵
</spoiler>↵

Difficulty range: 1100-1300↵

#### [B: 2013/2014, Contest 1: Organizator](https://evaluator.hsin.hr/tasks/HONI131417organizator/)↵
Author: Domagoj Ćevid↵

Tags: ↵

<spoiler summary="Spoiler">↵
sieve, harmonic sum</spoiler>↵

Note: ↵

<spoiler summary="Spoiler">↵
Non-standard sieve, good after learning Eratosthenes' sieve↵
</spoiler>↵

Difficulty range: 1300-1500↵

#### [C: 2017/2018, Contest 5: Birokracija](https://evaluator.hsin.hr/tasks/HONI171855birokracija/)↵
Author: 
?Ivan Zufić ([user:falanga,2021-10-23]) 

[Solution](http://blog.brucemerry.org.za/2018/01/coci-20172018-r5-analysis.html) (thanks [user:bmerry,2021-10-23])↵

Tags: ↵

<spoiler summary="Spoiler">↵
tree, dfs↵
</spoiler>↵

Note: ↵

<spoiler summary="Spoiler">↵
order-doesn't-matter trick, after that, dfs dp practice↵
</spoiler>↵

Difficulty range: 1400-1600↵

#### [D: 2009/2010, Contest 7: Svemir](https://evaluator.hsin.hr/tasks/HONI091074svemir/)↵
Author: Goran Žužić ([user:Zuza,2021-10-23])↵

Tags: ↵

<spoiler summary="Spoiler">↵
mst, 3d-points↵
</spoiler>↵

Note: ↵

<spoiler summary="Spoiler">↵
Picking $O(N)$ edges to apply Kruskal. Similar trick, in a much much more difficult task, was seen also in [IOI 2019 &mdash; Skywalking](https://oj.uz/problem/view/IOI19_walk).  ↵
</spoiler>↵

Difficulty range: 1600-1800↵

#### [E: 2014/2015, Contest 6: Kratki](https://evaluator.hsin.hr/tasks/HONI141566kratki/)↵
Author: Dominik Gleich ([user:Dgleich,2021-10-23])↵

Tags: ↵

<spoiler summary="Spoiler">↵
square-root, construction↵
</spoiler>↵

Note: ↵

<spoiler summary="Spoiler">↵
Square root longest monotone subarray trick. Trick later used in [user:Swistakk,2021-10-23]'s [favorite task of 2019](https://codeforces.me/blog/entry/72856?#comment-572130) (of course, that task is much harder :) ).↵
</spoiler>↵

Difficulty range: 1600-1800↵

#### [F: 2019/2020, Contest 6: Index](https://evaluator.hsin.hr/tasks/HONI202167index/)↵
Author: Marin Kišić ([user:mkisic,2021-10-23])↵

Tags: ↵

<spoiler summary="Spoiler">↵
persistent segment tree or parallel binary search↵
</spoiler>↵

Note: ↵

<spoiler summary="Spoiler">↵
Introductory task either for persistent segment tree or parallel binary search. Simple statement.↵
</spoiler>↵

Difficulty range: 2100-2300↵

#### [H: 2016/2017, Contest 1: Vještica](https://evaluator.hsin.hr/tasks/HONI161718vjestica/)↵
Author: Dominik Gleich ([user:Dgleich,2021-10-23])↵

Tags: ↵

<spoiler summary="Spoiler">↵
trie, bitmask dp</spoiler>↵

Note: ↵

<spoiler summary="Spoiler">↵
Nice non-standard bitmask dp task; easy code; introductory task for $O(3^N)$ sum over subsets.↵
</spoiler>↵

Difficulty range: 2200-2400↵

I hope you find these tasks useful!↵



История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en4 Английский MladenP 2021-10-23 21:18:54 40 Tiny change: '\nAuthor: ?\n\n[Solut' -> '\nAuthor: Ivan Zufić ([user:falanga]) \n\n[Solut'
en3 Английский MladenP 2021-10-23 18:19:18 97 Tiny change: '0-2400\n\n\n\n\n\n\n\n\n' -> '0-2400\n\nI hope you find these tasks useful!\n\n\n\n' (published)
en2 Английский MladenP 2021-10-23 17:17:32 3189 Tiny change: 'gleich])\nTags: <s' -> 'gleich])\n\nTags: <s'
en1 Английский MladenP 2021-10-22 13:30:19 1626 Initial revision (saved to drafts)