All Questionshttps://inoi15.discuss.codechef.com/questions/?type=rssquestionsenFri, 16 Jan 2015 18:21:34 +0530Welcome to INOI 2015 preparation group.https://inoi15.discuss.codechef.com/questions/60298/welcome-to-inoi-2015-preparation-group<p>Welcome to the INOI 2015 preparation group. This group consists of those members who have qualified for INOI 2015 to be held on the 31st January 2015. The details of this contest and the selection of the candidates can be found here: <a href="http://www.iarcs.org.in/inoi/2015/.">http://www.iarcs.org.in/inoi/2015/.</a></p>
<p>We want you to win the Gold medal for India at the IOI finals. Last year, <a href="https://www.google.co.in/?q=delhi%20boy%20wins%20gold#q=delhi+boy+wins+gold">Akshat won it for us</a>. And this year, if you do so, we have something in store for you. You can win exciting prizes through our <a href="http://www.codechef.com/school/goforgold">Go For Gold program</a>. </p>
<p>We want you guys to give it your best shot in the next round. This group is to help you towards that. The senior students of Computer Science Engineering from the CodeChef community will be helping you out to solve your queries related to preparations for the INOI. </p>
<p>All the best! </p>
<p><strong>PS:</strong> If you know someone who is left out and wants to get added, please fill in this <a href="https://docs.google.com/a/codechef.com/forms/d/1muwlJCfvGEwOgqoD5HBj19lhVQ_F0qISwQXhQbP3MoI/edit">form</a>. He will need to fill in his Roll Number along with the CodeChef username. If he does not have a CodeChef username, then he will need to create one by registering <a href="http://www.codechef.com/user/register">here</a>. </p>adminTue, 30 Dec 2014 20:18:56 +0530https://inoi15.discuss.codechef.com/questions/60298/welcome-to-inoi-2015-preparation-groupdescriptionHelp me with this graph problemhttps://inoi15.discuss.codechef.com/questions/60367/help-me-with-this-graph-problem<p>Someone mentioned in an answer that the following problem can be solved using only DFS/BFS: <a href="http://www.spoj.com/problems/PRATA/">http://www.spoj.com/problems/PRATA/</a></p>
<p>I am not getting any idea on how to solve this problem without using Dijkstra's algo/ MST. Binary Search is another approach. Can anyone tell how to solve this using only BFS/DFS?</p>ketanhwrWed, 31 Dec 2014 21:54:18 +0530https://inoi15.discuss.codechef.com/questions/60367/help-me-with-this-graph-problembfsgraphdijkstramstdfsHere'e a prob. I've been struggling with...Plz. help!!!https://inoi15.discuss.codechef.com/questions/60384/heree-a-prob-ive-been-struggling-withplz-help<p>Can someone explain the statement of the HYPERSPACEPATHS prob. from the INOI Practice Server..
If possible, please describe the solution...</p>arpanb8Thu, 01 Jan 2015 02:28:22 +0530https://inoi15.discuss.codechef.com/questions/60384/heree-a-prob-ive-been-struggling-withplz-helpgraphDiscussion on Java and some tipshttps://inoi15.discuss.codechef.com/questions/60417/discussion-on-java-and-some-tips<p>I have found that the BufferedReader is faster than the Scanner at taking inputs. My program was getting TLE with Scanner and as soon as I switched to BufferedReader, it ran perfectly well. Same goes with PrintWriter. My program which was getting TLE with System.out.print ran perfectly when I used PrintWriter instead. Will this be true for all programs? Can I save execution time by using BufferedReader and PrintWriter?</p>
<p>I have seen many programmers who import library classes one by one instead of the whole. I mean they write,"import java.io.BufferedReader; import java.io.PrintWriter;". I always write,"import <a href="http://java.io">java.io</a>.*;". This imports the entire IO library. Does importing only the required libraries save time/memory or both?</p>
<p>What are some other ways I can reduce the execution and memory required in Java?
If you guys know some quick tips or techniques in Java that are helpful, please write them for every Java programmer. </p>
<p>I'll start by saying Arrays.sort() is the best way to sort an array(even Strings). </p>
<p>Thanks a lot :-)</p>infam0usThu, 01 Jan 2015 17:44:18 +0530https://inoi15.discuss.codechef.com/questions/60417/discussion-on-java-and-some-tipsjavatleprogramminginoiioizioinoi2015Dynamic Programming Problemhttps://inoi15.discuss.codechef.com/questions/60500/dynamic-programming-problem<p>How to solve the problem STANOVI from COCI contest 4 ?</p>
<p><a href="http://hsin.hr/coci/contest4_tasks.pdf">http://hsin.hr/coci/contest4_tasks.pdf</a> It is the 6th problem.</p>neo1tech9_7Fri, 02 Jan 2015 02:15:32 +0530https://inoi15.discuss.codechef.com/questions/60500/dynamic-programming-problemdynamic-programmingcociFolks, I found some nice study material for INOI...https://inoi15.discuss.codechef.com/questions/60533/folks-i-found-some-nice-study-material-for-inoi<p>It covers all you need to know for INOI. And all the material is covered in the form of problem and solutions. It is effective for both novices and experienced contestants. Google "IOITC 2008 NOTES PDF". Even no algorithmic background will do...
It covers many of the past ioi problems.
*I'm not the creator of these notes...</p>
<p>Thanking Everybody...</p>arpanb8Fri, 02 Jan 2015 13:45:16 +0530https://inoi15.discuss.codechef.com/questions/60533/folks-i-found-some-nice-study-material-for-inoinotesCovering: ZCO 2015https://inoi15.discuss.codechef.com/questions/60636/covering-zco-2015<p>How do I solve the Interval Covering Problem from ZCO 2015???</p>arpanb8Sat, 03 Jan 2015 21:55:57 +0530https://inoi15.discuss.codechef.com/questions/60636/covering-zco-2015intervalgreedyzco2015Need some graph theory problemshttps://inoi15.discuss.codechef.com/questions/60648/need-some-graph-theory-problems<p>What are some good problems to do for Graph Theory for preparation of INOI ?</p>nibnalinSun, 04 Jan 2015 00:22:33 +0530https://inoi15.discuss.codechef.com/questions/60648/need-some-graph-theory-problemsgraphsproblemsinoiinoi2015Can someone solve FREETICKET from INOI 2014?https://inoi15.discuss.codechef.com/questions/60652/can-someone-solve-freeticket-from-inoi-2014<p>Hi everyone.
I've been practicing on the INOI server lately, however I've not yet solved even a single question. I studied Graph Theory for the first time last week and decided to do the FREETICKET problem using Djikstra's Algorithm (<a href="http://www.iarcs.org.in/inoi/2014/inoi2014/inoi2014-qpaper.pdf">here</a>).</p>
<p>I've tried to solve the problem innumerable times, but am still not able to do so. If someone could please tell me the pseudocode, it'll be of great help. I'm asking for the pseudo code as I program in Java and am sometimes not able to understand c++ syntax. </p>
<p>Also, if you could review my pseudo code once, I'll be very grateful.
<code></code></p><code>
<p>int[] max = new int[vertices]
for each vertex u = 1 -> v:
int[] dist = new int[vertices]
dist[u] = 0
for each int i = 1 -> v:
if i != u:
dist[i] = INFINITY
for each int i = 0 -> v:
if edge exists from u->i:
int tmp = dist[u] + weight[u][i]
if tmp < dist[i]:
dist[i] = tmp
max[u] = maximum(dist)
int f = maximum(max)
return f //here max is an array and maximum is the
//function for finding maximum value</p>
</code><p><code></code></p>
<p>I realize this is a tedious work but please help me, it's really important.</p>
<p>Thank you all for your help, guys.</p>
<p>Note: when I'm trying the sample case, it returns maximum int value, which means the relaxation is not being done properly.</p>pm1511Sun, 04 Jan 2015 00:47:17 +0530https://inoi15.discuss.codechef.com/questions/60652/can-someone-solve-freeticket-from-inoi-2014bfsgraphshortest-pathAdjacency lists & Adjacency matriceshttps://inoi15.discuss.codechef.com/questions/60720/adjacency-lists-adjacency-matrices<p>I recently implemented DFS by making an adjacency list using a vector of vectors and was pretty pleased about that. But yesterday, I read here <a> </a><a href="http://web.stanford.edu/class/cs97si/">http://web.stanford.edu/class/cs97si/</a> on the basic Graph algorithms slide that an array of vectors is slower than plain arrays.</p>
<p>For me, vectors of vectors was pretty easy to code but just arrays was hard as I had trouble just adding an edge and manipulating the 2 arrays. What do the rest of you recommend me to use taking into account time and memory efficiency? If you recommend arrays, could you also give me a good resource which explains how to easily implement it?</p>
<p>Also, I read that we should use an adjacency matrix only when the graph is dense (No. of vertices is almost equal to no. of edges). But what if the constraints (around 10^5 edges) are such that it is too large even for the global scope? What do I use to represent the edge relations in such a case?</p>sandy999Sun, 04 Jan 2015 16:24:04 +0530https://inoi15.discuss.codechef.com/questions/60720/adjacency-lists-adjacency-matricesgraphsSubstring with least mod value - DP?https://inoi15.discuss.codechef.com/questions/60742/substring-with-least-mod-value-dp<p>This is from IARCS Problem archive (DEVIOUS). Given a sequence of integers, how do you find the contiguous substring with the absolute value of the sum of its numbers being minimum?
Is it even DP? How do you relate it to smaller subproblems?</p>vikramnitin9Sun, 04 Jan 2015 19:14:03 +0530https://inoi15.discuss.codechef.com/questions/60742/substring-with-least-mod-value-dpdynamiccontiguousprogrammingsubstringiarcsdeviousarchiveabsoluteTLE in SUMTHINGhttps://inoi15.discuss.codechef.com/questions/60819/tle-in-sumthing<p>I'm getting a TLE in SUMTHING from the INOI Practice Server...
Here's my C++ source code:</p>
<h1>include "iostream"</h1>
<h1>include "cmath"</h1>
<h1>include "string"</h1>
<h1>include "algorithm"</h1>
<p>using namespace std;</p>
<p>int main()</p>
<p>{</p>
<pre><code>int n;
cin >> n;
string x;
cin >> x;
int k, z;
cin >> k;
int xyz[n];
int sum[n-1];
for (int i = 0; i<=n-1; i++)
{
if (i<n-1)
sum[i]=0;
xyz[i]=(int)<a href="http://x.at">x.at</a>(i)-48;
}
int ans;
for (int p = 1; p<=n-1; p++)
{
sort (sum, sum+n-1);
sum[n-1-p]=1;
do
{
ans=0;
z=1;
for (int q = n-1; q>=0; q--)
{
if (q<n-1 && sum[q]==1)
z=1;
else
z++;
ans+=pow(10, z)*xyz[q];
}
if (ans==k)
{
cout << p;
return 0;
}
}while(next_permutation(sum, sum+n-1));
}
cout << "-1";
return 0;
</code></pre>
<p>}</p>
<p>PLEASE HELP ME SPEED IT UP...</p>arpanb8Mon, 05 Jan 2015 20:21:32 +0530https://inoi15.discuss.codechef.com/questions/60819/tle-in-sumthingpracticeserverCHANGED ONCE AGAIN!!! HIGHWAYBYPASS@INOI Practice Serverhttps://inoi15.discuss.codechef.com/questions/60844/changed-once-again-highwaybypassinoi-practice-server<p>On submission, It works fine for 90%+ testcases under each subtask but the final score is 20, since I got a WA some...PLEASE HELP!!!</p>
<blockquote>
<h1>include "iostream"</h1>
<h1>include "algorithm"</h1>
</blockquote>
<p>using namespace std;</p>
<p>int main()</p>
<p>{</p>
<pre><code>int r, c;
cin >> r >> c;
int d;
cin >> d;
d++;
int x[r][c];
for (int i = 0; i<=r-1; i++)
for (int j = 0; j<=c-1; j++)
cin >> x[i][j];
long long int ans[r][c];
int temp1, temp2, temp3, temp4;
ans[0][0]=1;
for (int p = 0; p<=r-1; p++)
for (int q = 0; q<=c-1; q++)
{
temp1 = (p>=d)?ans[p-d][q]%20011:0;
temp2 = (q>=d)?ans[p][q-d]%20011:0;
temp3 = (p>=1)?ans[p-1][q]%20011:0;
temp4 = (q>=1)?ans[p][q-1]%20011:0;
if (temp3+temp4-temp1-temp2>=0)
ans[p][q]=temp3+temp4-temp1-temp2;
else
ans[p][q]=0;
if (x[p][q]==0)
ans[p][q]=0;
ans[0][0]=1;
}
cout << ans[r-1][c-1];
return 0;
}
</code></pre>
<p>I know of the O(n^3) & the O(n^4) solutions. Given the constraints, they should work... But my solutions is, in fact, O(n^2). The method is called GRAPH CUTTING. It is a very correct algorithm. There are probably slight mistakes in memory allocation, implementation of the algorithm etc. So, I need help in debugging the solution...So please try to...THANKS!!!</p>arpanb8Mon, 05 Jan 2015 23:07:45 +0530https://inoi15.discuss.codechef.com/questions/60844/changed-once-again-highwaybypassinoi-practice-serverdynamic-programmingpracticeservermoduloHelp needed with this Dynamic Programming Questionhttps://inoi15.discuss.codechef.com/questions/60875/help-needed-with-this-dynamic-programming-question<p>I am preparing for INOI and am stuck on this problem here: <a href="http://acm.timus.ru/problem.aspx?space=1&num=1081">http://acm.timus.ru/problem.aspx?space=1&num=1081</a></p>
<p>I am just a beginner with DP so I am not getting any idea on how we will solve this question. Can anyone explain me the proper logic of the solution to this problem instead of just giving the code?</p>ketanhwrTue, 06 Jan 2015 11:10:22 +0530https://inoi15.discuss.codechef.com/questions/60875/help-needed-with-this-dynamic-programming-questionbinaryicodynamic-programminginoi2015lexicographicalinoiTABLESUM WAhttps://inoi15.discuss.codechef.com/questions/60902/tablesum-wa<p>Could someone please tell me what's going wrong with this TABLESUM code? I am getting WA in all except 3 test cases. The algorithm is O(N), so time is not an issue.</p>
<p><a> </a><a href="https://www.dropbox.com/s/im7sjck0z8elukk/TABLESUM.cpp?dl=0">https://www.dropbox.com/s/im7sjck0z8elukk/TABLESUM.cpp?dl=0</a> </p>sandy999Tue, 06 Jan 2015 17:37:16 +0530https://inoi15.discuss.codechef.com/questions/60902/tablesum-watablesumCan anyone teach me DP on trees with the help of solving this question?https://inoi15.discuss.codechef.com/questions/60948/can-anyone-teach-me-dp-on-trees-with-the-help-of-solving-this-question<p>I came across this problem (DP on trees): <a href="http://acm.timus.ru/problem.aspx?space=1&num=1018">http://acm.timus.ru/problem.aspx?space=1&num=1018</a></p>
<p>I solved some beginner level problems on DP but I can't get the logic of this particular topic. I tried reading about this topic on the IARCS website (<a href="http://www.iarcs.org.in/inoi/online-study-material/topics/dp-trees.php">link</a>) but I couldn't understand it completely. Can anyone explain me DP on trees along with solving the question given above? (I mean, like a proper tutorial. Since there are very few good resources on DP on trees, it would help all of them searching for this topic)</p>ketanhwrWed, 07 Jan 2015 10:53:03 +0530https://inoi15.discuss.codechef.com/questions/60948/can-anyone-teach-me-dp-on-trees-with-the-help-of-solving-this-questiondynamic-programmingtreedp+treesDP problemshttps://inoi15.discuss.codechef.com/questions/61013/dp-problems<p>Guys, where can I find IOI style DP problems?</p>infam0usThu, 08 Jan 2015 14:43:01 +0530https://inoi15.discuss.codechef.com/questions/61013/dp-problemsdynamic-programmingprobleminoiioiIarcs problem archive- Find the Numbershttps://discuss.codechef.com/questions/61044/iarcs-problem-archive-find-the-numbers<p>link: <a href="http://opc.iarcs.org.in/index.php/problems/FINDNUMS">http://opc.iarcs.org.in/index.php/problems/FINDNUMS</a></p>
<p>My approach was to factorize 'P' and as it is small to brute force over all combinations of divisors.
For example for S=11, P=48 and k=3 (Shown example) I would check (1,1,48),(1,2,24),(1,3,16) and so on till i reached (3,4,4) which was the answer. Could someone suggest some method to enumerate all the sets of the divisors of the number?</p>
<p>Any other solution too would be of great help.</p>ajs97Thu, 08 Jan 2015 21:02:59 +0530https://discuss.codechef.com/questions/61044/iarcs-problem-archive-find-the-numbersiarcsserverODDSORT and ANTS on the INOI serverhttps://discuss.codechef.com/questions/61046/oddsort-and-ants-on-the-inoi-server<p>Has anybody solved these two? If so, how?</p>supertyThu, 08 Jan 2015 21:58:27 +0530https://discuss.codechef.com/questions/61046/oddsort-and-ants-on-the-inoi-serveroddsortantsTIMBER: Runtime Errorhttps://discuss.codechef.com/questions/61090/timber-runtime-error<p>I was solving this problem on IARCS Judge: <a href="http://opc.iarcs.org.in/index.php/problems/TIMBER">http://opc.iarcs.org.in/index.php/problems/TIMBER</a></p>
<p>And I made a O(n*m + c) solution but still it says TLE on some cases:
<img alt="alt text" src="http://discuss.codechef.com/upfiles/codechefproblem.png"></p>
<p>And it says Runtime Error: TLE. Idk whether it is a runtime error or not. Because I don't think that there is segmentation fault anywhere. Nor there should TLE because O(n*m + c) solution is perfectly fine for the test data.
Here is my code. Can anyone help me find the problem?</p>
<pre><code>#include<iostream>
using namespace std;
int dp[1002][1002];
int a[1001][1001];
int main()
{
ios::sync_with_stdio(false);
int n,m;
cin >> n >> m;
for(int i = 0;i < n;i++)
for(int j = 0;j < m;j++)
cin >> a[i][j];
int c;
cin >> c;
dp[1][1] = a[0][0];
for(int i = 0;i <= n;i++) dp[i][0] = 0;
for(int j = 0;j <= m;j++) dp[0][j] = 0;
for(int i = 2;i <= n;i++) dp[i][1] = a[i-1][0] + dp[i-1][1];
for(int i = 2;i <= m;i++) dp[1][i] = a[0][i-1] + dp[1][i-1];
for(int i = 2;i <= n;i++)
for(int j = 2;j <= m;j++)
dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1] + a[i-1][j-1];
//***DEBUG***
/*cout << endl;
for(int i = 0;i < n+1;i++)
{
for(int j = 0;j < m+1;j++)
cout << dp[i][j] << " ";
cout << endl;
}
cout << endl;*/
for(int ctr = 0;ctr < c;ctr++)
{
int x1,y1,x2,y2;
cin >> x1 >> y1 >> x2 >> y2;
cout << dp[x2][y2] - dp[x2][y1-1] - dp[x1-1][y2] + dp[x1-1][y1-1] << endl;
}
return 0;
}
</code></pre>
<p>If anyone is having confusion regarding the approach of my code, then here is the approach: <a href="http://www.iarcs.org.in/inoi/contests/dec2004/Advanced-2-solution.php">http://www.iarcs.org.in/inoi/contests/dec2004/Advanced-2-solution.php</a>
(The approach is the bottom most pseudocode on this webpage)</p>ketanhwrFri, 09 Jan 2015 11:54:00 +0530https://discuss.codechef.com/questions/61090/timber-runtime-erroriarcsruntime-errorinoitletimberThe Great Escape: Runtime Errorhttps://discuss.codechef.com/questions/61167/the-great-escape-runtime-error<p>I tried solving The Great Escape on the INOI server: <a href="http://opc.iarcs.org.in/index.php/problems/GREATESC">http://opc.iarcs.org.in/index.php/problems/GREATESC</a></p>
<p>I used a simple BFS to find the minimum number of jumps. But my code is showing segmentation fault in the last test case. Can anyone one point out my mistake?
My code:</p>
<pre><code>#include<iostream>
#include<queue>
#include<vector>
#include<cstring>
using namespace std;
vector<int> adjlist[3500];
queue<int> bfs;
int main()
{
int n,m;
cin >> n >> m;
int a,b;
while(m--)
{
cin >> a >> b;
a--; b--;
adjlist[a].push_back(b);
adjlist[b].push_back(a);
}
int s,t;
cin >> s >> t;
s--;
t--;
int v[n];
memset(v,-1,sizeof(v));
v[s] = 0;
bfs.push(s);
while(!bfs.empty())
{
int node = bfs.front();
bfs.pop();
int d = v[node];
for(unsigned int i = 0;i < adjlist[node].size();i++)
{
int node2 = adjlist[node][i];
if(v[node2] == -1)
{
v[node2] = d+1;
bfs.push(node2);
}
}
}
if(v[t] == -1) cout << 0 << endl;
else cout << v[t] << endl;
return 0;
}
</code></pre>ketanhwrSat, 10 Jan 2015 10:51:42 +0530https://discuss.codechef.com/questions/61167/the-great-escape-runtime-errorgreatesciarcsruntime-errorinoiSUMTHING IOITC 2013https://discuss.codechef.com/questions/61186/sumthing-ioitc-2013<p>Can someone please tell me what's wrong with the following code?</p>
<h1>include <iostream></h1>
<h1>include <stdio.h></h1>
<h1>include <vector></h1>
<h1>include <string></h1>
<p>using namespace std;</p>
<p>signed int st(string a, signed int b) {
vector<signed int=""> v;
int asize=int(a.size());
int bsize=int(to_string(b).size());</p>
<pre><code>if(a==to_string(b)) {
return 0;
}
else if((asize>bsize) && (b>0) && asize>1) {
int j=1;
while((j<=bsize) && a.substr(0,j).size()>0) {
v.push_back( st( a.erase(0,j), b-stoi(a.substr(0,j))));
j++;
}
int i=0;
while((v.begin()+i) < v.end()) {
if(v[i]== -1) {
v.erase(v.begin()+i);
}
else {
i++;
}
}
if(v.size()>0) {
return (*min_element(v.begin(), v.end()) +1);
}
else {
return -1;
}
}
else if((asize==bsize) && b>0 && asize>1) {
v.push_back( st( a.erase(0,1), b-stoi(a.substr(0,1))));
int i=0;
while((v.begin()+i) < v.end()) {
if(v[i]== -1) {
v.erase(v.begin()+i);
}
else {
i++;
}
}
if(v.size()>0) {
return (*min_element(v.begin(), v.end()) +1);
}
else {
return -1;
}
}
else {
return -1;
}
</code></pre>
<p>}</p>
<p>int main() {
signed int a,b;
string c;
scanf("%d",&a);
cin>>c;
scanf("%d",&b);
signed int final=st(c,b);
cout<<final<<endl;
return 0;
}</p>
<p>(Sorry, the code is not documented :P)</p>chittaranjanSat, 10 Jan 2015 16:50:01 +0530https://discuss.codechef.com/questions/61186/sumthing-ioitc-2013dynamic-programminginoi2015Floyd Warshall Algorithmhttps://discuss.codechef.com/questions/61201/floyd-warshall-algorithm<p>Could someone please give me a basic intuition between the Floyd Warshall algorithm like how you would explain it to a layman? In addition to when it is/isn't preferred over Dijakstra's algorithm?</p>
<p>I've tried looking up various sources but it's like, if I read a pseudocode I am able to understand what they are doing but not why they are doing it, which is pretty pointless as that is not the right way to learn.</p>
<p>Could someone please help me out?</p>sandy999Sat, 10 Jan 2015 20:45:57 +0530https://discuss.codechef.com/questions/61201/floyd-warshall-algorithmfloyd-warshallIarcs Problem Archive - Number of Routings(NUMROUTE)https://discuss.codechef.com/questions/61286/iarcs-problem-archive-number-of-routingsnumroute<p><a href="http://opc.iarcs.org.in/index.php/problems/NUMROUTE">link NUMROUTE</a></p>
<p>Can someone please tell me the algorithm I should use to solve this problem. My algorithm is giving TLE error. </p>rahulthebestMon, 12 Jan 2015 08:26:58 +0530https://discuss.codechef.com/questions/61286/iarcs-problem-archive-number-of-routingsnumrouteiarcsPREEORDERTREE from the INOI Practice Server...https://discuss.codechef.com/questions/61403/preeordertree-from-the-inoi-practice-server<p>How should I attack this problem...is the answer not the Kth permutation of the 1st N letters?>!>!>!?</p>arpanb8Mon, 12 Jan 2015 22:17:34 +0530https://discuss.codechef.com/questions/61403/preeordertree-from-the-inoi-practice-serverioitcError in FREETICKET(INOI14)https://discuss.codechef.com/questions/61463/error-in-freeticketinoi14<p>I tried solving the FREETICKET problem from INOI 2014 using floyd-warshall algorithm. Following is the code I wrote:</p>
<pre><code>#include <iostream>
#include <cstdio>
#include <climits>
#include <vector>
#include <algorithm>
using namespace std;
typedef vector<long long int> vl;
typedef vector<vl> vvl;
long long int maxelem(const vvl& arr)
{
long long int max = 0, curmax;
for(int i = 0, l = int(arr.size());i < l;i++)
{
curmax = *(max_element(arr[i].begin(), arr[i].end()));
if(curmax > max)
{
max = curmax;
}
}
return max;
}
int main(void)
{
long long int c, f, x, y, p;
scanf("%lld%lld", &c, &f);
vvl adj(c, vl(c, 26336));
for(int i = 0;i < f;i++)
{
scanf("%lld%lld%lld", &x, &y, &p);
adj[x-1][y-1] = p;
adj[y-1][x-1] = p;
}
long long int max = 0;
for(int k = 0;k < c;k++)
{
for(int i = 0;i < c;i++)
{
for(int j = 0;j < i;j++)
{
adj[i][j] = min(adj[i][j], adj[i][k] + adj[k][j]);
}
for(int j = (i + 1);j < c;j++)
{
adj[i][j] = min(adj[i][j], adj[i][k] + adj[k][j]);
}
}
}
max = maxelem(adj);
printf("%lld\n", max);
}
</code></pre>
<p>This code just uses an adjacency matrix and ensures that no one tries to go from the same place, to the same place(in the innermost loop). It fails to solve some of the subtasks from subtask 3 and yields me 50/100 marks. Can anyone help me finding the bug in my code ?</p>
<p>Thanks!
nibnalin</p>nibnalinTue, 13 Jan 2015 11:32:14 +0530https://discuss.codechef.com/questions/61463/error-in-freeticketinoi14floyd-warshallpaths-in-graphhelp_inoiinoiinoi2015HISPDNET algorithmhttps://discuss.codechef.com/questions/61499/hispdnet-algorithm<p>Problem statement: <a> </a><a href="http://opc.iarcs.org.in/index.php/problems/HISPDNET">http://opc.iarcs.org.in/index.php/problems/HISPDNET</a> </p>
<p>I can only think of the following:</p>
<p>1) Brute force: Consider all permutations of 2,3,4,...,N and find which among these gives the minimum cost (where the 1st city of the permutation is connected only to 2nd element, 2nd element to 3rd element and so on). But it is too time consuming and wouldn't give the answer even in a billion years.</p>
<p>2) Use some shortest path algorithm. (As of now, I am only familiar with Dijkstra's and Floyd Warshall). But there is a big restriction, I need to find shortest paths between all pairs of sources and destinations and where the number of intermediate edges is strictly N-2 (excluding source and destination), nothing more or nothing less.</p>
<p>I am really confused as to how to approach the problem with an elegant time efficient algorithm. It would be great if someone could give me a hint.</p>sandy999Tue, 13 Jan 2015 16:16:16 +0530https://discuss.codechef.com/questions/61499/hispdnet-algorithmhispdnetMock INOI in codechefhttps://discuss.codechef.com/questions/61738/mock-inoi-in-codechef<p>check out <a href="http://www.codechef.com/DINP1501/">http://www.codechef.com/DINP1501/</a> it has mock INOI<strong>_</strong>. these may help :)</p>jayaganeshThu, 15 Jan 2015 15:04:00 +0530https://discuss.codechef.com/questions/61738/mock-inoi-in-codechefpracticeinoi2015Graph algorithmshttps://discuss.codechef.com/questions/61805/graph-algorithms<p>Hi friends,
Please refer me a good book for learning the basics of Graph Theory.( Such as shortest paths.)</p>anupam_dattaThu, 15 Jan 2015 23:35:56 +0530https://discuss.codechef.com/questions/61805/graph-algorithmsshortest-pathAdjacency listhttps://discuss.codechef.com/questions/61845/adjacency-list<p>Can anyone give me a code of using adjacency lists to represent a graph using arrays only( perhaps by using an 2D array).</p>anupam_dattaFri, 16 Jan 2015 18:21:34 +0530https://discuss.codechef.com/questions/61845/adjacency-listarrayadajacency-list