11351 - Last Man Standing

[shakil]

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

[rio]

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

----
Rio

[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]

Look at this:
http://online-judge.uva.es/board/viewto ... ight=10015

[kissu parina]

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

[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]

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.

[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?