stone division code

[mandeepsingh1616]

Consider the following game:

There are two players, First and Second, sitting in front of a pile of stones. First always plays first.
There is a set, , of distinct integers defined as .
The players move in alternating turns. During each turn, a player chooses some and splits one of the piles into exactly smaller piles of equal size. If no exists that will split one of the available piles into exactly equal smaller piles, the player loses.
Both players always play optimally.

Given , , and the contents of , find and print the winner of the game. If First wins, print First; otherwise, print Second.

Input Format

The first line contains two space-separated integers describing the respective values of (the size of the initial pile) and (the size of the set).
The second line contains distinct space-separated integers describing the respective values of .

Constraints

Output Format

Print First if the First player wins the game; otherwise, print Second.

Sample Input 0

15 3
5 2 3

Sample Output 0

Second

Explanation 0

The initial pile has stones, and . During First's initial turn, they have two options:

Split the initial pile into equal piles, which forces them to lose after the following sequence of turns:
stone-division.png
Split the initial pile into equal piles, which forces them to lose after the following sequence of turns:
stone-division-2.png

Because First never has any possible move that puts them on the path to winning, we print Second as our answer.

Submissions: 214

Max Score:

50

Difficulty:

Hard

Rate This Challenge:
More


my code is this but it not pass all the test cases
so i need answer for this

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;


int main() {
    /* Enter your code here. Read input from STDIN. Print output to STDOUT */  
    int n,m;
    int flag=0;
    cin>>n;
    
    cin>>m;
    int arr[m];
    for(int i=0;i<m;i++){
        cin>>arr[i];
    }
    for(int i=0;i<m;i++){
        if(n%arr[i]==0){
            int a=arr[i];
            if(a%2!=0){
                flag=1;
            }
            else
            {
                flag=0;
            }
              
            
        }    
    }
    if(flag==1){
        cout<<"Second";
    }
    else{
        cout<<"First";
    }
    
    return 0;
}

[2kaud]

When posting code, please use code tags so that the code is readable. Go Advanced, select the formatted code and click '#'.

For the test cases where your code doesn't provide the correct answer, have you traced through the code with the debugger to see why?

[wolle]

my code is this but it not pass all the test cases
so i need answer for this

Here's what seems like the original description of the problem:

https://www.hackerrank.com/challenges/stone-division

I don't see anything in your code suggesting there are two players (taking turns at splitting piles)?

One approach would be to introduce a sequence of piles (SoP) where each pile is an integer telling how many stones are in that pile. All possible splits of SoPs can then be generated recursively until no further split is possible (whereby the recursive path up to that point represents one game the player on turn has lost.)

I can think of a way to implement the SoPs quite densely but it's still an exhaustive combinatorial solution. There may be some number theoretical or combinatorial results available that could simplify things. I don't know really. Also I don't quite understand what's meant by "both players play optimally"? It's not quite clear to me who wins if both players can win?

[2kaud]

Also I don't quite understand what's meant by "both players play optimally"

A player always makes the best possible move that would enable that player to win. ie a player can't play to loose or to give advantage to the other player or to lessen their own chances of winning.

There is actually no need to play out the game from a starting point. All that is needed is to determine which player can't win from a position. If a player can't win, then the other player by default is the winner.

[wolle]

A player always makes the best possible move that would enable that player to win. ie a player can't play to loose or to give advantage to the other player or to lessen their own chances of winning.

There is actually no need to play out the game from a starting point. All that is needed is to determine which player can't win from a position. If a player can't win, then the other player by default is the winner.

I'm not so sure about that, or rather it depends on what is meant by playing "optimally".

I've implemented the game with optimal playing defined by these rules: A player must, if possible,

1. split a single pile into unsplittable piles (instant winning move)
2. split a pile to produce an even number of once-splittable piles (deferred winning move)
3. not split a pile to produce an odd number of once-splittable piles (deferred losing move)

