Contest 2 - Hints to Problems [OFFICIAL]

CodeChef-DSA-learners
, ,
50 
`#include <bits/stdc++.h>

using namespace std;
#define mod 1000000007uLL
#define ll unsigned long long
int main()
{
//for fast input/output
ios_base::sync_with_stdio(false);
cin.tie(NULL);
ll int n,k;
unsigned long long tem=1;
cin>>n>>k;
vector v(n),l(n,-1);
for(int i=0;i<n;i++)
cin>>v[i];
stack s;
s.push(v[n-1]);
for(long long int i=n-2;i>=0;i–)
{
while(s.empty()==false && v[s.top()]>=v[i])s.pop();
l[i]=s.empty()?-1:s.top();
s.push(i);
}
for(long long int i=0;i<n;i++)
{
if(l[i]!=-1)
{

        tem = (tem%mod * (l[i]%mod - i%mod + 1)%mod)%mod; 
    }
}

cout<<tem;
return 0;

}`

Can somebody tell where is my mistake for the question CHFQUEUE?

52

Help with Not All Flavours - NOTALLFL

Hello all, I am getting partially marks in this …plz help me out.
Approach- for this problem ,i have created a set and each time i am adding elements to my set and incrementing the count and as soon as the size of set becomes equal to number of flavours , i remove all elements of set except the last one ,and put count=1…and this loop continues…and i have store the maximum value of count in variable m then printing it at last.
plz. help me

here is my code:

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

int main() {

int t;
cin>>t;
while(t--)
{
    int l,f;
    cin>>l>>f;
    int a[l];
    set<int >s;
    int count=0;
    int m=0;
    for (int i=0;i<l;i++)
    {
        cin>>a[i];
        
        s.insert(a[i]);
        
        if (s.size()<f)
           {count++;
             m=max(m,count);
           }
        else if (s.size()==f)
        {
            s.clear();
            s.insert(a[i]);
            count=1;
        }
        
    }
    
    m=max(m,count);
    
    
    cout<<m<<endl;
}
    
return 0;

}

53

In question infix to postfix, ^ operator in right to left assosciative.
for example A^B^C, the postfix expression must be ABC^^ as B^C will be calculated first and then A^(B^C). But my code is being accepted even when my output for this case is AB^C^.

54

Hints for NOTALLFL are somewhat convoluted. I am sharing my hints here for someone who is stuck. Complexity for this problem is O(n). Space requirements is O(k+n).

Hint

A subsequence S is valid if there exists at least one flavour F that is not present in it.

Hint

If a flavour F is not present, optimally, the subsequence would share the start with the main sequence or it would have started just after an occurrence of F. And similarly, it would end just before an F or at the end of the whole sequence.
In other words, Subsequence S is of the form [F||start]+S+[F||end].

Hint

Therefore, whenever a flavour f is found - check when it occurred last or never occurred. If the current index is j, and F occurred last at i; we can safely say that sequence (i+1,j-1) is a valid subsequence. The length of this sequence is j-i-1. Compare it with current maximum length.

Also, don’t ignore elements that never occurred in the sequence.

3 Likes
55

What is wrong in this code for Chefs in Queue, I’m finding nextSmallestValue for current i on its right

#include<bits/stdc++.h>
using namespace std;
#define ll long long int
void findNextSmaller(vector& fearfullness, ll n, vector arr)
{
stacks;
for(int i=0;i<n;i++){

    while(!s.empty() && arr[s.top()] > arr[i]){
        fearfullness[s.top()] = i;
        s.pop();
    }
    s.push(i);
}

}

int main(){
ll n, k;
cin>>n>>k;

vector<ll> arr(n), f(n, -1);
for(ll i=0;i<n;i++) cin>>arr[i];
findNextSmaller(f, n, arr);

ll ans = 1, mod = 1000000007;

for(int i=0;i<n;i++)cout<<f[i]<<" ";
for(ll i=0;i<n;i++){
    if(f[i]==-1) continue;
    
    ans = ((ans % mod) * ((f[i] - i + 1) % mod));
}
cout<<ans;

}

56

In first case answer will be 4
In 2nd case answer will be 0
The question says to look for prefix. That means you need to see from start how many are correct pairs. And if the start is never closed then it is 0

57

For compilers and parsers problem, there should one added test case where it should focus on prefix. i.e I was looking for a longest valid string.
@techie_pals
Example : > <> > <><> , if you look into it its ans is zero. but because I missed prefix in ques its ans can be 4. (string[4:]) as it is longest compare to string[1:3].
I hope it is understandable. :grinning:

58

why my infix to postfix showing WA?
any suggestions please.?

import java.util.*;
import java.io.*;
class InfixToPostfixPr {

