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
[INOI1201] Triathlon (INOI 2012: India)
Problem in short: There are N people, and person i takes a[i], b[i] and c[i] time to do task a, b, c respectively. Only one person can do task a at a given point of time, and each person must do tasks a, b, c in-order. In which order should the N people do task a, so as to minimize the time at which everyone is done with all of their tasks. N <= 2 * 10^5.
Indian National Olympiad in Informatics (INOI) is round 2 out of 3 (i.e. intermediate) for selection into Indian IOI team.
You also need to track the maximum time taken by any single person. Coz edge case may be that a person takes more time than anybody else, and goes beyond sum(exi)+min(ei). Once you have the maximum time taken by any one person, the answer will be max(sum(exi)+min(ei), max_time)
Interesting problem with more thinking and less implementation. You can find hints and more discussion here: POI 10 Sums. Problem is from Polish Olympiad in Informatics.
Problem in short: You are given an array a of length N. You start at position k. In the forward phase, you make jumps of size 1 or 2 towards the right. Then in the backward phase, you make jumps of size 1 of 2 towards the left till you reach position 1. Your score is the sum of the values in the array where you landed after each jump. What is the maximum score you can make?
Indian National Olympiad in Informatics (INOI) is round 2 out of 3 (i.e. intermediate) for selection into Indian IOI team.
Problem in short: You are given a tree with N nodes, where each node i has a value v[i] associated with it. Find nodes i and j, such that i is an ancestor of j and (v[i] - v[j]) is maximized. N <= 10^5.
Indian National Olympiad in Informatics (INOI) is round 2 out of 3 (i.e. intermediate) for selection into Indian IOI team.
I need some help about what exactly should I do for inoi
My prob is i am confused about which dp topics to do and which to not. For example dp with bit masking is required or not. Also there were many many topics on geeks for geeks and i couldnt get which ones to do as time is limited. It is nowhere mentioned on iarcs etc. Which questions of dp go beyond inoi level? Also is there a need to do segment trees ( i have no idea about it).
This playlist is mostly based on IARCS syllabus and previous years' papers' trends.
Read more… (23 words)
Read more (23 words)
NaN.
discussion
[659E] New Reform (Graph Problem)
In this question, if it is modeled as a tree then yes, there is only 1 separate city, that's intuitive, but there can be several cycles, here is where I am stumped.
I could consider a vertex to be a starting point and perform dfs but there are 10^5 vertices, so no. I didn't really understand the editorial either.
My logic is that the graph may be a collection of disconnected graphs. So a disconncted graph has a cycle=0 isolated cities, otherwise 1 isolated cities.
#include <bits/stdc++.h>
using namespace std;
long long n,m,x,y;
vector <long long> graph[1000000];
bool vis[1000000];
int main()
{
long long cycle (long long,long long);
cin>>n>>m;
for(long long i = 0 ; i < m ; i++)
{
cin>>x>>y;
graph[x].push_back(y);
graph[y].push_back(x);
}
for(long long i = 1 ; i <= n ; i++ ) //This loops helps in navigating through different disconnected graphs
{
x=0; // x is used inside cycle()
if( !vis[ i ] ){
vis[1]=1;
isolated += ( !cycle( i , -1 ) ) ; //if it is a cycle add 0, else add 1
}
}
cout<<isolated;
return 0;
}
long long cycle(long long cur, long long prev)
{
long long x=0;
for(unsigned long long i = 0 ; i < graph[cur].size(); i++ )
{
if( !vis[ graph[ cur ][ i ] ] )
{
vis[ graph[ cur ][ i ] ] = 1;
x+=cycle( graph[ cur ][ i ] , cur );
}
else if( prev != graph[ cur ][ i ] )
{
x++; //It has a cycle (so we will add 0 to isolated.