Fork512Hz's blog

By Fork512Hz, 7 months ago, In English

Hello Codeforces!

Solving 5 problems in Educational Codeforces Round 164 (Rated for Div. 2) gave me an unexpected +125 and I leaped across *1800 right into the lower bounds of purple. This means I am finally touching the eligibility to take part in contests with many of the brightest competitive programmers!

Within the 3 months after registering my account, I have learned many new techniques, with the most representative being modular inverse, segment tree with lazy propagation, fenwick tree and Tarjan's algorithm. I really believe segment tree is something like "Welcome to the realms of div.1!" However, my rating revolved around 1790 and was incredibly stable and I doubted if I was improving. But in several training sessions and VPs I managed to do well. Never mind, CM has come, and I finally start to believe I can go on in CP and reach for my goal in an ICPC regional. The next step is to defend CM, and I'm planning to learn:

  • More STL
  • KMP and AC automaton
  • Decomposition and Mo's algorithm
  • Maxflow and Mincut: Dinic's algorithm
  • Euler's sieve
  • Matching on a bipartite?
  • Suffix array of a string?
  • Fast Fourier Transformation?
  • Heuristic searching and pruning techniques?
  • More ad-hoc constructive problems
  • More ad-hoc dp problems

Fun fact: Div 1+2s finish at 1:35AM in China, so I did not register for CodeTON 8 because I would get up early to enjoy cherry blossoms the next day, but when upsolving I solved ABC1C2, skipped D and took down E within 90 minutes and the trip cost me 2 TON...

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

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

Great Work man. Any suggestions for newbie please?

  • »
    »
    7 months ago, # ^ |
      Vote: I like it -18 Vote: I do not like it

    Focus on Greedy and Math Problems, Wish you the best!

»
7 months ago, # |
  Vote: I like it +1 Vote: I do not like it

your graph shows really nice progress how did u train ? also how did u handle editorials

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

    chinese do not train, chinese just EXIST

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

      if i had realized he was chinese i would'nt have asked

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

    What does "handle editorials" mean? Basically I upsolve problems up to Blue difficulty label(CSP-S+ ~ Provincial selection-) on Luogu. If I stare at the statement for 20mins and have no idea I simply go to the editorial.

  • »
    »
    7 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Well, what i wonder is how does both of you progress so fast? You are both amazing though.

    • »
      »
      »
      7 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      i guess the same thing i just choose problems way too hard read their editorials and never learn aglos or data structures

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

my congratulations!

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

Congratulations!

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

You must have a very strong mathematical background. It is not possible to reach CM so soon without already being a pro at maths.

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

    Actually I major in Computer science, and some of the required courses include:

    • Data structure
    • Probability and Statistics (I completed this last term so some probability-based problems are easier for me now)
    • Basic discrete math (Sets, graphs, combinatorics)

    I've tried CP in 8th grade as well, and some of the easier techniques are remains from that.

»
7 months ago, # |
  Vote: I like it -16 Vote: I do not like it

Congratulations!
Purple is 1900-2199
https://codeforces.net/blog/entry/20638

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

what resources you depend on while learning a new topic ?

»
7 months ago, # |
  Vote: I like it +5 Vote: I do not like it

How did you practice? how did you choose your problems? was it randomly? also what advice you would give me so i can reach cyan in the next 2 months

»
7 months ago, # |
  Vote: I like it +27 Vote: I do not like it

I believe the choice of some of these algorithms is a bit hasty. I don't think I ever used an FFT, suffix array, Dinic algorithm, Mo algorithm in a Codeforces round, and I left the domain of CM many years ago. Structured understanding of what's out there in C++ STL and what is not is more important, I guess. Dp techniques (again, not very advanced) are also of use.

  • »
    »
    7 months ago, # ^ |
    Rev. 2   Vote: I like it +15 Vote: I do not like it

    Thank you for your suggestion. In fact, experienced contestants agree that FFT and suffix array are a bit too advanced for me now, but in the technique-dense Chinese NOI/NOIP, knowing Network Flow and Mo's do make sense. At least for the first 3 topics, their template problems are labeled BLUE difficulty on Luogu.

    Maxflow: P3376 <TEMPLATE> Maxflow

    AC automaton: P3808 AC automaton (Easy version)

    Mo's: P2709 Little B's queries

    Since many problemsetters of XCPC in China have a strong NOI background I believe learning these are of use. But I do agree how to model a problem into a template is the more important part.

    Also: GL World Finals!

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

      Well, I'm only discussing Codeforces specifics. If you're preparing for the Chinese olympiads as well, the priorities should be a bit different.

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

Congrats! And I solved 5 problems in that round too and gained +135 rating. It feels great!

  • »
    »
    7 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    how do you pick problems to practice ? do you practice on other judges too?

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

Congratss! Any suggestions for Constructive Problems? I have been doing CP for 4 years now (although not regular) but I still have no clue how to tackle them.