International Olympiad in Informatics

4925 members.

Prepare and practice for IOI + get better at competitive programming + learn algorithms in a fun way with animations and videos!

Invite Members

Show community info

Ask a question or start a poll…

Link

Poll

CommonLounge is a community of learners who learn together. Get started with the featured resources above, ask questions and discuss related stuff with everyone.

NaN.

tutorial

Segment Trees

Motivation: Given an array of N numbers, you need to support two operations. Operation 1: find-min(i, j) = return the minimum value in array[i ... j]. Operation 2: update(i, v) = update the value at array[i] to v. Solve the problem for N <= 10^6, number of operations <= 10^6.

To solve the above problem, both the operations need to run in O(log N) time, but using an naive array gives O(N) run-time for operation 1 (and O(1) run-time for operation 2). So how do you solve the problem? Read on. :)

Video tutorial: This is a superb tutorial, giving the motivation, walking through example, and going step-by-step through the pseudocode.

Read more…(295 words)

Category: International Olympiad in Informatics

Top comments in this discussion

Young KidYoung kid tryin' to … · 2w

Efficient and easy segment trees

Non-recursive Implementation of Range Queries and Modifications over Array

Read more… (14 words)

Read more (14 words)

another great tutorial Segment Trees

Read more… (5 words)

Read (5 words)

Himanshu Sharma2y

superb video :D _/\_

Read more… (4 words)

Read (4 words)

Show 9 more
comments

NaN.

discussion

Detecting Molecules (IOI 2016)

Discussion for the IOI 2016 problem Detecting Molecules.

Read more…(8 words)

http://comp.nus.edu.sg/~irving/ioi2016/day1-1-en.pdf

Category: International Olympiad in Informatics

Top comments in this discussion

Not fast enough, you should scan through all i but binary search for each corresponding j

Read more… (16 words)

Read (16 words)

Keshav DhandhaniaIOI medalist. DM me … · 3y

The below is a solution one hint at a time. Use the hints wisely!

Hint 1:

Read more… (128 words)

Read more (128 words)

NaN.

discussion

[SPOJ AGGRCOW] Aggressive cows!

Can someone please give me some hints to solve this problem. Thanks in Advance!!

Read more…(14 words)

Problem AGGRCOW

http://spoj.com/problems/AGGRCOW/

Category: International Olympiad in Informatics

Top comments in this discussion

Thicc

Read more… (1 word)

Read (1 word)

Chennupati Harish29w

this problem is a nice one we need to arrange the cows in such a way that

distance between them ...

Read more… (155 words)

Read (155 words)

Rahman Moshiur30w

Actually it's a formal binary search approach. If ok function returns false for any mid value that means for taking "mid" maximum gap we can't put C cows. As we know number of cows we can put ...

Read more… (67 words)

Read more (67 words)

Show 38 more
comments

NaN.

discussion

Solving linear recurrence using matrix exponentiation

Read more…

Solving Linear Recurrence for Programming Contest

http://fusharblog.com/solving-linear-recurrence-for-programming-contest/

Category: International Olympiad in Informatics

Top comments in this discussion

Shivam Kumar43w

Yeah same here

Read more… (3 words)

Read (3 words)

Rohit Upadhyaya1y

I'm not able to access the blog linked in this post, I was able to just a few days ago. It says my IP address on the server has been blacklisted.

Anyone else having the same problem?

Read more… (37 words)

Read more (37 words)

NaN.

discussion

Hospitals: IOITC 2015

Given N towns in a country of which P have hospitals and M bidirectional roads connecting them. Find the minimum distance of each town that does not have a hospital to the nearest hospital.

N, M <= 10^5 and P <= N.

Using Floyd Warshall or Dijkstra will push it to N^3 or N^2 log N. How to do it within the limits?

Read more…(63 words)

Category: International Olympiad in Informatics

Top comments in this discussion

Keshav DhandhaniaIOI medalist. DM me … · 2y

I think the second hidden block will answer your question - let me know if you have doubts after reading that!

Read more… (21 words)

Read (21 words)

Pradipta BoraAspiring Astrophysic… · 2y

Keshav,

What I am worried about is the constriant. If we do Floyd Warshall, it won't work. Djkstra with heap for all sources too s...

Read more… (50 words)

Read (50 words)

Keshav DhandhaniaIOI medalist. DM me … · 2y

Lets see if you can get it with this 4 word hint.

Try to not read this next hint, it gives it all away...

Read more… (82 words)

Read more (82 words)

NaN.

discussion

Topics which will be discussed in IOITC

I got selection to IOITC this year. I would like to know more about the camp and topics which will be discussed there. Will they teach the whole syllabus of IOI in the camp within a span 10 days? What all should I learn before attending the camp in order to understand everything discussed there in a more better way?

Read more…(60 words)

Category: International Olympiad in Informatics

Top comments in this discussion

Keshav DhandhaniaIOI medalist. DM me … · 2y

I see. I like the Stack Overflow link Shreeyash provided. I also like this tutorial on Codeforces: Counting problems from A to B.

Here are my thoughts and observations on it:

You should think of digit DP problems as j...

Read more… (296 words)

Read more (296 words)

Keshav DhandhaniaIOI medalist. DM me … · 2y

The best bit manipulation tutorials are Fun with Bits – topcoder and Bit Manipulation - HackerEarth. Although I haven't tried any of these problems myself, HackerRank seems to have a good collection of problems on bit manipulation.

I find bit manipulation to be useful quite rarely. B...

Read more… (89 words)

Read more (89 words)

Shreeyash Gotmare2y

It is dynamic programming on the digits of a number. It involves problems like this one Codeforces problem 489C.

Also, this might be useful : http://stackoverflow.co...

Read more… (27 words)

Read more (27 words)

Show 4 more
comments

Load More