Need help Codeforces Round #624 (Div. 3) Problem C

help
1

My unsuccessful attempt (TLE) : Submission #71797970 - Codeforces
Problem : Problem - C - Codeforces

Realized brute force won’t work. How can I overcome it? Any intution/logic for a faster approach would be helpful. Thank you.

1 Like
2

i commented the brute force and used the actual solution as non commented :slight_smile:
I think this will help

1 Like
3

Can you please explain a bit about your where array and how/why you’ve used it? I’m unable to get it. :slight_smile:

4

First make another array of size same as the length of the string say arr and initialize with 0. Then when taking input for ‘p’ array, increase the value of the array at index (p-1) by one . Finally , you can use suffix sum to answer in O(n).

My solution : Submission #71786236 - Codeforces

1 Like
5

My approach is make a frequency prefix table of each char in string. then for every time I make mistake at position i +1, I have pre computed values of the buttons clicked till i-th mistake. Now I just need to add the required frequency to ans array.

Link : Submission #71793985 - Codeforces

6

I really liked your approach, so simple and clear. Getting the number of updates in linear time using suffix sum.

Here’s my submission. Thanks to you all :slight_smile:

1 Like
7

It is a direct question of Fenwick Tree! Simple!

8

This seems cool, I’ve heard of it before but never used it… will try uisng this approach too.

9

Can you explain your solution a bit?

10

Okay so where array stores the number of times that position has been pressed.
Since the string is needed to traversed once I initialized it with zero.
Then I made a brute force and kept going till that position which is mentioned in the p array.
To optimize this I made a same where array where I just recorded till where in the array has the button been pressed, before that part the array must be pressed that many times too.
So that’s why I traversed in reverse and that relation was derived using the suffix knowledge :sweat_smile:.
This was a bit in depth explanation that has been previously provided but I decided to explain how my thought process worked

11

Yeah your solution is exactly what I did :slight_smile:
Glad you understood. I was very tired yesterday and slept before explaining ;_; sorry

12

XD
Its an overkill.
It is a basic prefix sum.

2 Likes
13

Oh it’s cool man, thanks for your explanation. Appreciate it. You’ve helped me before on some div2 problem btw if you remember xD

1 Like
14

I do remember a bit. XD I give short contests on cf,cc and Atcoder so I am usually upto date with them