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() {
// your code goes here
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: CodeChef: Practical coding for everyone
. 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,
# add it to output
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)
`
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.
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?
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[0]]++;
int max_lenght = 1;
int count = 1; // stores the numbers of flavour in range [l,r]
// let arr[0] 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;
}
// your code goes here
return 0;
}
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ā.
For the example 1,
Where is it implied in the STUPMACH problem that we have to put token in the boxes one after another? Cant we put token in box 1, skip box 2 and put token in box 3 as it states distribution of tokens in boxes donāt matter?