With this quite reasonable definition a optimal playing the game can still be won by both players depending on how the splitting unfolds so to me it looks like all possible games have to be investigated.

It cannot be ruled out that there exists an optimal strategy for this game like it does for the Game of Nim for example, but that's a different ballgame. It cannot be expected from participants in a programming contest to come up with a thorough math analysis of a non-trivial game. On the other hand the constrains specified for this game potentially can give rise to a "combinatorial explosion" so one cannot rule out that there's some clever shortcut available.

Anyway here is my implementation. It recursively generates all possible outcomes of the game. The objective was to be able to follow the behavior of the game, not to optimize speed. As I mentioned, both players can win and I cannot tell whether this is due to a mistake in the implementation or the way it should be. Unfortunately I've had only one officially verified test-case available (given in the game description). The program starts in the test() function. I've used Visual Studio 2017 Community:

#include <vector>
#include <set>
#include <string>
#include <iostream>
#include <algorithm>

using Pile = int; // a pile
using SoP = std::vector<Pile>; // sequence of piles
using SoPstack = std::vector<SoP>; // stack of SoPs
using Set = std::vector<int>; // set of divisors

bool splittable(Pile pile, int divisor) { // pile is splittable by this divisor?
	return (pile % divisor) == 0;
}

Pile split(Pile pile, int divisor) { // do split
	return pile / divisor;
}

bool splittable(Pile pile,  const Set& set) { // pile is plittable by some divisor?
	for (const int divisor : set) {
		if (splittable(pile, divisor)) return true;
	}
	return false;
}

bool splittable(const SoP& sop, const Set& set) { // is there at least one splittable pile in this SoP?
	for (const Pile pile : sop) { 
		if (splittable(pile, set)) return true;
	}
	return false;
}

bool once_splittable(Pile pile, const Set& set) { // pile is splittable exactly once?
	for (const int divisor : set) {
		if (splittable(pile, divisor)) { // splittable once - OK
			Pile p = split(pile, divisor);
			if (splittable(p, set)) return false; // splittable twice - bad
		}
	}
	return true;
}

int num_once_splittable(const SoP& sop, const Set& set) { // count number of once_splittable piles in SoP
	int piles = 0;
	for (const Pile pile : sop) { 
		if (once_splittable(pile, set)) ++piles;
	}
	return piles;
}


void printgame(int depth, int& count, int&first, SoPstack& stack, const SoP& winner) { // print game and update counters
	++count;
	std::cout << "new game " << (count) << std::endl;
	int level = 0;
	for (const SoP& sop : stack) {
		std::cout << ">" << (level++) << ": ";
		for (Pile pile : sop) std::cout << pile << " ";
		std::cout << std::endl;
	}
	std::cout << ">" << (level) << ": ";
	for (Pile pile : winner) std::cout << pile << " ";
	std::cout << std::endl;

	if (((level % 2) == 1)) {
		++first;
		std::cout << "game over, first won" << std::endl;
	} else {
		std::cout << "game over, second won" << std::endl;
	}
}

	// each recursive call is one turn of the game
