Single Round Match 713 Editorials

May 4, 2017 Harshit Mehta

We now have some of the SRM 713 Editorials published. We are awaiting or reviewing the submissions for some of them. If you would like to contribute an editorial for those problems you may do so by submitting to their respective challenge.

Thanks to stni, pakhandimarcose18 for contributing to the SRM 713 editorials.

 

Single Round Match 713 Round 1 – Division II, Level One SymmetryDetection by pakhandi

The problem can be solved by traversing the matrix and checking for symmetry in a greedy / ad-hoc way.
Let us first solve the problem for the vertical-symmetry.
We want to check if, for every cell [i][j], if it is equal to [i][cols – j – 1]. In this case we don’t need to visit every cell. We only need to check this condition for cells in all the rows but only half the columns. The proof of this optimization is very trivial and is left as an exercise for the reader.
For the horizontal-symmetry, we can use the same method for all the columns but half the rows, comparing [i][j] with [rows – i – 1][j].
The method is very similar to what is used for checking palindrome.
Please check the implementation below for details.

class SymmetryDetection 
{
public:
	string detect(vector  board) 
	{
		bool h = 1, v = 1;
		int rows = board.size();
		int cols = board[0].size();
		for(int i = 0; i < rows; i++)
		{
			for(int j = 0; j <= cols / 2; j++)
			{
				if(board[i][j] != board[i][cols - j - 1])
				{
					v = 0;
				}
			}
		}

		for(int i = 0; i <= rows / 2; i++)
		{
			for(int j = 0; j < cols; j++)
			{
				if(board[i][j] != board[rows - i - 1][j])
				{
					h = 0;
				}
			}
		}

		if(h && v)
		{
			return "Both";
		}
		else if(h)
		{
			return "Horizontally symmetric";
		}
		else if(v)
		{
			return "Vertically symmetric";
		}
		else
		{
			return "Neither";
		}
		
	}
};

 

Single Round Match 713 Round 1 – Division II, Level Two PowerEquationEasy by marcose18

In this question we will iterate through all the values & it’s powers which are less than n.

Now we will calculate answer for a number i & it’s powers in one go . Now for some power of i, let’s assume i ^ x we have to calculate all such values where (i ^ x) ^ c = (i ^ y) ^ d such that c, d & i ^ y <= n. Now clearly x, y <= maxpow where i ^ maxpow <= n while i ^ (maxpow + 1) > n.

Also (i ^ x) ^ c = (i ^ y) ^ d implies x * c = y * d. In short (x / y) = (d / c).

So for fixed values of x, y we have to find c & d such that it satisfies above equation while it is also <= n. So to find such c & d, reduce x & y to it’s lowest form by dividing both x & y by gcd(x, y).

Now it’s easy to see that total possible values = n / max(tempx, tempy) where tempx & tempy are x / gcd & y / gcd respectively. Do the above for all values of i and add it to answer. One final thing to note here is if i > sqrt(n) then it contains no power that is less than n i.e i ^ x = i ^ y only for x = y = 1. So each of them will contribute n to the final answer and thus we will loop only upto sqrt(n) instead of n.

Below is the code of above explanation.

Here HashSet is used to keep track of visited numbers and their powers.

import java.util.*;
import java.util.regex.*;
import java.text.*;
import java.math.*;
 
 
public class PowerEquationEasy {
 
// Calculating gcd of two numbers.
   static int gcd(int a, int b) {
   	if (a < b) {
       	int temp = a;
       	a = b;
       	b = temp;
   	}
   	if (b == 0) return a;
   	return gcd(b, a % b);
   }
 
   public int count(int n) {
   	long ans = n * 1L * n;
   	long mod = (long) 1E9 + 7;
 
   	ans %= mod;
       HashSet set = new HashSet<>();
        	
// Iterate through all values but not those which are stored in the hashset which are nothing but powers of earlier values and we have calculated answers for them before.
   	for (int i = 2; i * i <= n; i++) {
       	if (set.contains(i)) continue;
       	int maxpow = 0;
       	int temp = i;
       	while (temp <= n) {
               ++maxpow;
               set.add(temp);
           	temp *= i;
       	}
// Find the answer for all x & y such that (i ^ x) ^ c = (i ^ y) ^ d.
       	for (int x = 1; x <= maxpow; x++)
           	for (int y = 1; y <= maxpow; y++) { int g = gcd(x, y); int tempx = x / g, tempy = y / g; ans += n / Math.max(tempx, tempy); while (ans >= mod) ans -= mod;
      	     }
   	}
// All numbers greater than sqrt(n) will have no power that is less than n and for each of them there will be ‘n’ identities.
   	ans += (n - set.size() - 1) * 1L * n;
   	ans %= mod;
   	return (int) ans;
   }
}

 

 Single Round Match 713 Round 1 – Division II, Level Three DFSCountEasy

We are awaiting or reviewing the submission for the following editorial. If you would like to contribute an editorial for this problem you may do so by submitting to this challenge.

