shareChat hackerearth test help

SHARECHAT 3RD QUESTION: A-Z COUNT

Need help on this question. I used map and binary search still all test cases not passed.
Test is over now.So if anybody can share the working code it would be helpful for me.

1 Like

How many test cases did your solution pass?

Any idea , will 124 out of 170 get shortlisted ? I dont think so :frowning:

Square root decomposition will work for the given constraints

Please Correct me if i am wrong

@bng442 You have to make a 2d array of 26*n length. Then iterate whole string and fill this array like ar[s[i]-β€˜a’][i] =1, after that take cumulative sum of this array for each i =0 to 25, then for query type L, x will be lower_bound of ar[ch] and here k will be k+1 and ans is x-1,
for query type S, ans will be lower_bound of ar[ch].
Hope it help!

2 Likes

Have you solved the field of dreams problem???

Partially solved. Got 86 marks

1 Like

Can you tell me how you solved?

Why cant we make an array of size 26 and in each index we store a list of the indexes at which that character is present? then answer the queries accordingly

I solved it by making prefix arrays for each character and by maping indexes of first apperance and last appearances for each freq f of character ch. And directly answering queries using those pre calculated maps.

1 Like

@bng442 @arjun8115

I guess there was some problem with the A-Z question. In the attached screenshot my output is correct according to the custom input but the platform expects something else. What do you say?

Yeah, it is also a correct approach.

I used a dfs for finding no. of connected component. If this return >1 then answer would be 0 and in other case there is two possibility of answer, either 1 or 2. Then i just iterate over matrix and check if there is atleast one β€˜g’ which is just connected by a single β€˜g’ ,in this case ans is 1 otherwise it would be 2.

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.