void play(const SoP& sop, const Set& set, int depth, int& count, int&first, SoPstack& stack) {

	stack.push_back(sop); // push current SoP

	std::set<Pile> unique;
	for (const Pile pile : sop) unique.insert(pile); // extract set of unique piles

	SoPstack moves;
	for (const Pile pile : unique) { // collect all valid splits (moves)
		SoP nxt = sop;
		nxt.erase(std::find(nxt.begin(),nxt.end(), pile)); // remove pile to be split

		for (const int divisor : set) { 
			if (splittable(pile, divisor)) { // split pile with valid divisors
				Pile p = split(pile, divisor); // do split
				SoP move = nxt;
				if (splittable(p, set)) {
					for (int i=0; i<divisor; ++i) move.push_back(p); // add on split piles (if splittable)
				}
				moves.push_back(move);
			}
		}
	}

	bool endgame = false;

	if (!endgame) {  // find winning split (last pile split to non-splittable piles)
		for (const SoP& move : moves) {
			if (move.empty()) {
				printgame(depth, count, first, stack, move);
				std::cout << "(by splitting final pile into non-splittable piles)" << std::endl;
				endgame = true;
				break;
			}
		}
	}

	if (!endgame) { // find winning split (even number of once-splittable piles)
		for (const SoP& move : moves) {
			int piles = num_once_splittable(move, set);
			if (piles != move.size()) piles = 0; // all piles must be once-splittable

			if ((piles != 0) && ((piles % 2) == 0)) { // even number of piles
				printgame(depth, count, first, stack, move);
				std::cout << "(by leaving an even number of once-splittable piles)" << std::endl;
				endgame = true;
				break;
			}
		}
	}

	if (!endgame) { // avoid a losing split (odd number of once-splittable piles)

		SoPstack moves2;
		for (const SoP& move : moves) {
			int piles = num_once_splittable(move, set);
			if (piles != move.size()) piles = 0; // all piles must be once-splittable

			if ((piles == 0) || (piles % 2) == 0) moves2.push_back(move); // not a losing move
		}

		if (!moves2.empty()) moves = std::move(moves2); // no losing moves
	}

	if (!endgame) { // no winning split - investigate all valid splits (moves)
		for (const SoP& move : moves) {
			play(move, set, depth+1, count, first, stack); // next game level
		}
	}

	stack.pop_back(); // pop current SoP
}

void stone_division(const SoP& sop, const Set& set) {
	if (sop.empty() || set.empty()) {
		std::cout << "Stone Division: Invalid input !!!" << std::endl;
		return;
	}
	std::cout << "*** Stone Division ***" << std::endl;
	int count=0, first=0;
	play(sop, set, 0, count, first, SoPstack{});
	std::cout << "*** End ***" << std::endl;
	std::cout << "total games=" << (count);
	std::cout << ", first won=" << (first) << std::endl;
}

void test() {
	stone_division(SoP{Pile(15)}, Set{5,2,3});
//	stone_division(SoP{Pile(15)}, Set{15,5});
//	stone_division(SoP{Pile(8)}, Set{4,2});
//	stone_division(SoP{Pile(12)}, Set{4,3,2});
//	stone_division(SoP{Pile(9)}, Set{3});
//	stone_division(SoP{Pile(45)}, Set{15,5,3});
}

[2kaud]

Anyway here is my implementation

As it's a programming challenge, that's why I haven't posted a solution!

[wolle]

As it's a programming challenge, that's why I haven't posted a solution!

It's a challenge, not a contest. It's like the difference between a voluntary exercise and a grade-affecting homework. The challenge is publicly available in the "practice" department at HackerRank and there's even a "reveal solutions" button for members. But okay I'll discuss the solution I think I've found in general terms only.

I have used the implementation in my previous post to test a well known optimal strategy in game theory. I call it Strategy X not to reveal too much. It seems to work but to rely on it one must first formally prove that it works for this game indeed.

Anyway I now understand the meaning of "both players play optimally". The rules 1-3 (see my previous post) only stipulate the obvious namely that a player must make a winning move whenever possible. But to play optimally a player must also play according to a global winning strategy if one exists for the game, like Strategy X.

Applying Strategy X means each player tries to make a split that sets the player on a winning path the other player cannot break. So the game reduces to the question of which player can first make the winning strategic split. Jostling for this split typically ends quickly. If the first player cannot make it in the first turn of the game the second player usually can make it in the next (if the first player hasn't anticipated that and made a preventive split).

A proper solution to this game would be;

1. Prove that Strategy X applies to the game.
2. Write a program that generates all possible outcomes of the game according to rules 1-3 and Strategy X.

And it looks like Strategy X is stronger than the rules 1-3 so 2 becomes,

2. Write a program that generates all possible outcomes of the game according to Strategy X.

Finally here's a tutorial on this kind of games,

https://www.topcoder.com/community/d...gorithm-games/