Morphy's blog

What was your favourite problem in 2018?
By Morphy, history, 6 years ago, In English

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.

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

Comments Comments (47)
| Write comment?
»
6 years ago, # |
  Vote: I like it -34 Vote: I do not like it

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.

→ Reply
»
6 years ago, # |
← Rev. 33   Vote: I like it -40 Vote: I do not like it

Well, 1087C - Connect Three 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

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

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.

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

    "In some other world, today is Christmas."

    In our world, today is Christmas! :D

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

Karen (one-word problem) https://codeforces.net/contest/869/problem/A

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

Lunch Queue

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

Problem 1 Day 1, IOI 2018 — Combo

Because.. Why not? :P

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

CBFEAST of course! Such a simple algorithm with powerful applications!

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

    Please tell how to solve it then :P

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

      (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.

      → Reply
»
6 years ago, # |
← Rev. 3   Vote: I like it +1 Vote: I do not like it

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.

→ Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

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

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 - Logical Expression, 965B - Battleship, 980B - Marlin, 1075C - The Tower is Going Home

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

Problem 3 day 1 ioi 2018

→ Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it +26 Vote: I do not like it

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://codeforces.net/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

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

I liked 1012F - Passports.

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

I think that I can suggest some problems from my Open Cup, there were a few nice :D

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

One of my favorite problems: Cyclic GCDs.

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

I really liked 1045E - Ancient civilizations from this year's BubbleCup.

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

Off-topic but Morphy, if I may ask, what is your number?

→ Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 2   Vote: I like it +55 Vote: I do not like it

    by definition, I'm 0, If someone coauthors a contest with me, then she will be 1, and so on.

    → Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it +20 Vote: I do not like it

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)

→ Reply
»
6 years ago, # |
← Rev. 3   Vote: I like it +25 Vote: I do not like it

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.

→ Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it +43 Vote: I do not like it

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

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

    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. :(

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

I found Chemical Table to have a surprisingly nice connection to graph theory

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

I liked IOI 2018 — Werewolf. Though I knew reach-ability tree, but couldn't solve it in contest time. :(

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

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!

→ Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

My favourite problem is 316E3 - Summer Homework It's very interesting to solve it. The problem has a nice idea :D

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

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 - Public Service

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

    Btw how to solve Xian A?

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

      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

      → Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

[Indonesian Language Problem]

https://training.ia-toki.org/problemsets/45/problems/224/

Such a unique problem for a national contest :').

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

https://codeforces.net/contest/986/problem/E

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

1060D — Social Circles — My mind was blown away when I figured out the solution to this problem.

→ Reply