## 11351 - Last Man Standing

Moderator: Board moderators

shakil
Learning poster
Posts: 74
Joined: Sat Jul 15, 2006 6:28 am
Contact:

### 11351 - Last Man Standing

I think this problem has a formula.Any one can give some link.
SHAKIL

rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan
Do you mean closed formula ? Or some kind of DP-formula ?

----
Rio

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Contact:
There are different ways to dp it. The most obvious way is O(n).
I don't think there is any explicit formula, but I could be wrong.

asif_rahman0
Experienced poster
Posts: 209
Joined: Sun Jan 16, 2005 6:22 pm

kissu parina
New poster
Posts: 19
Joined: Thu May 20, 2010 8:58 am

### Re: 11351 - Last Man Standing

is there any particular algo for this prob??
i am getting TLE....
one day...

LeonardoB
New poster
Posts: 2
Joined: Wed May 11, 2011 3:39 pm

### 11351 - Last Man Standing

Hi everybody.

I was trying to attack this problem using a tree but got TLE. Which is how I can optimize this?

Code: Select all

``````#include <cstdlib>
#include <string>
#include <sstream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <iostream>
#include <map>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <stack>
#include <cctype>
#include <queue>

using namespace std;

class Node {

public:
int nr, nl, c;
Node * right, * left;
Node () : right (0), left (0), nr(0), nl(0), c(0) {}
};

void fill_tree (Node* tree, int B, int A = 1) {

if (A >= B) return;

Node* n1 = new Node();
n1->nl = A, n1->nr = (A + B) / 2, n1->c = n1->nr - n1->nl + 1;
tree->left = n1;
if (A < B) fill_tree (tree->left, (A + B) / 2, A);

Node* n2 = new Node();
n2->nl = (A + B) / 2 + 1, n2->nr = B, n2->c = n2->nr - n2->nl + 1;
tree->right = n2;
if (A < B) fill_tree (tree->right, B, (A + B) / 2 + 1);
}

int delete_position (Node* tree, int pos) {

--tree->c;

if (tree->nl == tree->nr)
return tree->nl;

if (pos <= tree->left->c)
return delete_position (tree->left, pos);

else
return delete_position (tree->right, pos - tree->left->c);
}

int main() {

int T, K, N;

scanf ("%d", &T);

for (int t = 0; t < T; ++t) {

Node* tree = new Node();
scanf ("%d %d", &N, &K);

tree->nr = 1, tree->nl = N, tree->c = K;
fill_tree (tree, N);

int j = 0;

while (N > 1) {
j = (j + K - 1) % N--;
delete_position (tree, j + 1);
}

printf("Case %d: %d\n", 1 + t, delete_position (tree, 1));
}
}``````
regards

plamplam
Experienced poster
Posts: 150
Joined: Fri May 06, 2011 11:37 am

### Re: 11351 - Last Man Standing

Oh dear, I don't understand a thing you wrote. Sorry Im a newbie and I don't know much about programming. I don't know how to program in c++, however I do know a little of C. Then why am I replying to you? Well, you see the problem is tricky. It is not really very hard, but yes it requires deep thinking. My main function consisted of less than 20 lines and I got AC in first try(0.056 seconds) . I'll give you a hint, there is a much more simple and efficient method. First try to solve it manually without the help of a computer, find a pattern. Good luck.
You tried your best and you failed miserably. The lesson is 'never try'. -Homer Simpson

plamplam
Experienced poster
Posts: 150
Joined: Fri May 06, 2011 11:37 am

### Re: 11351 - Last Man Standing

There might be a particular algorithm for this problem, I used an integer array of size 100010 and my main function consisted of less than 20 lines. No functions, no complications and nothing. Just try to solve the problem mathematically, try it first manually, without the help of a computer. For example if n = 3 and k = 2 then what is the result. If n = 4 and k = 2....etc etc.
If you're getting TLE then you can just use your inefficient code to find out such values and from there may be you will find a pattern?
You tried your best and you failed miserably. The lesson is 'never try'. -Homer Simpson