Circle of towers

Symbols broken in the input section here too.

does the friend move clockwise or anticlockwise movement is also allowed?

because in second test case, if friend moves from '7 to 9' in clockwise direction then time is 20

while if he moves from '7 to 9' in anticlockwise then time taken is 22.

Broken symbols fixed.

@Abhay Please read the problem statement.

"0-th to the k-th, assuming that the skyscraper in question has k floors"

There's a bit of a cultural boundary when dealing with floor numberings.  Some countries label the ground level the 0th floor, some label it the 1st floor.  And in my country, at least, the ground floor is included in the floor count, so a 4 floor building has a 1st, 2nd, 3rd, and 4th floor (but no 0th).

Well what about the 13th floor?  In America we don't typically have a 13th floor.  ;)

I'm a bit confused by the first example. If they both lived on the 4th floor in the two '4' buildings, wouldn't the travel time be 9? It would take 4 units of time to get from the 4th floor to the 0th, then 1 more to get to the neighboring building, then 4 more to get from the 0th to the 4th.

What am I missing?

Ah wait, I just realized that the first number is the number of buildings.

Hi,

I am getting a time limit exceeded in the below code - all it does is read the input. Is this the correct way to take input? I read the faq and can't figure out how else to take the input?

THanks for the help !

#include<iostream>
#include<stdio.h>
#include<vector>
#include<algorithm>
#include<set>
#include <stdlib.h>
#include <cstdlib>


using namespace std;

struct Data
{
long height;
long index;

};

Data d[1000000];
int main()
{

long nTotal = 0;

scanf("%ld",&nTotal);

for(long i = 0; i < nTotal; i++)
{   
scanf("%ld", &d[i].height);
d[i].index = i;
}



cout<<10;
}

I too have a question similar to Anirudh Saraf. Is there a solution to this problem that can be accepted by the judge, which just uses scanf for reading the integers?

Doesn't look like it. Having such a strict time limit is a bit silly, really. Takes all the emphasis off the algorithm and puts it on rather terrible hacking.

hi i am also facing the same problem.Can anyone suggest us a way out.

Hi, i think the cause of your input testing code to give tle is, your code does not read multiple test cases

Is it supposed to read multiple test cases? It doesn't say how multiple test cases are given?

even linear time algo is giving tle,so may b the algo shud be in logn order,right??

There are one test case per one test file. But the numbers can be given in multiple lines. I got WA assuming that there would be one line input. I think it would be better if the problem description mentioned that.

me too getting TLE, in problem statement multiple test cases are not mention..should that be tried?

i think numbers given in multiple lines wont b a problem since each number <=10^9.

@Tasnim: thanks, I hadn't thought of that possibility

@Iaxman: not a problem with C/scanf, but definitely a problem if expecting all input on one line!

to all complaining about strict timelimits - I have very stron reason to give them so tight, but I will explain it only *after* contest.

Until then - just live with it.

There is never a good reason for a time limit like this ;) But I guess we'll have to discuss that after the contest.

but however strict the time limit - we atleast need to read in all the numbers? I am getting a TLE if i just use scanf to read in the numbers and not even bother storing them separately or anything !On my machine I can read in 10^6 numbers in less than a second - but i still get a TLE when i submit it !

I could not understand the problem. Can someone explain the output for sample cases.The way I understand is , two persons should live at two places such that the distance is max(either from clockwise or anticlockwise). Am I right. I still cant understand the problem.

Got the problem!!!

@Writer: on problems where the desired solution is fast enough that reading input becomes a bottleneck, a good alternative to having the user read all the data from stdin is to supply a function that generates the input.  See http://www.topcoder.com/stat?c=problem_statement&pm=10717 for a recent topcoder example, where just 4 integers define a grid of size up to 350*350.

The time limit says 1s, but the successful submissions all have much longer in the time column. If the time column doesn't tell us the truth, how can we judge how close we are to being fast enough?

You haven't read the FAQ, I presume.

Read it and forgot it already! Sorry.

So there's really no way of telling how much you need to optimise? That really ruins the puzzle for me. :( Apart from making it a very artificial excercise, it means you can't even know that there _is_ a sufficiently fast solution in the language you're using. Suspicious that all of the successful submissions so far are in C/C++ - but since we don't know what we're aiming at, how could we know if we ought switch languages?

I have time limit exceeded even in scanning the input

