 # Contest 2 - Hints to Problems [OFFICIAL]

will someone please explain matched brackets problem? I am unable to understand the second part of the question. (specially the first positions)

I’m not sure why my logic is wrong. I am keeping track of encountered flavours in unordered_map(since insert is O(1)) and if the length of map is equal to “k” then I’m checking if max<count.
Current complexity is O(n+n) which can be reduced to O(n)

``````#include <iostream>
#include<unordered_map>
#include<vector>
using namespace std;

int main() {
long long int t, n ,k, p, max=0, count=0; vector<long long int> ar; unordered_map<long long int, int> l;
std::cin >> t;
while(t--)
{
std::cin >> n>>k; max=0; count=0; ar.clear(); l.clear();

while(n--)
{
std::cin >> p;
ar.push_back(p);
}
if(k==1)
{
std::cout << 0 << std::endl;
continue;
}
for(p=0;p<ar.size();p++)
{
l[ar[p]]=1;

if(l.size()==k)
{
if(max<count)
max=count;
l.clear();
count=0;
}
count++;
//std::cout << max<<"---"<<count << std::endl;
}
if(max<count)
max=count;
std::cout << max << std::endl;
}
return 0;
``````

}

in stupid machine question, i’ve implemented it through brute force. Following is my solution link: https://www.codechef.com/viewsolution/44713205
. It is giving correct answer. but my analysis shows that it’s worst case time complexity is O(n^2) when s[1…n] is reverse sorted. So, why does it not give TLE? Can anyone help me to figure out whether my analysis was wrong or something else. Thnx in advance.

i tried and make a class
but it dident work in submition time `# Python program to convert infix expression to postfix

# Class to convert the expression

class Conversion:

``````# Constructor to initialize the class variables
def __init__(self, capacity):
self.top = -1
self.capacity = capacity
# This array is used a stack
self.array = []
# Precedence setting
self.output = []
self.precedence = {'+':1, '-':1, '*':2, '/':2, '^':3}

# check if the stack is empty
def isEmpty(self):
return True if self.top == -1 else False

# Return the value of the top of the stack
def peek(self):
return self.array[-1]

# Pop the element from the stack
def pop(self):
if not self.isEmpty():
self.top -= 1
return self.array.pop()
else:
return "\$"

# Push the element to the stack
def push(self, op):
self.top += 1
self.array.append(op)

# A utility function to check is the given character
# is operand
def isOperand(self, ch):
return ch.isalpha()

# Check if the precedence of operator is strictly
# less than top of stack or not
def notGreater(self, i):
try:
a = self.precedence[i]
b = self.precedence[self.peek()]
return True if a <= b else False
except KeyError:
return False

# The main function that
# converts given infix expression
# to postfix expression
def infixToPostfix(self, exp):

# Iterate over the expression for conversion
for i in exp:
# If the character is an operand,
if self.isOperand(i):
self.output.append(i)

# If the character is an '(', push it to stack
elif i == '(':
self.push(i)

# If the scanned character is an ')', pop and
# output from the stack until and '(' is found
elif i == ')':
while( (not self.isEmpty()) and
self.peek() != '('):
a = self.pop()
self.output.append(a)
if (not self.isEmpty() and self.peek() != '('):
return -1
else:
self.pop()

# An operator is encountered
else:
while(not self.isEmpty() and self.notGreater(i)):
self.output.append(self.pop())
self.push(i)

# pop all the operator from the stack
while not self.isEmpty():
self.output.append(self.pop())

print("".join(self.output))
``````

for _ in range(int(input())):
n = int(input())
exp = input()
obj = Conversion(len(exp))
obj.infixToPostfix(exp)
`

for brackets matching problem how to store index of max depth ??
can anyone tell me ??

``````t = int(input())
for co in range(t):
n = int(input())
s = input()
awin = 0
bwin = 0
shots = 0
for i in range(0,len(s),2):
if(s[i]=="1"):
awin +=1
shots += 1
if(awin>(bwin+((len(s)-shots+1)/2))):
break
if(s[i+1]=="1"):
bwin +=1
shots += 1
if(awin>(bwin+((len(s)-shots)/2))):
break
print(shots)
``````

Can please anyone help me out to find where I am wrong?? I am not able to figure out why this code is giving wrong answer in PSHOT. I have tried the given testcases and they are giving me correct output.

Why this is giving me WA in two cases?

``````#define ll long long

using namespace std;

void solve(){

ll n, x, y;
cin>>n>>x>>y;

vector<pair<ll,ll>> c(n);
ll v[x];
ll w[y];

for(ll i = 0; i < n; i++){
pair<ll,ll> p;
cin>>p.first>>p.second;
c[i] = p;
}
for(int i = 0; i < x; i++){
cin>>v[i];
}
for(int i=0 ; i < y; i++){
cin>>w[i];
}

ll ans = 10000000;

sort(v,v+x);
sort(w,w+y);

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

ll mV = upper_bound(v, v+x, c[i].first)-v;
ll mW = lower_bound(w, w+y, c[i].second)-w;

if(mV < x && mW < y && mV >0){
ll k = w[mW]-v[mV-1]+1;
//cout << mV << " " << mW << endl;
ans = min(ans, k);
}
}

