anyone get 100 mark in field of dreams?
@sagrawal23 May be it is giving wrong expected output, but i think there input-output test files are correct.
Can you guys tell me how much marks you got? Also what should be the ideal score to qualify for the interview?
When did this contest take place? Can you please share me the link? Nothing is being shown in the past contests section in hackerearth.
3 Likes
i have got 138 . any idea of cut off?
@arjun8115 Yes but if a custom test case gives wrong output it means that the platform is treating my code as wrong atleast in this case. Anyways I have mailed them. Let’s wait for the reply.
prefix array for each character
(lower bound ,upperbound )for each query
Yeah, you are right, but i solved lot of questions where expected output is different from my code output, but i got full marks.
I got 156.
1 Like
I thought so but I got WA. The solution was passing almost every case I threw at it but still couldnot solve the issue…might have missed something 
Great!
1 Like
May be you are missing some corner cases. Like check for when k is equal to frequency of that character…
I put that as well…I wish I could share my solution
you dont even need binary search. You need to prepare a table for all the indexes of the lower case letters and then you can figure out the logic 
. Hope you understand . If you have any queries, feel free to post, will give out the detailed soln
How can we participate in this contest??
1 Like
Yeah bro pls share detailed solution
Question
Given a string Str of size N comprising lowercase English alphabets indexed from 1 to N. Answer the following Q Queries on the string which can be of either types:
- L \ ch \ K : Find the largest index I such that there are exactly K repetitions of the character ch in the range 1 to I of the string Str.
- S \ ch \ K : Find the largest index I such that there are exactly K repetitions of the character ch in the range 1 to I of the string Str.
Constraints
1 \leq T \leq 50
1 \leq N,Q \leq 10000
Solution:
Naive solution wont work as the constraints of N and Q are high enough to get TLE . So we will build a lookup table to answer the queries in O(1) time.
Observation:
- The answer to the query L \ ch \ K is ans - 1, where ans = the index of the (K + 1) \ th occurrence of the character ch in the string Str .
Note: Here is an edge case for the query type L \ ch \ K . Consider the string abaaba. Now for the query type L \ a \ 4 we need to print the length of the whole string as the largest index till the character a has occurance 4 will be the index of the last element of the array.
- The answer to the query S \ ch \ K is the index of the Kth occurrence of the character ch in the string Str.
We create a array of vectors of length 26, say named look. Then we traverse the entire string and store the indexes of the characters in look . Then for each query we can use the stored values to answer the queries in O(1) time.
Overall complexity in answering all the queries is O(Q).
C++ Implementation:
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define ll long long
void solve() {
int n,q;
cin >> n >> q;
vector <int> look[26];
string s;
char ch;
cin >> s;
for(int i=0;i<n;i++) {
ch = s[i];
look[ch - 'a'].pb(i+1);
}
while(q--) {
char choice;
int k;
cin >> choice >> ch >> k;
if(choice == 'L') {
if(k == look[ch - 'a'].size()) {
cout << n << '\n';
}
else {
cout << look[ch - 'a'][k] - 1 << '\n';
}
}
else {
cout << look[ch - 'a'][k-1] << '\n';
}
}
}
int main() {
ios_base::sync_with_stdio(0); cin.tie(0);
int t;
cin >> t;
while(t--)
solve();
}
5 Likes
This is the first time i have ever written a detailed solution of a problem 
. Suggestions on how i can improve are appreciated .
1 Like
Can you elaborate this. How did you conclude your observation regarding the solution would be either 1 or 2?