2018 was a semiprime year with great contests and some notorious coincidences.
From the problems that I proposed, my favourite was HAMEL, I invented it by mixing the definitions of eulerian and hamiltonian paths, the deterministic solution involves matroids, however many people solved it with randomization. Another problem of my hand that I liked was PWRTREE because it has a nice combinatorial solution by interpreting the digraph as an elimination tournament.
I didn't took part in CodeForces contests this year, but while training for snackdown I found an interesting problem in the Gym about constructing a maximum matching of line graphs.
My favorite problems are PSHTRG (very good datastructure problem) , HMAPPY1 . Also from codeforces my favorite are Masha and her two friends ,Connect three. I think there are will be also a good problems in this year's last Div3 contest.
Hopefully there are good problems in Goodbye 2018 as well :)
I certainly hope so, too!
are you the setter :)?
https://www.reactiongifs.us/wp-content/uploads/2014/06/its_classified_barack_obama.gif
Hope so too!
Hope there will be Hello 2019 as well.
Wait, connect three from today? What made that good?!
Probably the fact that this problem made him blue :)
hmrockstar
Proud father xD
https://www.reactiongifs.us/wp-content/uploads/2014/06/its_classified_barack_obama.gif
Well, 1087C - Соедините тройку in yesterday's Contest seems to be among the most enjoyable problems in 2018. This problem can be generalized in computational geometry to Connect Four, Connect Five, and Connect N for any given set of N ≥ 3 distinct points in general. The following is a possible solution of the generalized problem.
Connect N: A generalization of the 1087C — Connect Three Problem
ABC115 — D is best problem for me, it is so fun to solve such observation problem solvable with 20 lines (or less). Second is 1056B — Divide Candies.
"In some other world, today is Christmas."
In our world, today is Christmas! :D
Karen (one-word problem) https://mirror.codeforces.com/contest/869/problem/A
Lunch Queue
Problem 1 Day 1, IOI 2018 — Combo
Because.. Why not? :P
and you wrote it :)
CBFEAST of course! Such a simple algorithm with powerful applications!
Please tell how to solve it then :P
(i didnt code this solution, but one of my friends got AC with it so..)
I am giving the short version here. construct a dynamic lazy segment tree over C, such that it will store prefixmax, suffixmax and overallmax (refer to problem GSS3 in SPOJ for a similar idea)cost subarray for each vertex. The lazy values will also be pref,suf and overall max so that it can be combined. when doing an update, we will add the value to the range [c-k,c+k] in the segtree. when doing a query, we can simply access the value for that specific colour. note that adding at front and back is just manipulation.
PS: some of my friends also ACd it using history information technique described in segment tree beats blog.
For me, these ones:
1) Div.2D — Beautiful Graph
2) Div.3D2 — Great Vova Wall (Version 2)
3) Div.2E — Missing Numbers
4) Div.2D — The Fair Nut and the Best Path
Thanks for their authors.
And between them, the best ones are the 3rd one and the 4th one with no preferation between them.
Great Vova Wall (Version 1)
Great Vova Wall (Version 2)
these tow are on the top of my favorites in 2018, just how beautiful and simple are their solutions and tricky as well
My favourite was from Opencup GP Udmurtia: C. Unseen Segments. Still can't solve it.
Other favourite problems. From Opencup.ru:
GP Azov: I. Key Brute Forcing
GP Khamovniki: G. Piecewise Linearity
GP Poland: M. Matches
GP Bashkortostan: F. Firs
GP Korea: H. Fractions, L. Timsort, N. Rising Sun
GP Petehof: A. Alice and Path
GP Siberia: 13. From N-ary to M-ary
GP SPb: D. Distance in Crosses
From Codeforces: 913E - Логическое выражение, 965B - Морской бой, 980B - Марлин, 1075C - Ладья возвращается домой
Problem 3 day 1 ioi 2018
I surely don't remember some good problems at the moment, but some that came to my mind right now are https://szkopul.edu.pl/problemset/problem/URPMk7vthz60i1J3MT3XbIIO/site/?key=statement from POI (by Radewoosh iirc), http://mirror.codeforces.com/contest/913/problem/G from Hello 2018 (by YakutovDmitriy), hard from TCO finals about worm decomposing grid and this one from AGC https://atcoder.jp/contests/agc024/tasks/agc024_e
I liked 1012F - Паспорта.
I think that I can suggest some problems from my Open Cup, there were a few nice :D
One of my favorite problems: Cyclic GCDs.
I really liked 1045E - Древняя цивилизация from this year's BubbleCup.
Off-topic but Morphy, if I may ask, what is your number?
by definition, I'm 0, If someone coauthors a contest with me, then she will be 1, and so on.
I enjoyed problem B from the GP of Korea recently, the statement can be found in Petr's blog post here.
Also problem G: Grid With Mirrors from Radewoosh's round. (link to statements: http://opencup.ru/files/oci/gp18/problems1-e.pdf)
Among official ACM ICPC competitions, I would strongly recommend Roads Privatization from Southern Subregional of NEERC, and problems B and C from Moscow Subregional of NEERC.
Considering OpenCup, I really liked problem G from GP of Europe, and most problems from GP of Gomel (especially G and K). upd: Also C from GP of Dolgoprudny.
I didn't write a lot of CF rounds this year, but one problem I really enjoyed solving was Sky Full Of Stars.
Every problem by maroonrk is great.
Apart from that, these problems were very interesting for me.
All problems from IOI 2018
C/G from GP of Poland (Radewoosh)
B/K from GP of Korea
I from GP of Saratov
B from NEERC 2018
Btw, TCO 2018 R2B Med would be in this list if N = 250000 :)
I also enjoyed my problem “Baby Seokhwan” from CSAcademy #84. If hashes were not allowed, it would also be in my list. :(
I found Chemical Table to have a surprisingly nice connection to graph theory
I liked IOI 2018 — Werewolf. Though I knew reach-ability tree, but couldn't solve it in contest time. :(
I virtually participated in IOI 2018 Day2 and I have to say that I really enjoyed solving Highways. Accoring to my rule of thumb, every problem based on this technique (didn't want to spoil too much) is similar and boring, but that one was exactly the opposite!
My favourite problem is 316E3 - Задание на лето It's very interesting to solve it. The problem has a nice idea :D
These problems are very interesting for me:
AGC026 F
APC001 J
2018 Asia-EC Final(GP of Xi'An) A and B.
1070M - Algoland and Berland
923F - Общественный транспорт
Btw how to solve Xian A?
For every w in [1, 30], count how many components there are with edges cost ≤ w then it's easy to compute the answer.
Maintain a dsu of 2n nodes: assume they are nodes in column i and i + 1(let's call the dsu D1). How will the dsu change if we consider nodes in column i + 1 and i + 2(D2)? u + n and v + n are newly connected in D1, so u and v will be connected in D2. If u and v are already connected, the edge is useless from now on; otherwise, we will merge two components and they might make a difference to D3. There are only O(n) events.
my code here
[Indonesian Language Problem]
https://training.ia-toki.org/problemsets/45/problems/224/
Such a unique problem for a national contest :').
https://mirror.codeforces.com/contest/986/problem/E
1060D — Social Circles — My mind was blown away when I figured out the solution to this problem.