cout << ans << "\n";
}

int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
int t = 1;

while(t>0){
solve();
t--;
}
return 0;
}
``````

// WHATS WRONG IN MY CODE OF COMPILERS AND PARSERS

long long solve(){
string s;
cin>>s;

``````stack<char> st;
long long count=0;

for(int i=0;i<s.length();i++){
if(s[i]=='<') {
st.push(s[i]);
}
else if(!st.empty()){
count++;
st.pop();
}
else return count*2;
}
return count*2;
``````

}

STUPMATCH

I don’t undestand why I have WA for this code in python for the Stupid Machine problem:

``````tests = int(input())

for _ in range(tests):
n = int(input())
tokens = [int(n) for n in input().split()]
min_value = min(tokens)
min_index = tokens.index(min_value)
result = n * min_value + min_index
print(result)
``````

It passes all tests I have done. Can anyone help me, please?

Consider the test input:

``````1
2
5 1
``````

Shoud I get 3? This is my result…
n = 2
min_value = 1
min_index = 1
result = n * min_value + min_index
result = 2 * 1 + 1 = 3

You should get `6`: pick L=2 (gives 2 tokens), then L=1, 4 times (gives 4 more tokens).

Thanks ssjgz, seems I missunderstood the problem.

1 Like

Using set to track flavour will increase time complexity. Better algorithm is to use an array “freq” to store the frequency of each flavour in range (l,r). See Solution or see the following code. Comment if you have any question. HAPPY CODING.

``````#include<bits/stdc++.h>
using namespace std;

#define rep(i,n) for (int i = 0; i<n; i++)
#define rrep(i,n) for (int i = n-1; i >= 0; i--)

#define ll long long
#define endl "\n"

int main(){

//fast IO
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);

int t;
cin>>t;
while(t--){

int n,k;
cin>>n>>k;
int arr[n];
rep(i,n) cin>>arr[i];

int freq[k+1]; // to store frequencies
rep(i,k+1) freq[i] = 0; // initialize with zero

int l = 0, r = 0; // l = lower bound, r = upper bound
freq[arr]++;
int max_lenght = 1;
int count = 1; // stores the numbers of flavour in range [l,r]

// let arr is our ans initially so max_lenght = count = 1 and r = l = 0

while(l<=r && r<n){

if (count<k){

max_lenght = max(max_lenght,r-l+1); // update max_lenght

r++; // increase upper bound

if (r<n){
if (freq[arr[r]] == 0) count ++; // if freq[arr[r]] == 0, then add it to count (since it's new flavour)
freq[arr[r]]++; // increase freq
}

}
else{
if (freq[arr[l]] == 1) count --; // if freq[arr[l]] == 1, then after l++, this flavour will be excluded so count--
freq[arr[l]]--;
l++;
}
}
cout<<max_lenght<<endl;
}
return 0;
}``````

compilers and parsers: In the code below (mine), I’m counting the valid sequence until the stack becomes empty or until a wrong sequence is encountered. But it’s WA. Could someone help me figure out where I’m wrong: -_-

``````#include <iostream>
#include <bits/stdc++.h>
using namespace std;

int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);

int t;
cin>>t;
while(t--)
{
stack<int> s;
string str;
cin>>str;
int res = 0;

for(int i = 0; i<str.length(); ++i)
{
if(str[i]=='<')
s.push(str[i]);
else if (s.empty()==false)
{
if(s.top()=='<')
{
s.pop();
res+=2;
}

}
else if(s.empty())
break;
}
cout<<res<<endl;
}
return 0;
}``````

I am getting WA for the problem Compilers and Parsers
Can somebody tell me where I am wrong?

Here is the link to my submission
https://www.codechef.com/viewsolution/50430771

This is my code for Penalty Shoot-out, why is it giving wrong answer.

``````class Codechef
{
private static int checkWinner(int N, String scores){
int a = 0;
int b = 0;
int chance = N;
for(int i=0; i<2*N-1; i+=2){
if(scores.charAt(i) > scores.charAt(i+1)){
a++;
chance--;
}else if(scores.charAt(i) < scores.charAt(i+1)){
b++;
chance--;
}else if(scores.charAt(i) == '1' && scores.charAt(i+1) == '1'){
a++;
b++;
chance--;
}else chance--;
if(a - b > chance) return i+2;
else if(b - a > chance) return i+2;
}

return 2*N;
}

public static void main (String[] args) throws java.lang.Exception
{
Scanner sc = new Scanner(System.in);
int T = sc.nextInt();
int[] res = new int[T];
int k = 0;
while(T>0){
int N = sc.nextInt();
String scores = sc.next();
res[k++] = checkWinner(N, scores);
T--;
}

for(int i=0; i<res.length; i++){
System.out.println(res[i]);
}
}
}
``````

I have the same question, because as per question we have to print longest prefix but here there is an invalid prefix. I implemented it this way but its giving me wrong answer, there should be more clarity on that “longest prefix”.

Some of these are a bit late, but oh well 