Indian Computing Olympiad (ICO) Community | CommonLounge

Indian Computing Olympiad (ICO)

2165 members.

ICO is a computing competition, and also the selection process for the Indian IOI team. Non-Indians can also create an account and practice!

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.

discussion

DP On Trees Problem (CodeForces)

This is a DP on Trees problem. Unless I'm mistaken, the question basically requires us to:

Divide the tree into a number of (different) connected subsets of nodes (or sub-trees) in the tree, with at least one of the sub-trees having exactly K nodes. Then, output the number of edges connecting the different sub-trees.

Any hints? The editorial is unavailable unfortunately. :/

EDIT:

Solution here at my blog, if anyone is interested:

Codeforces 440D – Berland Federalization – T00 PR0

Read more…(80 words)

http://codeforces.com/contest/440/problem/D

Category: Indian Computing Olympiad (ICO)

Top comments in this discussion

I am unable to understand the solutions of this problem. Can you please provide similar problems? Maybe solving other problems that require similar technique will help me.

Read more… (27 words)

Read (27 words)

Rezwan ArefinLove Competitive Pro… · 2y

Here is the hard version of the problem - Młodzieżowa Akademia Informatyczna (MAIN)

Same problem, with k <= n <= 3000, So O(n k^2) isn't gonna pass.

Read more… (27 words)

Read more (27 words)

Keshav DhandhaniaIOI medalist. DM me … · 2y

Yes this version of your solution seems essentially the same. And it also seems as general as mine which uses a helper array, i.e. I don't think there are problems that your version without th...

Read more… (116 words)

Read more (116 words)

Show 3 more
comments

NaN.

discussion

Triangle Equality (IOITC 2013 Test 3)

This seems to be quite an interesting problem from IOITC 2013.

Problem in Short: You are given N distinct points on a plane where distances are measured using the Manhattan metric. Find the number of ordered triplets of distinct points (A;B;C) such that the sum of distances from A to B and B to C is equal to the distance from A to C.

I have been trying this problem for quite some time but unable to come up with a solution to pass the following constraints: N<=10^5 and |xi|<=10^9 , |yi|<=10^9.

Some hints to get me unstuck would be highly appreciated. Thank you.

Read more…(105 words)

Category: Indian Computing Olympiad (ICO)

Top comments in this discussion

Tanavya DimriA 16 year old compet… · 46w

However I get TLE in last 2 subtasks. O(N*log(N)*log...

Read more… (53 words)

Read more (53 words)

Nirmal ManojIOITC 2017, 2018 · 2y

Instead of taking the center B, can't we sort the co-ordinates and then take the leftmost co-ordinate A while sweeping from right to left.

Then, find the number of co-ordinates with y-coordin...

Read more… (88 words)

Read more (88 words)

Sampriti Panda2y

You can also compress the coordinates and use a normal BIT, which would be much easier.

Read more… (16 words)

Read (16 words)

Show 3 more
comments

NaN.

discussion

Facebook (IOITC 2012)

Problem In Short:

Given two nodes s and t in a weighted graph and Q queries to handle.

For every query you are given an edge to remove from the graph and you have to compute the shortest path between s and t.

Queries are independent, that is after you handle one query, reinsert the edge for subsequent queries.

N <= 7000, M <= 50000, Q <= 10000

(Please provide some hints, I'm unable to think a better solution than O(NM log N))

Read more…(83 words)

Category: Indian Computing Olympiad (ICO)

Top comments in this discussion

Mohammad Zaid46w

Full Solution:

At first get the shortest path tree rooted at S using Dijkstra.Now what we observe is if those edges w...

Read more… (338 words)

Read (338 words)

Swetanjal DattaIOITC 2017 · 2y

I am still unable to figure out the solution from Keshav's Hints. Would be grateful if someone expanded those hints.

Read more… (20 words)

Read (20 words)

Pradipta BoraAspiring Astrophysic… · 2y

Thanks.

I'll add hints to problems that I've solved (the few ones that I could manage :P).

Read more… (17 words)

Read (17 words)

Show 1 more
comment

NaN.

discussion

Asking for interesting IOITC problems!

Hi,

I've been doing some past IOITC problems for a while now, but due to lack of time before TC I started only from 2014 onwards. I was wondering if there are some more interesting, non-trivial problems from before 2014 besides the one I tried, Facebook, 2012. Would be great help if you named a few!

Thanks!

Read more…(57 words)

Category: Indian Computing Olympiad (ICO)

Top comments in this discussion

Keshav DhandhaniaIOI medalist. DM me … · 46w

I think the tree question was this: for each path in the tree, compute the sum of kth power of the sum of weights of edges...

Read more… (37 words)

Read (37 words)

Tanavya DimriA 16 year old compet… · 46w

https://www.dropbox.com/sh/3dpr9sknbu0ufbj/AAADGzJAclywaySuizHfLQC4a/Prelims%202010?dl=0&preview=code.pdf

Hints for Binary Codes problem please. Got a few tri...

Read more… (20 words)

Read more (20 words)

Keshav DhandhaniaIOI medalist. DM me … · 46w

Binary Codes is definitely my favorite IOITC problem (quite tough!).
Think there was a nice scheduling problem in one of the finals, where you had to find a day to send a ...

Read more… (144 words)

Read more (144 words)

NaN.

discussion

D - Array (IOITC 2015, Final 3)

Read more…

DArray (EN).pdf

https://dropbox.com/s/948owvukmia25ja/DArray%20%28EN%29.pdf?dl=0

Category: Indian Computing Olympiad (ICO)

Top comment in this discussion

Tanavya DimriA 16 year old compet… · 48w

Any hints? Seems like an annoying problem of pattern analysis, but if its more than just that, I would really like to know!

Read more… (23 words)

Read (23 words)

NaN.

discussion

Monster Challenge (IOITC 2015, Final 2)

Read more…

MonsterChallenge (EN).pdf

https://dropbox.com/s/dj4m823ump3eyhp/MonsterChallenge%20%28EN%29.pdf?dl=0

Category: Indian Computing Olympiad (ICO)

Top comment in this discussion

Where can I find hints or tutorial... :)

Read more… (8 words)

Read (8 words)

Load More