lis05's blog

By lis05, 22 months ago, In English

Any problems from any platforms are welcome!

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

| Write comment?
»
22 months ago, # |
  Vote: I like it +18 Vote: I do not like it

Probably this: https://www.spoj.com/problems/WM06/

The only time I've read an actual full paper to solve a problem.

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

    I think this will be one of the hardest problems I ever solved, only if I solved it (Same problem is in BOJ Ruby 1 — I tried for some days and just gave up)

»
22 months ago, # |
  Vote: I like it +2 Vote: I do not like it

Legends will say, I made a longer "template".

»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

This one from this year's advent of code: https://adventofcode.com/2022/day/22.

»
22 months ago, # |
Rev. 3   Vote: I like it +1 Vote: I do not like it

https://www.acmicpc.net/problem/25799 — The task where I had to copy paste a full Reeds-Sloane template and precompute at least 40 first entries. (and also a graceful one where I sniped first solve from aeren)

»
22 months ago, # |
  Vote: I like it +49 Vote: I do not like it

At 2772 lines, Making a Tangram from IEEEXtreme 14.0 (text, I think) is the longest .cpp file in my CP directory.

However, it's full of lines like this

It's autogenerated, probably because the actual solution was too slow, but the number of possible inputs is only 62. Also, IEEE being IEEE, I can't verify that this solution was actually submitted and got AC. In any case, it's probably not what you mean.

The next longest at 1421 lines is 1574F - Occurrences, submission: 186823042. But most of it is just someone else's polynomial library, so that is also probably not what you mean. The third place at 1405 lines goes to 1613F - Tree Coloring with exactly the same deal as the last time.

Skipping over some more files that are generated code or contain a massive external library, at 552 lines comes D-Dart, submission from CodeChef NOV19A. This beast is an implementation of dynamic CHT with weird circular arcs and a ton of weird corner cases.

CodeChef Long Challenge (RIP) takes the second place as well. At 512 lines I have Panic! at the Disco, submission from NOV20A. There is a ton of algebra (including field extensions!), but as far as I can tell no huge chunk that I didn't write.

More honorable mentions:

  • 447 lines for Tort from Estonian Open 2019
  • 443 lines for RB2CNF from CodeChef NOV20A
  • 435 lines for the 6th problem from HackerRank Week of Code 34 (probably, can't verify)
»
22 months ago, # |
  Vote: I like it +10 Vote: I do not like it

Snake matrix

»
22 months ago, # |
  Vote: I like it +5 Vote: I do not like it
cd contests/codeforces
wc -l **/code.cpp | sort -rn | head -2
wc -m **/code.cpp | sort -rn | head -2

Both give 1137F

»
22 months ago, # |
Rev. 2   Vote: I like it +23 Vote: I do not like it

Ruby 1 group contains the shittest hardest problems rated in Baekjoon Online Judge. Ruby 2 group isn't too different either. Judging from that...

I think the problem from GyojunYoun about representing an integer as the sum of three palindromic integers required the most amount of pure implementation. I took 900 lines + 23k code to complete it and still I'm in one of the shorter codes. No templates, no complicated algorithms. Just pure math, implementation and casework. But it wasn't the hardest problem ever, since I can just type the paper, and someone told me the incorrect case from the paper.

Other problems in the candidate:

  • BOJ. Query on a Sequence 34: I think xiaowuc1 sent me this. I have 17.5k and 650 lines, counting the 250-line-ish suffix array template, but I think it's long enough without it. I also did some parts naively and I think my code has a countercase, so it should be longer. It's also algorithmically very interesting. Highly recommend!
  • Korean IOI TST 2021 Communication: I was one of the organizers so I can share my experiences. Basically we were brainstorming random stuff and the professor came up with this. I thought for a while and replied this is not a good idea, but GyojunYoun became silent for a week and at some point just brought some 500-line-ish data structure hellhole. Why??? Anyway this problem is a monster in any aspect of difficulty. Fortunately, my implementation is short and concise — 400+ lines and 9.3k
  • GP of SPb. Machines on the Moon: It's a cute algorithm riddle, but implementation is not cute at all, especially debugging it was an absolute nightmare. 300+ lines and 9.5k
  • GP of Gomel. One Goal: Personally I recall this as quite doable, but I have 400+ lines and 9.2k without any template, so maybe it was something.

I think there are more disgusting problems in the BOJ but unfortunately I couldn't solve all of them :)

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

This one on AtCoder (which my friend solved in 50 lines): https://atcoder.jp/contests/abc124/tasks/abc124_d (I used 4 cases, which amounts to about 250 lines).

I guess I'm just not smart enough to think about code-efficient solutions to a problem. :(

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

Superpiece from EGOI2022. After trying something smart and modulary for a similar problem at a similar competition, and failed miserably, I just generated every possible if case and coded separately for every one of them.

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

Another challenge would be to code-golf these solutions :)

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

Not counting solutions where I hardcoded a bunch of numbers into the source code, it's this monstrosity. Problem Game Simulator from Round 2. Most annoying problem I've ever solved.

https://www.bubblecup.org/Content/Media/Booklet2019.pdf

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

The worst thing you could have to do is to code like 200 lines for a 7 marks subtask at some IOI style contest ):

»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Among CF problems, it's apparently 1140G - Double Tree, coming at 479 lines. That one has some redundancies though, so it's about 450 realistically.

However, I remember writing 903 lines for a local OI-style problem (Moscow Open Olympiad 2020-2021, long qualification stage, problem D). That was kinda painful, but entertaining in its own way.

What's more, I only got ~70pts for it :)

»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

https://codeforces.net/gym/100490/problem/I: 600 lines of code, 100+ submission attempts.

Later I read author's solution, which is veeery short :\