Problem Topics - Codeforces

№	Пользователь	Рейтинг
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

№	Пользователь	Вклад
1	cry	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	Dominater069	153
9	nor	153

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:

aho

automat

belman-ford

bfs

bfs-grid

big

binary_search

bits

bitset

bridges

brute-force

centroid

coloring

combinatorics

constructive

dfs

digits

dijkstra

divide_conquer

divisors

dsu

euler_function

euler_tour

factorization

fenwick

fft

flow

flow-matching-like

floyd-warshall

friedvaldAlgorithm

game_theory

gauss

geometry

graph

greedy

hash

hull

chess

implementation

inclusion-exclusion

interactive

isomorphism

josephus

KMP

lca

lcs_subsequence

lct

lis

matching

matrix

matrix_exponentiation

mcmf

median

meet_in_middle

next

np-hard

number_rectangle

number_theory

observation

oeis

offline

palindromes

patter-matching

permutations

persistent_segment_tree

preprocess

prime-count

prime-testing

probability

recursion

RMQ

rope

scc

segment_tree

sequences

sieve

simulation

sorting

spanning_tree

spfa

sqrt

stl

strings

suffix_array

ternary_search

topo

treap

tree

tree-dp

trie_bit

trie_string

TSP

two-pointers

wavelet_tree

Zfunction

2SAT

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:

It is very interesting
There is nothing, or low number of problems in the topic
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

Комментарии (119)

Показать архивные | Написать комментарий?

exelover

7 лет назад, # |

Thank You :)

→ Ответить

SYury

+18

http://www.spoj.com/problems/PAIRDIV/ (6) //cyka möbius -_-

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

-Morass-

7 лет назад, # ^ |

Hello, Yes,

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

prudent

6 лет назад, # ^ |

Good day to You too, I'm sorry to ask such a question, but I really couldn't really find where I can submit problem called "8015 — Alice and Bob play Contact" in a division trie_string, because when I go to UVA and insert a value 8015 in a problem id in a Quick Submit, I get a message: "The selected problem ID does not exist.", what is its actual id by which I can submit the problem?

good day to you,

seems to be on Live Archive

Well, can You please help me out with one more issue, when I try to register to icpcarchive.ecs.baylor.edu, it gives me this error, how to fix it?

Sorry — no idea what the error means :'(

Magician_Mathematician1

4 месяца назад, # ^ |

Hello there! I know it has been a very long time but I was trying to solve this problem PAIRDIV, and I couldn't solve it using mobius inversion. I managed to solve it in another way though, but I would like to know how to solve it with mobius inversion. Can you help me, please?

VastoLorde95

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

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 :)

kazuma_desu

+10

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

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 ^_^

acraider

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

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

← Rev. 2 →

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

Target2018

what is "big"?

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

Have Nice Day ^-^

SleepyShashwat

I think you mean to say Integer.

Yes, thank you — fixed this :)

sahil070197

I've got a nice problem for tree-dp

Torque and edges

segwit

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!!!

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

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

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 :) ]

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

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 :)

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!!

17_38_98_KB

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?

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 ^_^

Apptica

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

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

Its ok. Thank you for the wonderful list :)

GreenGrape

840D - Destiny is a nice example of a tricky wavelet tree.

usernameson

842D - Vitya and Strange Lesson is another trie_bit problem it might be a good addition since the trie_bit list is pretty small.

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!

Saidbek_Sarimsakov

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

Nickolas

That's what we're trying to do https://e-maxx-eng.appspot.com/

(And many thanks to -Morass- for contributing this list of problems to corresponding articles!)

vatsal

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

nope, seems to be mistake, thank you :)

Tutis

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

bradyawn

Aho-Corasick: http://mirror.codeforces.com/problemset/problem/346/B

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

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

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

Ilnur_the_best

Thank you very much, very interesting:))

kocko

Nice list! Thanks

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

Ghost0fSparta

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.

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!

Thank you for guidance!

sabertooth

Just the thing I want in my semester break vacation!

Thanks A Lot!

soohotiam

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

only a few — unroll "lct".

Thank You! :)

Ahs_58

