-Morass-'s blog

By -Morass-, history, 4 months ago, In English,

Good Day to you!

I've been asked to make some topic-wise list of problems I've solved. Even though I couldn't involve all problems, I've tried to involve at least "few" problems at each topic I thought up (I'm sorry if I forgot about something "easy"). I've alredy made such list once anyway I've tried to include more problems now — so here it is:

automat
belman-ford
bfs
bfs-grid
big
binary_search
bits
bridges
brute-force
combinatorics
constructive
dfs
digits
dijkstra
divide_conquer
divisors
dp
dsu
euler_tour
factorization
fenwick
flow
flow-matching-like
floyd-warshall
friedvaldAlgorithm
game_theory
gauss
geometry
graph
greedy
hash
hull
implementation
isomorphism
josephus
KMP
lca
lcs_subsequence
matching
matrix
matrix_exponentiation
mcmf
meet_in_middle
np-hard
number_rectangle
number_theory
observation
oeis
patter-matching
permutations
persistent_segment_tree
preprocess
prime-testing
probability
recursion
scc
segment_tree
sequences
sieve
simulation
sorting
spanning_tree
spfa
sqrt
stl
strings
suffix_array
ternary_search
topo
treap
tree
tree-dp
trie_string
TSP

Finally if you would like to add some problem to the list — even though I would be glad, please do so only in case of:

  1. It is very interesting

  2. There is nothing, or low number of problems in the topic

  3. You add it in "bigger amount" at once

Thank you.

Offcourse if you have any remarks, questionns or requests, don't hesitate to ask.

PS: I'm sorry but there might be some duplicities. In that case, either report it or ignore it (unless they are in different topics, then it have reason :) )

Good Luck & Have Nice Day

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

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

Thank You :)

»
4 months ago, # |
  Vote: I like it +18 Vote: I do not like it
http://www.spoj.com/problems/PAIRDIV/ (6) //cyka möbius -_-

It seems that you don't like Möbius inversion much.

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

    Hello, Yes,

    I'm not mathematician and it seems slightly like magic to me :'( I find it hard somehow :/

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

Are the numbers in the parenthesis your judgement of how difficult each problem is?

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

    Good day to you,

    yes, exactly as you say. But as it is stated — it is my opinion so it might be "a little bit" off :)

»
4 months ago, # |
  Vote: I like it +10 Vote: I do not like it

I find it funny that there is a topic "oeis". xD

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

    Good day to you,

    well right :D .. it is mostly math.

    It is might be used slightly in "different" manner then normal math problems. I.e. you can brute-force small test-cases only and then "google the rest" .. So math but basically different approach ^_^

»
4 months ago, # |
  Vote: I like it +10 Vote: I do not like it

Can you please tell what are the problems from LA are?? i mean what is LA?? i have never heard of it.

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

    Good day to you,

    sure: LA stands for Live Archive — it is a judge which stores most of the problems from Regional Contests + World Finals

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

      Ok... never came across the acronym before :).Thnx for the prompt reply.

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

what is "big"?

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

    Good day to you,

    This topic stands for Big Integer — so problems with numbers which doesn't fit in 264 :)

    Have Nice Day ^-^

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

I've got a nice problem for tree-dp

Torque and edges

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

are all the questions tough or are some questions easy, how does a pupil like me approach those questions??? I simply want to ask that how do i use this resource for optimum benefit!!!

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

    Good day to you,

    imho there shall be easy questions too. Some of them are marked by a number (by which I've tried to estimate the difficulty). So you might try (firstly) problems marked with lower numbers (lets say lesser/equal 3 or 4)

    Wish you a nice day,

    ~/Morass

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

      thank you for such a quick reply. is the estimate out of 10.

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

        Yes it is out of 10 (even thought — I think I've never used such big number :P) [but again.. it is just estimation, so might not be absolutely correct :) ]

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

          can you give an estimate that what will be my rating like if I solve questions till level a)5 b)6 c)7 d)8(will take a long time to reach here.)

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

            Unfortunatelly it is not much possible imho :'(

            Firstly, even person with lover rating can solve hard problem. It will just take him more time to come-up with solution and/or to code the solution.

            Secondly some problems fit to some people more — so it varies.

            Another thing is that many problems here are algorithmic. So sometime the hardest part might be algorithm itself. It indeed might be hard to code — and even more difficult to come with. On the other hand, it is not that hard to find such algorithm somewhere on google, learn it, code it.. and then it colsts "nothing" when you use it for the second time (even thought It costed many hours for the first time).

            So in my opinion, I can't say it... Anyway if you would be able to do that fast (so it would easily fit into codeforces contest) the rating might possibly probabli be somewhere between purpble to red (the range you told)

            Also note, that codeforces stile problems might be different from "ACM"-stlye problems... and also from some direct-method SPOJ problems.

            So well, sorry this didn't help you much, but that is my opinion :)

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

              No No, infact I WANTED an answer to my silly question but you gave me the answer I NEEDED to progress further, thank you so much!!

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

Sir, what do you think about the book — competitive programming 3 -by steven halim and felix halim? If I solve all the problems mentioned in that book will I improve? If yes, then how much?

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

    Good day to you,

    Well firstly, I've not read the book so not sure if my answer will be "valid". Anyway I know some people who did so (and I've also heard a little bit about it and so on):

    The book introduces most of the algorithms which are considered "basic" so imho it is "almost necessary" to know these algorithms as "ground" for almost any (at least a little bit) advanced skill-level. I heard it is a great book (the algorithms are well described there) so it is worth giving it a try (well you shall learn the algorithm somewhere — so why not from here?). Anyway what I also think is, that it won't ensure you any of the skill-levels: There are many more thinks, which "shuffled" together makes you good at CP and the knowledge of algorithms is "only" (but it is imho important) one of the "carrier pillars".

    Again, I haven't read it and this is just my option :)

    Wish you a nice day ^_^

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

      This one is nice for Z function . https://www.codechef.com/problems/CHSTR

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

        Good day to you

        Thank you very much for suggestion, anyway sadly I'm not able to edit my blog anymore to add it :'(

        Seems I'm getting "504 Gateway Time-out" every time I try so and I'm unable to resolve this problem .. sorry :'(

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

          Its ok. Thank you for the wonderful list :)

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