	static int priority(int ch) {
		switch(ch) {
			case '+':
			case '-': return 1;
			case '*':
			case '/': return 2;
			case '^': return 3;
		}
		return -1;
	}
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int t = Integer.parseInt(br.readLine());
		while(t--!=0) {
			int n = Integer.parseInt(br.readLine());
			char[] str = br.readLine().trim().toCharArray();
			Stack<Character> stack = new Stack<>();
			String ans="";
			for(int i=0;i<n;i++) {
				char ch = str[i];
				if(Character.isLetterOrDigit(ch)) {
					ans+=ch;
				}else if(ch=='(') {
					stack.push(ch);
				}else if(ch==')') {
					while(!stack.isEmpty() && stack.peek()!='(') {
						ans+=stack.pop();
					}
					stack.pop();
				}else {
					if(!stack.isEmpty() && priority(ch)<=priority(stack.peek())) {
						ans+=stack.pop();
					}
					stack.push(ch);
				}
			}
			while(!stack.isEmpty()) {
				ans+=stack.pop();
			}
			System.out.println(ans);
		}

	}

}
59

Please help. I have confusion in “Compilers and Parsers” problem, I thought that we need to find the longest valid sequence in the expression as the test case:

<>>> gives 2 even though full expr is invalid.

So,

“><><>” should give 4
“> <><” should give 2
“> <<<><>>” should give 6

my submission: CodeChef: Practical coding for everyone

Is this right?

60

We need to find longest valid sequence from start, here

61

In Problem 3 COMPILER I think there is confusion in most of our minds. The question is to find the longest prefix that is valid NOT the longest valid substring (Be careful :smile: ).
Some more sample test cases for clarification:

  1. <><> ans : 0 (since ‘<><>’ are not prefix although they are valid substring)

  2. <>><<>> ans: 2
63

Infix_to_postfix
Hey you, no, not the one behind you, I’m talking to you. Do you have free time? If you stumbled upon this post, and if you have free time, continue reading. (Sorry for the rubbish)

I wrote the code for the problem infix_to_postfix. It worked. I wrote in both py and cpp.
The thing is, when i submitted the C++14 solution, the memory I used was 14.9M. But when I submitted the C++17 solution (which was the same code) the memory used was 5.8M.

I am curious, is this because of the standard of cpp that I used? Or is it something else? And if it’s because of the standard used (cpp 17), exactly what is it that makes my code when using cpp17 standard take less memory? Care to tell?

This is from a geeks_for_geeks discussion. Here’s the thing, the code I used (and the “kind” of code I have seen many others use) for the infix_to_postfix problem is pretty much the same. (The difference? I can write the code on my own, and I also know the logic behind it)

The thing is, this “kind” of code (link to my solution is above) doesn’t work for certain test cases (which apparently are not there in both the geek and codechef version of the problem).

For example:

Case: a^b^c*d
Real answer: abc^^d*
Code given answer: ab^c^d*

Case: x+y^z*p/q^r^s
Real answer: xyz^pqrs^^/+
Code given answer: xyz^p*qr^s^/+

I tested these with the very code I submitted in the codechef version of the problem. I get the code given answer every time I do that. And according to all the knowledge of infix to postfix conversion that I have, my code given answer is wrong. What can I do to solve this? (I obviously couldn’t understand much of the R-L priority thing, so I was hoping to get guidance here)

1 Like
64

penalty shoot

please help me
i am getting wrong answer

for j in range(int(input())):
a = int(input())
b = input()
i =0
count1 =0
count2 = 0
while(i<len(b)):

    if i%2==0:
          count1+=int(b[i])
    if i%2!=0:
          count2+=int(b[i])
    
    if i%2!=0:
            a-=1 
    if abs(count1-count2)>a:
          
            break
    i+=1
if i==len(b):    
    print(i) 
else:
    print(i+1)
65

i am getting wrong answer for penalty shoot

link to my sol
https://www.codechef.com/viewplaintext/36147685

66

contest-2 (penalty shoot)

what is the use of queue ds instead of using simple for or while loop?(penalty shoot)

67

precedence!

68

i agree with @supandeep
+1

69

ya! ~ exactly

70

Bro
we just need to print length of longest valid PREFIX(which exists in starting of expression)
that makes the questions easy

though your solution is nice,
just tweek it to chk only for PREFIX sequences i.e. single seq which is in starting
if PREFIX(that single seq) is invalid then longest length 0

71

the real ans in case a^b^cd will be
ab^cd^ i guess ;
i compiled and ran it in codeblocks ide on ma pc;
here is the output screen
But what you say is interest ing
Did you got AC on codechef while submission

Annotation 2020-08-02 124146
Annotation 2020-08-02 124146841×407 26.2 KB

1 Like