
July 30th, 2017, 09:12 AM
#1
stone division code
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 spaceseparated integers describing the respective values of (the size of the initial pile) and (the size of the set).
The second line contains distinct spaceseparated 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:
stonedivision.png
Split the initial pile into equal piles, which forces them to lose after the following sequence of turns:
stonedivision2.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
Code:
#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;
}
Last edited by 2kaud; July 30th, 2017 at 10:45 AM.
Reason: Added code tags

July 30th, 2017, 10:48 AM
#2
Re: stone division code
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?
All advice is offered in good faith only. You are ultimately responsible for the effects of your programs and the integrity of the machines they run on. Anything I post, code snippets, advice, etc is licensed as Public Domain https://creativecommons.org/publicdomain/zero/1.0/
C, C++ Compiler: Microsoft VS2017.2

July 31st, 2017, 02:02 PM
#3
Re: stone division code
Originally Posted by mandeepsingh1616
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/stonedivision
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?

July 31st, 2017, 02:27 PM
#4
Re: stone division code
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.
All advice is offered in good faith only. You are ultimately responsible for the effects of your programs and the integrity of the machines they run on. Anything I post, code snippets, advice, etc is licensed as Public Domain https://creativecommons.org/publicdomain/zero/1.0/
C, C++ Compiler: Microsoft VS2017.2

August 4th, 2017, 02:07 AM
#5
Re: stone division code
Originally Posted by 2kaud
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 oncesplittable piles (deferred winning move)
3. not split a pile to produce an odd number of oncesplittable 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 nontrivial 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 testcase available (given in the game description). The program starts in the test() function. I've used Visual Studio 2017 Community:
Code:
#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 nonsplittable piles)
for (const SoP& move : moves) {
if (move.empty()) {
printgame(depth, count, first, stack, move);
std::cout << "(by splitting final pile into nonsplittable piles)" << std::endl;
endgame = true;
break;
}
}
}
if (!endgame) { // find winning split (even number of oncesplittable piles)
for (const SoP& move : moves) {
int piles = num_once_splittable(move, set);
if (piles != move.size()) piles = 0; // all piles must be oncesplittable
if ((piles != 0) && ((piles % 2) == 0)) { // even number of piles
printgame(depth, count, first, stack, move);
std::cout << "(by leaving an even number of oncesplittable piles)" << std::endl;
endgame = true;
break;
}
}
}
if (!endgame) { // avoid a losing split (odd number of oncesplittable 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 oncesplittable
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});
}
Last edited by wolle; August 4th, 2017 at 04:25 AM.

August 4th, 2017, 04:46 AM
#6
Re: stone division code
Anyway here is my implementation
As it's a programming challenge, that's why I haven't posted a solution!
All advice is offered in good faith only. You are ultimately responsible for the effects of your programs and the integrity of the machines they run on. Anything I post, code snippets, advice, etc is licensed as Public Domain https://creativecommons.org/publicdomain/zero/1.0/
C, C++ Compiler: Microsoft VS2017.2

August 5th, 2017, 01:55 AM
#7
Re: stone division code
Originally Posted by 2kaud
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 gradeaffecting 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 13 (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 13 and Strategy X.
And it looks like Strategy X is stronger than the rules 13 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...gorithmgames/
Last edited by wolle; August 7th, 2017 at 11:14 PM.
Posting Permissions
 You may not post new threads
 You may not post replies
 You may not post attachments
 You may not edit your posts

Forum Rules

Click Here to Expand Forum to Full Width
This a Codeguru.com survey!
OnDemand Webinars (sponsored)
