440 - Eeny Meeny Moo

[littledump]

My 440 works, i tested with all sample input, but it goes over the 10 seconds.

When i compile and run & i hit 0, the program wont terminate, but it wont let me type

If you wish to see my code, i will post it

[littledump]

actually i decided to post my code anyway. it executes really quick when i use it.

[cpp]
/*
*
* Solves #440 - Eeny Meeny Moo
*
*/

#include <iostream.h>

void main(void) {

int *cityOnNet, *cityOffNet;
int citiesOff, citiesOn, nextCity, numCities, m;

while(cin >> numCities != 0) {
cityOnNet = new int[numCities];
cityOffNet = new int[numCities];

m = 0;

do{
citiesOn = numCities;

for (int i = 0; i < numCities; i++){
cityOnNet = i+1;
cityOffNet = 0;
}

cityOffNet[0] = 1;
citiesOn--;
citiesOff=1;
nextCity=0;

for (int i = 1; i < numCities; i++){
nextCity+=m;
while(nextCity >= citiesOn){
nextCity -= citiesOn;
}
for (int j = 0; j < citiesOff; j++){
for (int k = 0; k < citiesOn; k++){
if (cityOffNet[j] == cityOnNet[k]){
for (int l = k; l < citiesOn; l++){
cityOnNet[l] = cityOnNet[l+1];
}
}
}
}
cityOffNet = cityOnNet[nextCity];
citiesOff++;
citiesOn--;
}
m++;
}while (cityOffNet[numCities-1] != 2);
cout << m;
delete [] cityOnNet;
delete [] cityOffNet;
}
}
[/cpp]

[Adil]

shouldn't it be[cpp]while(cin >> numCities && numCities != 0) [/cpp]in stead of[cpp]while(cin >> numCities != 0) [/cpp]
?

[littledump]

thanks

that now makes it terminate on my end

but when i submitted again, it still execeeds time

it gets stuck on input 5 it seems

[kmhasan]

I think you are making a O(n^4) implementation where O(n^3) does the job. And there are opportunities where you can break your search. My solution takes 1.871s which is of course not fast compared to others, but could help you, i guess. I did a simple simulation to find the smallest m value.
Here's my solution:
[cpp]
#include <iostream.h>

bool josephus(int m, int n) {
int *array = new int[n];
int i, j, count;
for (i=0;i<n;i++)
array=i+1;
array[0] = 0;

for (i=1,j=0;i<n;i++) {
count=0;
while (count<m) {
j++; if (j>=n) j=0;
if (array[j]!=0) count++;
}
array[j]=0;
if (i<n-1 && j==1) {
delete array;
return false;
}
}
delete array;
if (j==1) return true;
return false;
}

int main() {
int m,n;
while (true) {
cin>>n;
if (n==0) break;
for (m=1;!josephus(m,n);m++);
cout<<m<<endl;
}
return 0;
}[/cpp]

[littledump]

but compiling and running my code on my pc, it runs extremely fast. evidently < 1 sec for all valid input 3<=n<=150. i do not understand why when it gets to input 5, at about 5 secs, it takes more than 5sec to solve it. There must be another problem?

[littledump]

might the following have something to do with it

or should i say lack of the follow:

[cpp]
using namespace std;
[/cpp]

?

[kmhasan]

Yes you are right. Your program does produce output in less than 1s. But that is for each test case. What I realized is that your solution can get TLE even if the judge input consists of 20 selected cases. The time limit given is for all test cases, not a single case.

You can generate one single input file that has all integers from 3..150 and try to see how much time your program takes for that.

There are many solutions that required 0sec for this problem, I guess most of them are using precomputed tables, you can try that one as well. I won't recommend it though.

[littledump]

i compiled using input from files

it took about 12 seconds to do all 147 valid inputs

why cant it do 5 in 10 seconds for the judge?

[littledump]

im also sending this in through the online submission page

any chance that could have anything to do with it?

most likely not i guess?

[littledump]

well. i made one small change. i dont think it was significant enough to cut over 9 seconds off though, but i guess it was. it now runs in 1.709 seconds

heres my new code:

[cpp]/*
*
* Solves #440 - Eeny Meeny Moo
*
*/

#include <iostream>

using namespace std;

void main(void) {

int *cityOnNet, *cityOffNet;
int citiesOff, citiesOn, nextCity, numCities, m;

while(cin >> numCities && numCities !=0) {
cityOnNet = new int[numCities];
cityOffNet = new int[numCities];

m = 0;

do{
citiesOn = numCities;

for (int i = 0; i < numCities; i++){
cityOnNet = i+1;
cityOffNet = 0;
}

cityOffNet[0] = 1;
citiesOn--;
citiesOff=1;
nextCity=0;

for (int i = 1; i < numCities; i++){
nextCity+=m;
while(nextCity >= citiesOn){
nextCity -= citiesOn;
}
for (int j = 0; j < citiesOn; j++){
if (cityOffNet[i-1] == cityOnNet[j]){
for (int l = j; l < citiesOn; l++){
cityOnNet[l] = cityOnNet[l+1];
}
}
}
cityOffNet = cityOnNet[nextCity];
citiesOff++;
citiesOn--;
}
m++;
}while (cityOffNet[numCities-1] != 2);
cout << m <<endl;
delete [] cityOnNet;
delete [] cityOffNet;
}
}[/cpp]

[sami]

[cpp]

why i am getting TLE?[/cpp]

[Dominik Michniewski]

I think, that's too litle informations to say why

Dominik

[sami]

is there any speciality in its implementation or brute force is the solution..

[gates1]

what's wrong in this, i getting WA

Code: Select all

var a:array[1..100] of shortint;
b:array[1..100] of byte;
i,j,u,z,k,n,r,l:longint;
begin
b[1]:=1;
repeat
inc(i);
readln(a[i]);
until a[i]=0;
n:=i-1;
for i:=1 to n do begin
r:=a[i];
j:=1;
repeat
inc(j);
l:=1;
k:=1;
for z:=2 to r do
b[z]:=0;
        repeat
        u:=0;
                repeat
                inc(l);
                if l=r+1 then begin
                l:=1;
                repeat
                inc(l);
                until b[l]=0;
                end;
                if b[l]=0 then inc(u);
                until u=j;
        b[l]:=1;
                inc(k);
        until k=r;
until l=2;
a[i]:=j;
end;
for i:=1 to n do
writeln(a[i]);
readln;
end.