CareerCup

meet in the middle

1) simple brute force approach have 9^11 complexity. So we can place on each position of key number from some guess or number dont set in any guess.
2) on base brute force we can use meet in the middle approach. We can divide length of guess on two equal parts and iterate brute force for each parts
independent. So we will get lacks for each guess from first part and we have to find them in second part.
this approach have complexity 9^6 in worst case for iterate and 9^5 * log(9^5) for finding lacks.
So time complexity of this solution is O(q^(k/2) * q * log(k / 2))
memory complexity is O(q ^ (k/2))

This dynamic computing solution took me an hour to write and 20 minutes with a compiler to debug, plus I had to check the documentation for next_permutation. That's a pretty hard question to encounter in an interview.

This solution would need lots of comments to really be useful. The idea is that it is going to check every possible combination of which guesses could be right and wrong. Suppose a key element is guessed to be "1" in the first round. If we hypothesize that guess is wrong, then that key element must be equal to one of { "2", "3", "4" }. On the other hand, if that guess is right, then the key element must be in { "1" }. We keep sets to show all the possibilities that any part of the key could be. Each round gives us more constraints for each part of the key. For example, based on our guess in the second round, we might believe that same key element to be in { "1", "3", "4" }. We can intersect one of our hypotheses from the first round { "2", "3", "4" } with the information from the second round { "1", "3", "4" } and derive a new constraint that the key must be in { "3", "4" }.

If it ever looks like the key must be in the empty set { }, then that means we should discard that possibility, because it is impossible. If we end up discarding all possibilities from a round, then there is no way the game was valid. The program prints "Yes" or "No" depending on whether a valid game could exist.

There are an exponential number of combinations that need to be tested, because every hypothesis from one round must be tried with every hypothesis of the other rounds. The algorithm does its best to discard false hypotheses as quickly as possible though. On my laptop, it computes most games instantly, although for the largest games, it can run for over a minute. I consider that to be pretty good for this size of problem though. It's much faster than the simple brute-force approach for most games, but comparable in speed for pathological games.

#include <algorithm>
#include <cstdlib>
#include <iostream>
#include <iterator>
#include <set>
#include <vector>

using std::cin;
using std::cout;
using std::endl;
using std::inserter;
using std::next_permutation;
using std::set;
using std::set_intersection;
using std::vector;

bool check_possible(vector<set<vector<set<int>>>> const &constraints) {
	if (constraints.empty()) {
		return true;
	}

	for (auto choice = constraints.front().begin(); choice != constraints.front().end(); ++choice) {
		vector<set<vector<set<int>>>> intersected_constraints;
		for (auto cascade = ++constraints.begin(); cascade != constraints.end(); ++cascade) {
			set<vector<set<int>>> intersected_round;
			for (auto possibility = cascade->begin(); possibility != cascade->end(); ++possibility) {
				vector<set<int>> intersected_possibility;
				for (size_t elem_idx = 0; elem_idx < possibility->size(); ++elem_idx) {
					set<int> intersected;
					set_intersection(
							(*choice)[elem_idx].begin(), (*choice)[elem_idx].end(),
							(*possibility)[elem_idx].begin(), (*possibility)[elem_idx].end(),
							inserter(intersected, intersected.begin()));
					if (intersected.empty()) {
						break;
					}
					intersected_possibility.push_back(intersected);
				}
				if (intersected_possibility.size() == possibility->size()) {
					intersected_round.insert(intersected_possibility);
				}
			}
			if (intersected_round.empty()) {
				break;
			}
			intersected_constraints.push_back(intersected_round);
		}
		if (intersected_constraints.size() == constraints.size() - 1) {
			if (check_possible(intersected_constraints)) {
				return true;
			}
		}
	}

	return false;
}

int main(int argc, char const *argv[]) {
	int test_case_count;
	cin >> test_case_count;
	for (int test_case_idx = 0; test_case_idx < test_case_count; ++test_case_idx) {
		int n, q, k;
		cin >> n >> k >> q;
		vector<vector<int>> guesses;
		vector<int> scores;
		for (int round_idx = 0; round_idx < q; ++round_idx) {
			guesses.push_back(vector<int>());
			for (int elem_idx = 0; elem_idx < k; ++elem_idx) {
				int elem;
				cin >> elem;
				guesses.back().push_back(elem);
			}
			int score;
			cin >> score;
			scores.push_back(score);
		}

		// There's a utility called iota that could do this block better, but I couldn't remember what it looked like.
		set<int> ALL;
		for (int n_idx = 0; n_idx < n; ++n_idx) {
			ALL.insert(n_idx);
		}

		vector<set<vector<set<int>>>> constraints;
		for (int round_idx = 0; round_idx < q; ++round_idx) {
			constraints.push_back(set<vector<set<int>>>());
			vector<int> const &guess = guesses[round_idx];
			int const &score = scores[round_idx];

			// One of the STL helpers could do this block better too.
			vector<bool> filter;
			for (int i = 0; i < k - score; ++i) {
				filter.push_back(false);
			}
			for (int i = 0; i < score; ++i) {
				filter.push_back(true);
			}

			do {
				vector<set<int>> constraint;
				for (int elem_idx = 0; elem_idx < k; ++elem_idx) {
					if (filter[elem_idx]) {
						set<int> possibilities = { guess[elem_idx] };
						constraint.push_back(possibilities);
					} else {
						set<int> possibilities(ALL);
						possibilities.erase(guess[elem_idx]);
						constraint.push_back(possibilities);
					}
				}
				constraints.back().insert(constraint);
			} while (next_permutation(filter.begin(), filter.end()));
		}

		bool possible = check_possible(constraints);
		if (possible) {
			cout << "Yes" << endl;
		} else {
			cout << "No" << endl;
		}

	}

	return 0;
}

