Fype's blog

By Fype, 19 months ago, In English

I gathered up a lot of Segment problems :) -->

upd1 : more segment :D
upd2 : now there is e-olymp problems. thanks to dmkozyrev.

codeforces :
Xenia and Bit Operations
Knight Tournament
Bash and a Tough Math Puzzle
Pashmak and Parmida's problem
Enemy is weak
Circular RMQ
Lucky Queries
XOR on Segment
Sereja and Brackets
Ant Colony
Babaei and Birthday Cake
A Simple Task
Frogs and mosquitoes
Copying Data
Lucky Array
Vika and Segments
Misha and Permutations Summation
Little Elephant and Inversions
One Occurrence
Yaroslav and Divisors
New Year Domino
On Changing Tree
Infinite Inversions
Interesting Array
Alphabet Permutations
DZY Loves Fibonacci Numbers
Eyes Closed
Tree and Queries
Valera and Queries
Nikita and stack
Linear Kingdom Races
Camping Groups
Little Girl and Problem on Trees
Domino Principle
Water Tree
Propagating tree
Kefa and Watch
Jeff and Removing Periods
Drazil and Morning Exercise
Tree or not Tree
The Child and Sequence
Encryption (hard)
Hot is Cold
Developing Game
Drazil and Park
Board Game
The Untended Antiquity
Danil and a Part-time Job
More Queries to Array...
Cow Tennis Tournament
Coins Exhibition
Till I Collapse
Serge and Dining Room
Subarray Sorting
Physical Education Lessons
Alyona and towers
Sasha and Array
New Year and Old Subsequence
Timofey and our friends animals
Yash And Trees
Periodic RMQ Problem
Leha and security system
Vladik and Entertaining Flags
MEX Queries
The Bakery
Nauuo and Bug
Duff in the Army
Fools and Roads

codeforces gym :
Letter Array
Hacker Cups and Balls
Colonial Mansions
Colors Overflow
Running a penitentiary
Subsequence Sum Queries

spoj :

BGSHOOT — Shoot and kill
HORRIBLE — Horrible Queries
GSS1 — Can you answer these queries I
GSS3 — Can you answer these queries IV
GSS5 — Can you answer these queries V
KGSS — Maximum Sum
POSTERS — Election Posters
BRCKTS — Brackets
LITE — Light Switching
KQUERYO — K-Query Online
CNTPRIME — Counting Primes
IOPC1207 — GM plants
ADACABAA — Ada and Species
DQUERY — D-query
PATULJCI — Snow White and the N dwarfs
ADAGF — Ada and Greenflies
ADATREE — Ada and Trees
Mass Change Queries
PRMQUER — Prime queries
NAJ0001 — Divisible Number Sum
DCEPC11I — Impossible Boss
PERMPATT — Check 1324
THRBL — Catapult that ball
MON2012 — Monkey and apples

lightoj :

1082 — Array Queries
1080 — Binary Simulation
1112 — Curious Robin Hood

e-olymp :
In the Country of Unlearned Lessons
In a country of Unlearned Lessons 2
The kid who learned to count
Investigation by koloboks
Cheburashka and Crocodile Gena
Винни-Пух 2
Карлсон, который живет на крыше
Ну, погоди!
Three from Prostokvashino
Трое из Простоквашино 2
Трое из Простоквашино 3
Золотой ключик или приключения Буратино
Приключения кота Леопольда
Adventures of Dunno and His Friends
38 попугаев
Возвращение блудного попугая
Сказка о попе и работнике его Балде
you can use google translate for the problems written in russian.

any suggestion ? :D

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

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

any suggestion ? :D
Remove "advance data structures" tag.
Segment tree is way away from advance data structures.

19 months ago, # |
  Vote: I like it 0 Vote: I do not like it
19 months ago, # |
Rev. 3   Vote: I like it +8 Vote: I do not like it

One more: 1172F - Nauuo and Bug

BTW, I think it would be better if you sort these problems by difficulties, or classify them into different types, like this blog.

And do you choose all the problems which are solvable by segment tree, even if there are both faster and easier solutions? I've noticed that 516C - Drazil and Park only needs RMQ, and 516D - Drazil and Morning Exercise's official solution doesn't need any advanced data structures (I don't think union-find-set is), however, I have a solution using segment tree with worse complexity ($$$O(qn\log^2 n)$$$) but less observation, does this make it a segment tree problem? Or there are faster segment tree solutions?

UPD: seems that these two problems are from this blog.

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

    Thanks, the problem added to the list.

    When you are unfamiliar with the segment tree it's better to solve the problem using the segment tree even if there is a better time-complexity because you will understand different usage of the segment tree. (At least that's what I believe)

    I never came across a faster solution for 516D.

19 months ago, # |
  Vote: I like it -11 Vote: I do not like it


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

thank you. Its near to usless to me. Thank you.

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

Can anybody help me with the SPOJ-PERMPATT problem? I saw people building segment trees for finding minimum element but there should be one more idea i cannot catch.

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

Another problem can be solved by Segment Tree: 1070C - Cloud Computing