Infytq advantage round

help
1

String Question

You are given a string A representing a number. The digits of the number only consists of digits 1 to 9.

You are given a function F that contains a mapping for digits from 1 to 9 i.e. F[i] transforms the digit i to the value defined in F[i].

You can apply the following operation at-most 1 time:

  • Choose a continuous segment of digits in A and replace each digit x in this segment with a digit replaced using the function F.

What is the maximum number you can obtain in this manner? Since the number can be large, output it modulo 10^9 + 7

Input Format

The first line contains a string, A, denoting the number.

Each line i of the 9 subsequent lines (where 0 <=i<9) contains an integer describing F[i]

Can anyone tell what would be the correct solution/approach for this problem?

1 Like
2

U can solve it using sliding window technique or two pointer technique and just keep doing modulo and precalculate sum of each prefix and suffix

3

I was trying to solve this question. But, it didn’t pass in Hackwithinfy today.

This question was easy and it even was available on gfg

1 Like
4

I think this method will not work in the above question because the length of the string was very high(10^5). We can 't take modulo at the end, we need to somehow calculate the modulo during the process of calculating the maximum possible number.

5

I also used the logic still passed only 1 subtask, might be some edge cases is there.

6

AC in one go
should I post the solution?

2 Likes
7

Can you explain your approach?

8

yeah sure

3 Likes
9

How to solve the first problem? Count consecutive triplets?

10

same… only 1 testcase passed… i sat there for an hour debugging, i even rewrote the code in python …but no luck… i guess some issue with the test perhaps… its not possible otherwise or maybe i missed something who knows

1 Like
11

i had a different first problem…given an array choose 5 integers to maximize product

12

Yes, plzz share the approach of your solution

13

@king_of_string @yashdew @zero_bug
is the solution Maximize the given number by replacing a segment of digits with the alternate digits given - GeeksforGeeks correct or not? I think it is correct

14

Yes Please. I was also not able to do this. Only 1 TC passed

15

I had this. Greedy didn’t work. I got some thought of DP but could not implement it.

16

Please explain the logic.

17

Same with me

18

Could you tell the approach?

19

Yeah same
after that even i tried the brute approach by getting all the subarrays then changing the number in that position and checking for max but no luck

20

Same for me. After not passing all cases I also coded in python but get nothing . I believe there is
probably some problem with the testcases . I also mailed them about this. Now waiting for their reply. :slightly_smiling_face: