BOJACK - Editorial

editorial
, , , ,
22

This question is as adhoc as it gets. Some people are gonna have a hard time digesting this(me included). I was trying some stuff using triangular numbers and having strings like “abcd…z”. I had a feeling the actual solution was much simpler. Kudos to the author.

5 Likes
23

Appeal to change the contest name to AdHoc CC Contest ;-;

10 Likes
24

During Contest, All I believe was this is a dp problem and I was finding some O(nlogn) solution. After this editorial, I am like :astonished:

8 Likes
25

Umm, I just tried this, but it gave me a WA, I think there’s something wrong with the checker.
Here is the submission

EDIT: Darn it, we had to output the string length as well, I Iiterally worked on this problem for 2 hours, and didn’t notice that we had to output the length as well, sorry folks my bad. :sweat_smile:

4 Likes
26

should i laugh or cry after seeing this solution cant judge please help!!

3 Likes
27

And 7*n is provided Just to distract us! (My all thinking starts from number 7, I make different combination of a string having the length multiple of 7) :no_mouth: :no_mouth: :no_mouth:

7 Likes
28

From aaaa....bbbbb You can choose 0-D occurrence of each character.
So number of distinct Substrings is (D+1)(D+1) - 1.
-1 is because of the empty string.

Number of Palindromes in aaa...a is n\choose2 +n.

2 Likes
29

Are they rejudging this problem I see a few submissions in being judged right now ?

1 Like
30

This along with GOLMINE :stuck_out_tongue:
You must remember that problem right? XD

10 Likes
31

Yup! still haunts me

1 Like
32

@rajarshi_basu will practice make me able to solve such problems?I had guessed the pattern to be like this but got stuck on how to count number of substrings.
Any suggestions about how to improve Sir?

1 Like
33

Aaaree bro, I had guessed a pattern of such kind but me so stupid could not count number of distinct substrings

2 Likes
34

U are not alone buddy

2 Likes
35

Last test case has changed during contest without any notification/announcement. Previously the input was 63 and then changed to 60.

1 Like
36

Bad day after todays CC and CF contests :grimacing:

5 Likes
37

WTF ,i spent so much time in this and still can’t figure it out during contest i thought it’s pretty tough question but after seeing the solution i think i am way poor in thinking and coding

38

Experiments with inputs and observation on them.

40

Instead of directly calculating it…you can also count it using map bro…

int ass(string s) {
    int n = s.size();
    map<string, int> cnt;
    int pal = 0;
    for (int i = 0; i < n; i++) {
        for (int j = i; j < n; j++) {
            int l = j - i + 1;
            string t = s.substr(i, l);
            bool f = true;
            for (int k = 0; k < l; k++) {
                if (t[k] != t[l - k - 1]) f = false;
            }
            cnt[t]++;
            if (f) pal++;
        }
    }
    return cnt.size() - pal;
}
41

nnoo is not palindromic

1 Like
42

okey got the error silly mistake and thanks