is problem set arranged in order of ascending difficulty?

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!

unofficial10

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

Good day to you!

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

Fullmetal_Algorithmist

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.

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

HLD is there as part of "LCA"

SinByCos

← Rev. 3 →

Can someone explain what is the solution for this problem? http://www.spoj.com/problems/AMR10J/

I am thinking a dp on tree solution, something like O(N*K^2) but that would be too slow. No clue how the problem tag you mentioned, of DAG, would help. Isn't the graph in the form of a forest, with each tree having only one cycle?

Hints would probably be more appreciated though, seems like an interesting problem. :)

EDIT:

Help no longer needed! Managed to solve it in just O(N) and N is only <= 100. Pretty neat. In case anyone is interested, here is the code: https://pastebin.com/GrvCjSwt

brdy

As I was browsing here this problem caught my eye. I have made not much progress in a week or so other than determining the shape of each component (multiple trees hanging from a cycle).

Could you please explain your dp idea? For example, what does DP[i][j] represent?

Vicennial

Is there a CHT list?

sorry but not :'( Maybe there is something in Number Theory but I wouln't bet on many problems

codeforrest

6 лет назад, # |

Some more easy problems on Josephus : http://www.spoj.com/problems/WTK/ (Easy) http://www.spoj.com/problems/DANGER/ (Easy) http://www.spoj.com/problems/POCRI/ (Medium) http://www.spoj.com/problems/NG0FRCTN/ (Medium)

thank you very much. I wanted to reply after update yet sadly I'm getting 504 Gateway Time-out when trying to update for more two week already so sorry, and I hope it will get better once :'(

It's my pleasure to get a reply from you! Great efforts in Compilation, really useful.

Warawreh

Bridge Problem : http://mirror.codeforces.com/contest/1000/problem/E

des1997

the question ada and power mentioned in friedvald algorithm section is giving wa for test file 15. please give some insights

I have an Idea for you if you can do it.

I love solving problems from CF so when I open any category I search for CF problems and start solving them.
So my idea is to divide the problems in each category by the problem's website to make it easier to navigate.

Example :

kowalsk1

What does "L-mex" stand for in the segment tree section?

not much sure now — yet imho firstly there is some check with "L" parameter... and then probably getting "MEX" (minimal unused value).

dunno — sorry :P

Sasuke-u

-8

hey, Can somebody help me with this problem Ada and Zoo

thanks :)

I would recommend you to take peek onto Steiner's Tree -> That shall be a great start ^_^

Good Luck

Thank you!

GuillermoFrancella

-31

You should erase most categories from that list, because they are useless. Problemsetters no longer know what most of those categories are.

RMQ? KMP? LCA? What's all that? Might be some names for prehistoric problem solving techniques. All you need today is math, some thinking and three lines of code.

drinkWater.

I wish there were tutorials and solutions gathered for these problems :D

ProximaCentauri

What do you mean by hard/weak children? (in category 'topo', problem : spoj — 'CODESPTI')

well it was just kind of hint that in my approach you should distinguish nodes by their "shape" (which recursively applies)

phibrain

This one link could be interesting for persistent segment tree, for me it was...

5 лет назад, # |

Please anyone give the link for problem 4956 [LA] . category : friedvaldAlgorithm

5 лет назад, # ^ |

the link shall be here

nks43

I wrote a script to save all these questions along with their categories in a CSV file using python. Here is Pastebin link if you would like to use it.

art-hack

I have saved your code on one of the repls, so you can just run and get the file directly (Link).

Thanks a lot! I shall add this link to my blog post if you have no problem.

smhh22

I think 576C is the most classical problem for MO's algorithm. So that's good to add it.

En_deavour

+11

-Morass- Can You say the total numbers (digit) :p of the problem listed here :D :D

qingczha

sorry my bad

Olympia

Thank you so much! I will definitely use this to structure my training. I appreciate all of the div 1 codeforcers helping out the rest of us!

idgaf

Hey -Morass- I've been trying to solve SPOJ — JUSTAPAL from the palindrome category using hashing + binsearch and then using nlogn SA + LCP + RMQ to get first and second mismatches and do some swaps. However I'm still getting TLE. Is there something to take into account for getting a faster solution. Can you please share a hint or your code about this one? Thanks! :)

