Topcoder SRM 709 DIV 2 500pt Permatchd2 solution

Problem Statement
	Hero has a simple undirected graph. (Simple means that each edge connects two different vertices, and each pair of vertices is connected by at most one edge.) A graph is considered pretty if it is a simple undirected graph in which each connected component contains an even number of edges. You are given the adjacency matrix of Hero's graph as a vector <string> graph. ('Y' means that the two vertices are connected by an edge, 'N' means that they aren't.) Change Hero's graph into a pretty graph by adding as few edges as possible. Return the minimum number of edges you have to add, or -1 if Hero's graph cannot be changed into a pretty graph.
Definition
	Class: Permatchd2 Method: fix Parameters: vector <string> Returns: int Method signature: int fix(vector <string> graph) (be sure your method is public)
Limits
	Time limit (s): 2.000 Memory limit (MB): 256 Stack limit (MB): 256
Notes
-	Don't forget that the graph you'll obtain after adding the edges must still be simple.
Constraints
-	n will be between 1 and 50, inclusive.
-	graph will contain exactly n elements.
-	Each element in graph will contain exactly n characters.
-	Each character in graph will be either 'N' or 'Y'.
-	For all valid i graph[i][i] will be equal to 'N'.
-	For all valid i, j graph[i][j] will be equal to graph[j][i].
Examples
0)
	{"NYN", "YNN", "NNN"} Returns: 1 This is the adjacency matrix of a simple graph on three vertices. Two of the three vertices are connected by an edge. Here, an optimal solution is to add one edge that will connect the remaining vertex to one of the other two. The resulting graph is a simple graph with a single connected component. The connected component contains two edges, which is an even number.
1)
	{"NYY", "YNN", "YNN"} Returns: 0
2)
	{"NYY", "YNY", "YYN"} Returns: -1
3)
	{"NYYY", "YNYY", "YYNN", "YYNN"} Returns: 1
4)
	{"NYNNNN", "YNNNNN", "NNNYNN", "NNYNNN", "NNNNNY", "NNNNYN"} Returns: 3
5)
	{"N"} Returns: 0

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.

Solution:

  The size of the number of nodes is less than 50, which means we can use direct search on graph.
  First, we build the graph.
  Second, search all the nodes that have not been searched. Create unions with edge and nodes numbers.
  Then we search all the unions and record the number of ugly unions(unions that have odd number of edges).
   If there's only one ugly union in the whole graph, we want to see if all the nodes are connected. If not, we could connect any pair of unconnected nodes to make it a pretty graph. print "1".
   If there exists at least one union with even number of edges, we could create a pretty graph by connecting all ugly unions to this pretty union. print the number of ugly unions.
   If there's only ugly unions in the graph, we connect all of them together and add one edge to any pair of unconnected nodes to make it a pretty graph. print the number of ugly unions - 1 + 1 = number of ugly unions.
  The interesting magic of this problem is that we can reduce the cases to two: only one ugly union & exists at least one pretty union.

Codes:

// BEGIN CUT HERE

// END CUT HERE

#line 5 "Permatchd2.cpp"

#include<bits/stdc++.h>

using namespace std;

int a[55][55];

int size[55];

int edge, node;

int vis[55];

int kk[55], gg[55];

int ss;

bool flag;

void dfs(int root){

vis[root] = 1;

edge += size[root];

for(int i = 1; i <= size[root]; i++){

if(!vis[a[root][i]]){

node++;

dfs(a[root][i]);

}

}

}

class Permatchd2 {

public:

int fix(vector <string> graph) {

int n = graph.size();

for(int i = 0; i < n; i++){

for(int j = 0; j < n; j++){

if(graph[i][j] == 'Y') size[i]++, a[i][size[i]] = j;

}

}

for(int i = 0; i < n; i++){

edge = 0, node = 1;

if(!vis[i]){

ss++;

dfs(i);

kk[ss] = edge / 2;

gg[ss] = node;

if(kk[ss] < node * (node - 1) / 2){

flag = 1;

}

}

}

int count = 0;

for(int i = 1; i <= ss; i++){

if(kk[i] % 2 == 1) count++;

}

//return count;

int ans = 0, remain = ss - count;

if(ss == 1 && count == 1) {

if(flag) return 1;

else return (-1);

}

else return count;

}

};