Single Round Match 713 Round 1 – Division I, Level One PowerEquation by stni

 If a=c, b=d, we have n*n identities.
Here, 1^1=1^2=1^3=…=1^n,—-(n-1)
1^2=1^1=1^3=…=1^n,—-(n-1)

1^n=1^1=1^2=…=1^(n-1) —-(n-1)
For a=1 and b=1,
we need to add another n*n-1.
So we already have n*(2*n-1) identities obviously.

For a != c:
Without loss of generality, we say ac.

For all integers not power of other integers p,
let a=p^i, c=p^j
number of c we can choose from equals to
number of powers of least common multiple(LCM) of a and c.
j/gcd(i,j) is the min distance between powers of LCM,
n/(j/gcd(i,j)) is the number of such identities in [1..n]
multiply 2 for symmetry of a-c, b-d

Complexity is O(n)

#include
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
ll gcd(ll a,ll b){
    return a?gcd(b%a,a):b;
}
class PowerEquation{
public:
    int count(int n0){
        ll n=n0;
        setse; //all power bases
        ll ans=n*(n*2-1)%mod;
        for(ll p=2;p*p<=n;p++){
            if(se.count(p))
                continue;   //we already calculated p's base
            ll t=p;
            ll k=0;//number of powers of t
            while(t<=n){
                se.insert(t);
                t*=p;
                k++;
            }
            for(ll i=1;i<=k;i++){ 
                for(ll j=i+1;j<=k;j++){
                    ans+=n/(j/gcd(i,j))*2;
                    ans%=mod;
                }
            }
        }
        return (int)ans;
    }
};

 

Single Round Match 713 Round 1 – Division I, Level Two DFSCount by stni

We use an 15-bit integer to remember which nodes we visited during the dfs process. If we have visited the i-th node, we set the i-th bit to 1. If it is not visited, the i-th bit is set to 0. We need a dfs function with two parameters.
The parameters being an integer as the 15-bit integer and an integer which keeps the last visited node.
In dfs:
If all nodes connected to the last node are visited -there is only 1 way to do dfs which is “to do nothing and return”.
If there is a node i connected to this node and not visited,  -we can append i to p.
We dfs with node i as last visited node, get the number of ways we can do dfs, and 15-bit visited nodes. We get the second integer which shows the nodes we visited from i. If we do the dfs again from last node with parameter visited being the newly returned visited integer.
The ways to do dfs from last node is to multiply these 2 returned values because 2 orders exist. Suppose nodes visited in the first dfs are n1, nodes visited in the second dfs are n2.
We can visit n1 then visit n2, so after i we append n1 then n2 to p.
We can also visit n2 then n1, so after i we append n2 then n1 to p.
They all start from last node, and n1 includes node i. If we have a set of nodes not visited and we visited node last, the number of ways we can do dfs is always the same. So we memoize that in a 2D vector to avoid repeated calculations. The first dimension is all 15-bit integer which stores the visited nodes, size 1<<n, The second dimension is 15, which is the last node we visited.

We have n nodes, each has n potential positions.
Complexity is O(n^2)

#include
#include
#include
using namespace std;
typedef long long ll;

vectorG;
vector<array<pair<ll,ll>, 15>>mem;
class DFSCountEasy{
public:
    pair<ll,ll> dfs(ll visited, ll last){
        if(mem[visited][last].second)return mem[visited][last];
        pair<ll,ll> r(0,0);
        for(int i=0;i<G.size();i++){
            if((last!=G.size()&&G[last][i]=='N')||(visited&(1ll<<i)))continue;
            pair<ll,ll>t1=dfs(visited|(1<<i), i);
            pair<ll,ll>t2=dfs(t1.second,last);
            r.first+=t1.first*t2.first;
            r.second=t1.second|t2.second;
        }
        if(r.second==0){
            r=make_pair(1, visited);
        }
        return mem[visited][last]=r;
    }
    ll count(vectorG){
        ::G=G;
        mem.clear();
        mem.resize(1<<G.size());
        pair<ll,ll> r=dfs(0,G.size());
        return r.first;
    }
};

 Single Round Match 713 Round 1 – Division I, Level Three CoinsQuery 

We are awaiting or reviewing the submission for the following editorial. If you would like to contribute an editorial for this problem you may do so by submitting to this challenge.

The post Single Round Match 713 Editorials appeared first on Topcoder.

Previous Article
Data Science Weekly Challenges: Week #6
Data Science Weekly Challenges: Week #6

Week #5 Challenge Update As a reminder, the week #5 challenge was… …The competitor who has the shortest cod...

Next Article
Design Spotlight: Erianto Ongko and Tewibowo, GE Transportation Champions
Design Spotlight: Erianto Ongko and Tewibowo, GE Transportation Champions

In this blog post, we are featuring 2 designers, and it’s a special one because we spotlight the GE Transpo...