May 14, 2017 Single Round Match 714 Editorials

We now have some of the SRM 714 Editorials published. Challenges to contribute to the rest of the editorials are still open. If you would like to contribute for an editorial for those problems you may do so by submitting to their respective challenges.
Thanks to dush1729 and stni for contributing to the SRM 714 Editorials. You may discuss the editorials in the match discussion forum.
SRM 714 was held on 7th May 2017. TCO17 Russia Regionals Round took place alongside SRM714. Check out the blog to know more about how the day unfolded at TCO17 Russia Regionals.
SRM 714 Round 1 – Division II, Level One RangeEncoding by dush1729
Since arr will be in strictly increasing order, so new range will start whenever difference between adjacent numbers is greater than 1.
Code:

int ans=1;
class RangeEncoding
{
public:
int minRanges(vector a)
{
for(int i=1;i<a.size();i++) ans+=(a[i]-a[i-1]>1);
return ans;
}
};

Complexity:
O(n), where n is the length of the sequence.
Challenge:
What if arr is given in any order and arr can contain duplicates?
Solution:
We will first have to sort arr, rest code will remain same.
Complexity:
O(nlogn) for sorting
 
SRM 714 Round 1 – Division II, Level Two  RemovingParenthesis by Vetteru
The solution of this problem is the dynamic programming with memoization.
In each state, count up valid step.
For example, we assume that given string is “(()())()”.
Then, valid new strings after removing one pair of parentheses are “(())()”, “()()()”, “()()()”.
In each string removed pairs of indexes were (0, 2), (0, 4), (0, 5).
Note that last two strings are the same, but different indexes are moved.
And then, we can get a formula as follows: count(“(()())()”) = count(“(())()”) + count(“()()()”) + count(“()()()”).
By Recursively calculating the count(…), we can finally get the answer

import java.util.HashMap;
import java.util.Map;
 
public class RemovingParenthesis {
 
    private Map<String, Integer> counts;
 
    public int countWays(String s) {
       counts = new HashMap<>();
        counts.put("", 1);
        return parse(s);
    }
 
    private int parse(String s) {
        if (counts.containsKey(s)) {
            return counts.get(s);
        }
 
        int result = 0;
        int depth = 0;
        for (int i = 0; i < s.length(); i++) {
           char c = s.charAt(i);
           if (c == '(') {
                depth++;
            } else {
                depth--;
 
                String nex;
               if (i == s.length() - 1) {
                    nex = s.substring(1, i);
                } else {
                    nex = s.substring(1, i) + s.substring(i + 1);
                }
 
                result += parse(nex);
                 if (depth == 0) {
                   break;
               }
            }
        }
 
        counts.put(s, result);
        return result;
    }
}
 
 

SRM 714 Round 1 – Division I, Level Three  Saleswoman by stni
We traverse through all positions of people from left to right.We remember the total amount of demand and supply of people behind us ( on the left of the current position ), If the supply surpasses demand, we turn back and trade items to people demanding, clear demand amount and reduce supply by the amount of demand we filled.
We multiply the length from the position of the left most demanding person to the position of the current supplying person, by 2, which means we moved forward and backward, then add it to the total amount of time.
Every time we add these lengths, we moved forward and backward and returned to the original first demanding person, which means we didn’t move at all along the axis after moving backward.
So intuitively, after we finished supplying all items to the demanding people, we add the total length from person[0] to person[n-1].
The route goes like this:

Total Complexity is O(n)
 

#include<vector>
using namespace std;
class Saleswoman{
public:
        int minMoves(vector <int> pos, vector <int> delta){
        int n=(int)pos.size();
        int sup=0;
        int dem=0;
        int ans=0;
        int first_demand=-1;
        for(int i=0;i<n;i++){ if(delta[i]>0&&first_demand!=-1){
                sup+=delta[i];
                if(sup>=dem){
                    ans+=(pos[i]-pos[first_demand])*2;
                    first_demand=-1;
                    sup-=dem;
                    dem=0;
                }
            } else {
                delta[i]*=-1;
                int mi=min(sup,delta[i]);
                sup-=mi;
                delta[i]-=mi;
                if(delta[i]>0){
                    if(first_demand==-1)first_demand=i;
                    dem+=delta[i];
                }
            }
        }
        ans+=pos.back();
        return ans;
    }
};