Topcoder SRM 709 DIV 2 250pt Robofactory solution

Problem Statement
	Hero owns a factory. There are n robots working at the factory. The robots are numbered 0 through n-1. Today, exactly one of the robots became corrupted. Hero has decided to give all robots a test that may determine the number of the corrupted robot. The test works as follows: For each x from 0 to n-1, in order, Hero tells robot x a positive integer and the robot answers whether the integer is odd or even. Each normal robot will always give the correct answer. The corrupted robot may sometimes give the opposite answer. More precisely: the corrupted robot will answer incorrectly if and only if the previous robot was given an odd number. In particular, if robot 0 is the corrupted robot, it will give the correct answer (as there is no previous robot). You are given a log of the test: a vector <int> query and a vector <string> answer, each with n elements. For each x, query[x] is the positive integer given to robot x, and answer[x] is the answer given by the robot: either "Odd" or "Even". It is guaranteed that the situation described by query and answer could have occurred as described above. If it is possible to determine the index of the corrupted robot, return it. Otherwise, return -1.
Definition
	Class: Robofactory Method: reveal Parameters: vector <int>, vector <string> Returns: int Method signature: int reveal(vector <int> query, vector <string> answer) (be sure your method is public)
Limits
	Time limit (s): 2.000 Memory limit (MB): 256 Stack limit (MB): 256
Constraints
-	n will be between 1 and 50, inclusive.
-	query and answer will contain exactly n elements.
-	Each element in query will be between 1 and 1000, inclusive.
-	Each element in answer will be either "Odd" or "Even".
-	It is guaranteed that there will be at least one possible number of the corrupted robot.
Examples
0)
	{3,2,2} {"Odd", "Odd", "Even"} Returns: 1 Robot 1 gave the wrong answer. Thus, robot 1 is the corrupted robot.
1)
	{1,3,5,10} {"Odd", "Odd", "Odd", "Even"} Returns: 0 All robots gave correct answers. Still, we can deduce that the corrupted robot must be robot 0. For example, robot 1 cannot be the corrupted robot: as robot 0's number was odd, robot 1 would have answered incorrectly if it were corrupted.
2)
	{2,3,5,10} {"Even", "Odd", "Odd", "Even"} Returns: -1 Again, all robots gave correct answers. This time we cannot be sure which robot is corrupted. All we know is that it is either robot 0 or robot 1. Both possibilities are consistent with the given input data. Thus, we should return -1.
3)
	{2,4,6,10} {"Even", "Even", "Even", "Even"} Returns: -1
4)
	{107} {"Odd"} Returns: 0
5)
	{1,1,1} {"Odd", "Odd", "Even"} Returns: 2

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.

Solution:

  The key of this problem is to remember that there's exactly one corrupted robot. We could assume that robot#0 is not at first, and then search the next n - 1 robots. Once we find a robot that does not satisfy "the corrupted robot will answer incorrectly if and only if the previous robot was given an odd number", it's the corrupted robot. When we are searching throw robot #1 to robot #n - 1, we record the number of robots whose previous robot number is even because we cannot judge if the robot is the corrupted one.
  Finally, if we have more than 0 robots undecided with 0 robots that are corrupted, print "-1" because we don't know which one is corrupted between robot #0 and robots undecided.
if we have 0 robots undecided remained, print "0" because we know there's one robot that is corrupted and it must be robot #0.

Code:

#include <bits/stdc++.h>
using namespace std;
int a[1002];
map <string, int> m;
class Robofactory{
  public:
    int reveal(vector<int> query, vector <string> answer){
    m["Odd"] = 1, m["Even"] = 0;
    int different = 0, wrong = -1;
    a[0] = query[0] % 2;
        //if(a[0] == m[answer[0]]) wrong++; else different++;
    for(int i = 1; i < query.size(); i++){
    a[i] = query[i] % 2;
    if(a[i - 1] == 0) different++;
    if(m[answer[i]] != a[i]){
    if(a[i - 1] == 1) wrong = i;
    }
    }
    if(wrong != -1) {
    return wrong;
    }
    else{
     if(different == 0) return 0;
     else return (-1);
    }
    }
};