the time limit is 3 sec...i have figured out a brute force solution of doing it by generating all the possible permutations...but that wd definitely time out...how can we optimise it further...any suggestions...

i think n and k are preety small and max. no of operations performed will be (11^11)*8.
So i think it will not time out.

for each pair of guesses, count the number of diff pair:
1 2 3 4 5 (score1)
1 2 3 5 6 (score2)
dirr pairs: 4-5 5-6, then abs(score1 - score2) <= 2.
err chck: 0 <= score <= k

Seems like CSP(en.wikipedia.org/wiki/Constraint_satisfaction_problem):

import scala.util.Sorting
import scala.collection.mutable.ArrayStack
import java.util.Scanner

class Constraint(var key : Array[Int], var score : Int) {
  
}

class KeyState(val i : Int, val possible : Set[Int]) {
}

class State(var s : Array[KeyState]) {
  def score(keyGuess : Array[Int]) = {
    (s zip keyGuess) map { 
      case (keyState, guess) =>
        if(keyState.possible.size == 1 && 
          keyState.possible.contains(guess))
          1
        else
          0
    } sum
  }

  def unassigned() = s filter(_.possible.size > 1)

  def removeFromPossibleUnassigned(key : Array[Int]) = {
    val sNew = s map { keyState =>
      if(keyState.possible.size > 1)
        new KeyState(keyState.i, keyState.possible - key(keyState.i))
      else
        keyState
    }
    new State(sNew)
  }

  def isValid() = ! (s exists (_.possible.size == 0))

  def assign(vars : Array[Int], key : Array[Int]) = {
    val varsSet = vars.toSet
    val sNew = s map { keyState =>
      if(varsSet.contains(keyState.i)) 
        new KeyState(keyState.i, Set(key(keyState.i)))
      else
        keyState
    }
    new State(sNew)
  }
}

object KeyMaster {
  val scanner = new Scanner(Console.in)
  def main(args : Array[String]) : Unit = {
    readAndSolve
  }

  def readInt() = {
    //readf("{0, number, integer}").first.asInstanceOf[Long].toInt
    scanner.nextInt()
  }

  def readAndSolve() = {
    val nTestCases = readInt
    (1 to nTestCases) foreach { _ =>
      val n = readInt
      val k = readInt
      val q = readInt
      val initialState = new State(
        (0 to k-1) map { i =>
          new KeyState(i, (1 to n) toSet) 
        } toArray
      )
      val constraints =  (1 to q) map { _ =>
        val key = (1 to k) map { _ => readInt } toArray
        val score = readInt
        new Constraint(key, score)
      } toArray
      val r : Boolean = nextConstraint(constraints)(initialState)
      if(r) {
        println("Yes")
      } else {
        println("No")
      }
    }
  }

  def nextConstraint(constraints : Array[Constraint]) (s : State) : Boolean = {
    if(constraints.length == 0)
      true
    else {
      val c = constraints(constraints.length - 1)
      val newConstraints = constraints.slice(0, constraints.length - 1)
      resolveConstraint(s, c, nextConstraint(newConstraints))
    }
  }

  def resolveConstraint(s : State, 
                          c : Constraint, 
                          nextConstraint : State => Boolean) : Boolean = {
    val curScore = s.score(c.key)
    if(curScore < c.score) {
      val kNewVars  = c.score - curScore
      val availablePlaces = possiblePlaces(s.unassigned, c.key)
      if(availablePlaces.size >= kNewVars)
        tryAssignVars(s, c, kNewVars, availablePlaces, nextConstraint)
      else
        false
    } else if (curScore == c.score) {
      val sNew = s.removeFromPossibleUnassigned(c.key)
      if(sNew.isValid) 
        nextConstraint(sNew)
      else
        false
    } else {
      false
    }
  }
      
  def possiblePlaces(unassigned : Array[KeyState], key : Array[Int]) = {
    unassigned filter { keyState =>
      keyState.possible.contains(key(keyState.i)) 
    } map(_.i)
  }

  def tryAssignVars(s : State, 
                    c : Constraint, 
                    kVars : Int, 
                    places : Array[Int],
                    nextConstraint : State => Boolean) : Boolean = {
    places.combinations(kVars).foreach { vars =>
      val newState = s.assign(vars, c.key).removeFromPossibleUnassigned(c.key)
      if(newState.isValid && nextConstraint(newState))
        return true
    }
    false
  }

}

Some context:

en.wikipedia.org/wiki/Mastermind_(board_game)

I think we should find the number of matching columns,ie. if input is:
4 4 2
2 1 2 2 0
2 2 1 1 1

here number of matching columns , same=1.
Then find largest and smalllest values of b, here largest=1,smallest=0
Then find diff=largest-smallest
Find nonmatch=q-same

if(match >= lower && nonmatch >=diff)
{
print "yes"
}
else
print "No"

I dont know how valid is my approach,but I got all the test cases correct,but one hidden case went wrong. any further ideas ?