SRM 714 Round 1 – Division I, Level One ParenthesisRemoval by stni
For all ‘)’, we have to use a ‘(‘ before it to match with it.
The number of ways to match a ‘)’ equals to the number of ‘(‘ left after matching previous ‘)’s,
which equals to the number of ‘(‘ before the current ‘)’ minus the number of ‘)’ before it,
we call this number l,
and multiply it to the answer for each of ‘)’s. You may refer to the Basics of Combinatorics tutorial.
We can do this in a for loop through s.
Overall complexity is O(n), where n is the length of the sequence.

#include<string>
using namespace std;
const long long MOD = 1e9 + 7;
class ParenthesisRemoval {
 public:
  int countWays(string s) {
    long long result = 1;
    long long availableOpeningBrackets = 0;
    for (int i = 0; i < s.length(); i++) {
      if (s[i] == '(') {
        availableOpeningBrackets++;
      } else {
        result *= availableOpeningBrackets;
        result %= MOD;
        availableOpeningBrackets--;
      }
    }
    return (int)result;
  }
};

SRM 714 Round 1 – Division I, Level Two NAddOdd by stni

The problem asks for the sum of g(x) for x between L and R, inclusive.
Let’s compute the sum of g(x) for x between 0 and R, inclusive, say it’s sum(R),
then compute the sum of g(x) for x between 0 and L-1, inclusive, say it’s sum(L-1),
the answer is sum(R) – sum(L-1).
To compute sum(r),
– if r <= K, for x in 0…r, g(x) is 0, so the sum is 0.
– use memoization to prevent repeated calculations.
– Let’s divide x in K+1…r to odd numbers and even numbers.
notice that K will be an odd number according to problem constraints.
– We easily get maximum and minimum of even and odd numbers in K+1…r,
call them maxEven, maxOdd, minOdd and minEven.
Number of even numbers equals to (maxEven-minEven)/2+1,
We need to divide all those even numbers by 2.
So we add the number of even numbers to the answer.
Now these even numbers turns into numbers in 0…r/2,
So we calculate sum(r/2).
Notice that after the even numbers divided by 2,
the divided numbers are still continuous from somewhere between 0 and K to r/2.
Similarly, to solve the odd numbers part,
number of odd numbers equals to (maxOdd-minOdd)/2+1.
We need to add K then divide by 2, so 2 processes pre number,
We add (the number of odd numbers)*2 to the answer.
Now the original odd numbers in K+2…r turns to even numbers in 2*K+2…r+K, (K is odd),
then divided by 2 into continuous numbers in K+1…(r+K)/2,
so we calculate sum((r+K)/2) and add that to the answer.
Because r>K, (r+K)/2 <r, so odd upper bound of the continuous numbers shrinks by at least 1 in the process,
and even upper bound of the continuous numbers shrinks by half.
We use memoization so sum(r) will not be repeatedly calculated,
so total complexity is O(R).
Blue.Mary’s submission

#include<unordered_map>
using namespace std;
typedef long long ll;
int K;
unordered_map<ll, ll>mem;
ll sum(ll r){
    if(r<=K)return 0;
    if(mem.find(r)!=mem.end()){
        return mem[r];
    }
    ll maxEven, maxOdd, minOdd=K+2, minEven=K+1;
    if(r%2==0){
        maxEven=r;
        maxOdd=r-1;
    } else {
        maxOdd=r;
        maxEven=r-1;
    }
    ll ret=0;
    if(minEven<=maxEven){
        ret+=(maxEven-minEven)/2+1;
        ret+=sum(maxEven/2);
    }
    if(minOdd<=maxOdd){
        ret+=((maxOdd-minOdd)/2+1)*2;
        ret+=sum((maxOdd+K)/2);
    }
    return mem[r]=ret;
}
class NAddOdd{
public:
    ll solve(ll L, ll R, int k){
        K=k;
        if(R<=K) return 0;
        if(L<=K) L = K+1;
        mem.clear();
        ll ans = sum(R) - sum(L-1);
        return ans;
    }
};

SRM 714 Round 1 – Division I, Level Three Salesman
We are awaiting the submission for this problem. If you would like to contribute an editorial for this problem you may do so by submitting to this challenge.