840D - Судьба is a nice example of a tricky wavelet tree.

»
4 months ago, # |
  Vote: I like it +6 Vote: I do not like it

842D - Витя и странный урок is another trie_bit problem it might be a good addition since the trie_bit list is pretty small.

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

    Good day to you sahil070197 GreenGrape usernameson,

    Thank you for your contriution. Sadly I can't update the blog anymore (due to "504 Gateway Time-out") :'(

    If I would miraculously evade it one day, I'll add those problems,

    Good Luck & Have Nice Day!

»
4 months ago, # |
  Vote: I like it +6 Vote: I do not like it

It would be the greatest help i have ever had on CODEFORCES if you added articles for each type of problems. Because after learning the type of algorithm, the problem list you wrote is the best to deepen it. Anyway thanks a lot BRO!!!.

by the way your post is already is the best profit . . .:)

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

Hello! Why do you have two "Zfunction" tags? Do they serve different purpose?

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

    Good day to you,

    nope, seems to be mistake, thank you :)

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

Add this to geometry: https://icpc.kattis.com/problems/airport Really nice problem :)

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

Auto comment: topic has been updated by -Morass- (previous revision, new revision, compare).

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

    Congrats, I see you managed to get around 504-Gateway Time-out.

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

      Thanx ... I was trying for more than week and now it magicaly worked .. I was really surprised :)

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

Thank you very much, very interesting:))

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

Nice list! Thanks

I also use the Categories section on ahmed_aly's A2 online judge.

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

Auto comment: topic has been updated by -Morass- (previous revision, new revision, compare).

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

Hello sir, I am doing CP for over a year now(though not on CF) and have learnt basic algorithms(those taught in 6.006 class MIT). What according to you should I do to improve my skills?

EDIT:I forgot to mention that nowadays I am giving contests and reading blogs of people on CF and topcoder but I cannot get 100% of what author is trying to say(in editorial or blog):(

Is there anything I can do or should not do at this point of time?

Thank you.

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

    Good day to you,

    Firstly, this is HARD KIND of question, since it is not directly on CP but slightly on "psychology"/"learning" which might be different for different people (so question is whether programmers are the right people to answer this question). Also, as you can see, my progress is not that good so maybe it would be better to ask some red-coder (or nutela).

    Here is the text I typically use for such kind of question so hope you'll find something in it:

    In first place, one need obtain knowledge in basic algorithms: There are many algorithms which are not hard, yet it is hard to do even medium (sometime easy) problems without them. Starting from dfs/bfs/sieve/graph-algos/sorting/....(many many other). So find some way to learn them. Usually, find some good blod (codeforces/geeksforgeeks/some school's lectures/so on..).

    While doing the above, one has to catch some coding/debugging concepts. Afterward it is imho good to do many easy (at most medium) problems to improve coding skills. Even though many people undeestimate this, it is very important to get to phase where you can code what you know (well, it might sound stupid, but many times one know a solution one hour before end of contest, yet he ends coding 10 minutes before end when he starts his 20 minute debugging phase [and both could be significantly reduced])

    As one improves (hopefully), he must start doing harder and harder problems and soon with the harder problems, he must lear also advanced algorithms: Suffix Array/HLD/Segment Trees/...(and many many others) which are usually not "that" necessary for easier problems.

    Also during all phases, it is good (even thougt one spends a lot of time by coding) spend some time by reading:

    a) New algorithms helpful things b) Editorials for what one doesn't know (firstly THINK about the problems and if nothing come, search for solution. Sometime one just find he's "stupid" but many times one discovers "new amazing" techniques)

    Also sometimes it is interesting to peek to solution of others... even (or maybe BEST) after you solve the problem. Sometimes there is much better solution then you came with, sometimes there is something awesome (like algorithmic/or/language trick) which might simplify your futher coding.

    Also sometimes it is good to "measure twice, cut once"... thinking for a while even if you know the solution. Sometime you find improvement, or reduce it by redundant part..

    anyway... solve solve solve ~ that it what I usually do :)

    Good Luck & Wish you a Nice Day!

»
6 weeks ago, # |
  Vote: I like it +6 Vote: I do not like it

Just the thing I want in my semester break vacation!

Thanks A Lot!

»
6 weeks ago, # |
  Vote: I like it +5 Vote: I do not like it

Recently I was learn Link Cut Tree. Have any list of problems set of link cut tree? Help Me to find out.

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

is problem set arranged in order of ascending difficulty?

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Good day to you,

    nope it is not. Some problems mighthave number next_to them, which is estimated difficulty, but it is just "a very wild guess" :).

    Wish you a nice day!

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Strongly Connected Components(SCC) http://codeforces.com/problemset/problem/427/C

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Good day to you!

    Thank you very much. I've (hopefully) updated the topic!

    Wish you a nice day!

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

In your MO part there is a problem(https://toph.ws/p/distinct-dishting). The link has changed. It's now https://toph.co/p/distinct-dishting. If you have listed any other problem from that site I think the link should be updated.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

maybe you forget to include digit dp problem...you can use this.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Did you simply miss HLD or it's there but I can't find it?

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Good day to you,

    HLD is there as part of "LCA"