how can i optimse the code than?

can anyone get an idea.

TLE TLE TLE

@Saikat Debnath

Worst possible description of the problem i think. We can understand whatever we want. May be between towers you have to consider smallest distance. 3+1+4=8. The circle is biderectional i think.Anyways this is just a guess.

I think this is the worst problem from all the contest so far. I spend half a day just to fix the IO. This is not fun at all

@ Balakrishnan: Did you manage to fix the IO though ?

@David Stolp

great idea, I'm familiar with TopCoder. But with random input it's hard to generate some 'special' testcases.

But I'll try to follow the idea. Anyway, "time limit is extremely strict" should give point..

two solutions to 1 test case are:

one friend on top of 4, one on top of 3 (with distance 3+1+4),

or one on top of 4, one on top of 2 (with distance 2+1+4).

yes, circle is bidirectional

Hi Przemysław,

Does it make any sense to make my solution any faster?

At the moment it works fine, but perhaps it could be made a little faster...

Is there any faster way of getting the input than scanf()?

Is there any faster way of getting the input than scanf()?

scanf gets TLE. Some people have got accepted. You draw the logical conclusion.

@Johann Ly :

First try the problem "Enormous Input Output Test on Codechef". This will help you a lot.

I am getting Runtime Error : Other. Plz help me to correct it.

need to have return 0; at the end of main()

@Stephen Merriman

 Some got AC on Scanf and some TLE.

  How could both??

   Is there any other way to speed up IO?

@ Codechef Admin

I have solved Circle of towers with 2nd fastest speed. But still cannot see my ranking. Can u please check if some problem is there or tell me if I am mistaken abt something????

Thanks in advance!

@ Admin ... problem solved by resubmitting the solution.

Thanks anyways.

hai...

Im getting runtime error. But I think I took all precautions.(even checked the bounds on arrays).

Im doing it in JAVA and have tried for many inputs. I tried for large values also and not getting any errors on my pc. I named the file Main.java.

Can some 1 tell me what may be the reason??

"Please note: the time limit for this problem is extremely strict!"

My first impression from the problem is that it is gonna be like those extremely lame OJ questions in which you also have to do lower-level optimization for no reason ... Strike one...

TLE: i have an O(n) algo, is a better algo expected?

I strongly believe O(n) would definitely run within time. But I still dint find one O(n) solution

@piyush: If you can imagine sub-linear algorithm - cool.

why am i getting this error

/sources/tested.c:2:18: error: conio.h: No such file or directory

what is the correct header

FAQ

i have O(n) algo and i am using scanf, then what's problem ?

Are there multiple input cases ?

I hope if my algo is by chance wrong somewhere, it would give me err, and not TLE !!

Even I wrote an algo in O(n) time in JAVA. Im getting Runtime error . Is there any way to find out the exact error?? In my PC, i generated long random inputs, and the program worked very fast with out any errors!

No, you will not be told the exact error. You have to figure that out yourself.

From the problem , I understand that the whole input has to be read from a single line. Is this true?

is there a function in c++ to calculate my running time for a certain testcase?

@Admin:

is my algo giving a better solution !!!

or

i have over-looked some special test case ?

:P

@admin

(..continuation of previous post)

or

i have missed out something big

your comments would be of help

thanks

@admin

no sweat,

missed out on a "small" technicallity :D

Hi guys,how do we contact users here?

You can't.

Is this a variant of some algorithm or is there any related problems like this one? I dint get a clue on the approach.

Or I just missed the easy one?

1. # include <stdio.h>
3. int main()
4. {
5. long int n,i,j;
6. long int *h,max=1;
7. scanf("%ld",&n);
8. if(n<1 || n>1000000)
9. return 0;
10. h = malloc(n);
11. for(i=0;i<n;i++)
12. {
13. scanf("%ld",&h[i]);
14. if(h[i]<1 || h[i]>1000000000)
15. return 0;
16. }
17. for(i=0;i<n-1;i++)
18. for(j=i+1;j<n;j++)
19. if(((j-i)+h[i]+h[j])>max)
20. max=((j-i)+h[i]+h[j]);
21. printf("%ld",max);
22. return 0;
23. }
    codechef admin, can u explain by what means this code gives wrong answer?

You haven't included cases where you go from tower N to tower 1 in one minute.

hey.. can we get the test cases now as the contest is over!!?

dsfdf