Hmm okkey not sure whether BS + Hashing wouldn't time-out actually..

Anyways SA+LCP+RMQ seems to be right solution. Guess with this (you can check your local build-time, whether it is not too slow already --> it is NlogN so it shall be slowest part I guess, but shall not time-out: So try it/check it out), it shall be linear: For each possible "middle" check how far you can have palindrome -> then "repair" the next part and check whether the palindrome can continue .. and possibly whether it was "repaired" by swaping the next broken part and possibly check how far you get next....

So in the end (omitting build part): There shall be (+/-) 2N such processes, with at most 3 RMQ questions and a few peeks to array: So this part shall be linear and hopefully shall not time-out.

So if this is your approach, then it shall be fast enough (if there is no mistake :O )

Naithani

-Morass- could you plz include scanline algorithm problems like this https://www.codechef.com/problems/LAZER

Mohammad_Yasser

I was searching for randomization problems, but couldn't find a randomization category here. :( After expanding the categories and searching for "random", I found 9 problems, but I think it deserves its own category.

There are some problems that have very nice randomized solutions, and sometimes they aren't the intended solutions, but I believe randomization can sometimes be very powerful and interesting.

If I remember some of them I'll add them here. Kindly if anyone has such problems, post them too.

I found the following blogs that have some randomization problems/tutorials:

On a separate note, I believe it'll nice if each topic has its list of tutorials too. Most have easily-reachable nice tutorials, but some do not, and some tutorials are much better than others, so I believe it'll be nice if there's like a list of high-quality tutorials per topic, along with short comments if needed.

Casio991ms

Can you please arrange them in groups? for example, graphs, geometry etc.

CoderAnshu

4 года назад, # |

FFT Questions :

https://mirror.codeforces.com/problemset/problem/1096/G

https://mirror.codeforces.com/problemset/problem/632/E

https://mirror.codeforces.com/problemset/problem/1251/F

I found these nice ..

You may add these too

blitzkrieg639

Commenting to save the blog! Thank you!

Colossus20

4 года назад, # ^ |

You can add it to favorites, just click the star at the end of the blog (near the contribution count).

Saksham_2000

thanks a ton :)

-grace-

Thanks a lot for these! These are really useful for beginners like me.

AmirrzwM

hi and thanks for amazing blog post -Morass-. can you explain your segment Tree solution for 915E please?

Hot_Potato

whats is total number of problems here? Has anybody counted ?

zed_b

2870

Spoiler

// Number of direct paragraph child elements inside OP's spoiler tags
$x(`//div[@class='topic']//div[@class='spoiler-content']/p`).length;

Akif_Azwad

+82

"Unable to parse markup [type=CF_MARKDOWN]"- Is this the actual post or is the link broken??

+21

Hey ye: no idea what is wrong (not much verbose x( )

Here is the source to the post -- so you might either refer to it, or if anybody sees any visible failure — you can ping me and I'll try to fix x)

Have nice day ^_^

RetiredRmdanJr

The link gives me this error -_-

Error, this is a private paste. If this is your private paste, please login to Pastebin first.

Could you solve it, please?

yayx -- Might be hopefully fixed :D

Mac_prime

Thank you for your response got the pastebin link

Evirir

+14

The problems aren't enclosed properly in the spoiler boxes currently. -Morass-

Sadito10

Isn't there a topic for Heavy-Light-Decomposition? I haven't found it

JurCai

3 года назад, # |

I can't think of the solution to the problem "CODESPTI" in topic "topo". Could someone tell me how to do it?

Summer-Catchers

3 года назад, # ^ |

Hint

Seriously

Thanks!

hydra_cody

2 года назад, # |

how to approach graph modeling problems?

cajolery

23 месяца назад, # |

That's really great :)

peek4b00

20 месяцев назад, # |

Great problemset

Maruf39237

10 месяцев назад, # |

some problem links are not working....

donpaul2718

4 месяца назад, # |

thanks

gupta.102

2 месяца назад, # |

Блог пользователя -Morass-