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, pakhandi, marcose18 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 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.