11351 - Last Man Standing

All about problems in Volume 113. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
shakil
Learning poster
Posts: 74
Joined: Sat Jul 15, 2006 6:28 am
Location: CUET , bangladesh
Contact:

11351 - Last Man Standing

Post by shakil »

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

Post by rio »

Do you mean closed formula ? Or some kind of DP-formula ?

----
Rio

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:

Post by sclo »

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

Post by asif_rahman0 »


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

Re: 11351 - Last Man Standing

Post by kissu parina »

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

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

11351 - Last Man Standing

Post by LeonardoB »

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

Post by plamplam »

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) :D :D. 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

Post by plamplam »

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

Post Reply

Return to “Volume 113 (11300-11399)”