COCI '18 Contest 3 #1 Magnus

View as PDF

Submit solution

Points: 5
Time limit: 1.0s
Memory limit: 64M

Problem type

Magnus lost a game of chess to Kile so he found comfort in competitive programming. Very soon, he heard of the iconic COCI competition and decided to try his luck there.

He wrote a mail to Kile: "Dear Kile, please, prepare me for COCI. Magnus".

Kile replied: "You want to participate in COCI? All right, here's your warm-up task. A series of four consecutive letters of some word that make up the subword HONI (Croatian acronym for COCI) is called the HONI-block. I will send you the word of length N and you will throw out as many letters as you want (it might be none as well) so that in the end there are as many HONI-blocks as possible in the word. Kile".

Magnus was very worried and asked you, COCI competitive scene, for help. Help him determine the maximum number of HONI-blocks he can get in the final word.

Input

The first line contains a word of length N (1 \le N \le 100\,000), consisting of uppercase letters of the English alphabet.

Output

In the first and only line, print out the required number of HONI-blocks.

Sample Input 1

MAGNUS

Sample Output 1

0

Sample Input 2

HHHHOOOONNNNIIII

Sample Output 2

1

Explanation for Sample Output 2

By throwing out three letters H, O, N and I Magnus can get the word HONI, which contains one HONI-block.

Sample Input 3

PROHODNIHODNIK

Sample Output 3

2

Comments


  • 0
    AreYouNoU  commented on March 10, 2024, 11:09 p.m.

    This one brought me to my knees truthfully. First I had to figure out what a HONI-block is then I had to play with my program for a couple hours before I started over and got it.


  • 1
    Lemon_Licker123  commented on Jan. 12, 2024, 10:15 p.m. edited

    Here after the first half of chapter 3 on the Zingaro book. After a few hours and some YouTube breaks I finally got it. Don't give up and don't overcomplicate it!


  • 2
    McMinn  commented on Dec. 27, 2023, 5:07 p.m.

    Don't try solving with recursion. It will blow up on large input.


  • 1
    Mick  commented on Dec. 19, 2023, 4:38 a.m.

    Wow that was difficult to wrap my head around but it was a simple solution in the end


  • 1
    cozuu  commented on Feb. 27, 2023, 3:12 p.m.

    lol the implementation was harder than the solution itself


  • 3
    Marforio  commented on Jan. 1, 2023, 9:53 a.m. edit 2

    I don't understand the instructions tbh. Could anyone restate this more clearly for me?


    • -1
      Mick  commented on Dec. 18, 2023, 8:58 a.m.

      how do we delete a comment?


    • 4
      jeffrey0857  commented on Jan. 7, 2023, 5:22 p.m.

      Ignoring any alphabet of the input, just fxcking count 'H,O,N,I' in order.

      Please keep in mind that you must count that shit in order.

      So if the input is 'INOHXHIONI':

      step1. find H: So you can get rid of 'INO' and you complete this process.

      step2. find O: Ignoring any nonsense before O and you get 'ONI'.

      step3. find N. step4. find I.

      In the end, the count is one.


      So if the input is 'HHHHOOOONNNNIII':

      step1. find H.

      step2. find O: Ignoring any nonsense before O and you get 'NNNNIII'.

      step3. find N. Ignoring any nonsense before N and you get 'III'.

      step4. find I.

      In the end, the count is one.

      this one is tricky af, but don't give up! I try it like 10 times maybe, and eventually, I got it 10/10. Any questions you could ask if you have.


  • 3
    mehulkschool  commented on Dec. 20, 2022, 7:44 p.m.

    This one is tough. I'm getting all the test cases right here and in the comments (HONIIONIHHONI) but for some reason I only get 4/10 in the actual test cases and fail batches 7-11 consistently.


    • 1
      theshrike  commented on Jan. 24, 2023, 9:03 p.m.

      So, the test cases do a bad job of truly checking your work. If you try pulling each character into a separate var, even if you correct for repeated letters, you will fail 6/10.

      Hint:

      PROHODNIHODNIK will yield 2 for your output, but

      PROHODNIHOINIK will yield 1.

      (BOTH SHOULD be 2)

      Not sure if that helps, but that's what I was struggling with.


  • 1
    SirStarshine  commented on Dec. 20, 2022, 2:00 a.m.

    I'm having trouble solving this one. I understand the objective, iterating the characters only once for the HONI blocks. But I can only think of one solution, which I posted here. [https://dmoj.ca/src/5136161] However, my count isn't incrementing and I don't know why, as there are no errors shown in my test environment.


  • 11
    scarlihin85  commented on Dec. 5, 2022, 8:18 a.m.

    Whos here because of the Python book on solving real life problems? after giving up many times, i finally realized it. Don't give up!


    • 2
      valegrete  commented on Dec. 25, 2022, 10:54 p.m.

      I'm using the Zingaro book as well! This problem was fun. Good luck!


    • 2
      SirStarshine  commented on Dec. 20, 2022, 2:01 a.m.

      Any chance you could drop a hint? I'm using that book too and my solution appears to be bunk.


      • 2
        valegrete  commented on Dec. 25, 2022, 10:57 p.m.

        I'm not the person you asked but I'm using the same book. The problem is written weird but you need to scan left to right to find the letters H, O, N, and I in order.

        I also think this problem would've been easier after chapter 4 since it could be written more intuitively and run faster. I barely squeaked in under the 1.0s time limit.


  • 3
    Yashdeep007  commented on Nov. 18, 2022, 6:12 p.m. edited

    Can anyone explain what I'm doing wrong in my submission? Edit: It seems that if you don't specifically use print function to output your solution, you won't get marks even if the answer is correct


    • 1
      Snub3108  commented on Nov. 20, 2022, 2:44 a.m.

      Funny how every comment asking a q gets downvoted, if you dont print there is no output, you can run the programs yourself with the sample test cases before you submit


  • 1
    Nickthew  commented on Aug. 4, 2022, 4:19 a.m.

    I've hit a wall. I had one solution get 5/10, so I rewrote the code thinking it would work and I actually get 4/10 now. It passes all the test conditions given, plus a few I made up myself. Any advice would be appreciated.


  • 0
    jordanof23  commented on Aug. 2, 2022, 3:55 p.m.

    For the life of me I can't figure out what I'm doing wrong. I'm getting the correct output for all the sample inputs given, and for all the inputs listed in the comments here. Whenever I submit the code I get partial points.


    • 2
      omaewamoushindeiru  commented on Aug. 2, 2022, 8:41 p.m. edited

      In your latest submission, take a closer look at line 14.


  • 0
    nubblet  commented on July 28, 2022, 11:34 a.m.

    So after 5 attempts and many hours later, I finally did it. In may last submission that failed I forgot to output the result when no HONI blocks are found ( Maybe it helps someone, I completely forgot). Hard but still fun at the end for a beginner.


  • 0
    jim95437  commented on July 13, 2022, 7:18 p.m.

    All tests give me the correct number of HONI blocks, but the judge only gives me 4/10. I don't get it.


  • 2
    CS7  commented on May 22, 2022, 5:38 p.m.

    Is there a way to see the input of the test cases that are failing? Without that, It's hard to adjust my code.


  • 1
    maltesp  commented on May 17, 2022, 6:01 p.m. edit 2

    Can someone check what is going wrong with my code? It is failing some, but far from all simulations. Is it because of the way i count my blocks? Are my letter counters not resetting correctly?

    EDIT: Nevermind, i found the problem! It WAS my counting!


  • 3
    Elladan1337  commented on May 15, 2022, 4:31 a.m.

    This is a good test to try: HONIIONIHHONI should return 2, not 3.


  • 3
    Dukkering  commented on April 12, 2022, 2:21 a.m.

    A reminder to all people having issues;

    The rules specify the input will be Capital letters. Capitalization matters.

    I've been banging my head against a wall for a week because I was specifically looking for lowercase letters.


  • 1
    CA_marine  commented on March 23, 2022, 10:36 a.m.

    God as a beginner programmer this has been tough but extremely satisfying.


  • 1
    JustChaz  commented on March 14, 2022, 1:55 a.m. edited

    Okay, im getting flustered, Im unsure what im doing wrong, but its also cause i know im not 100% grasping the idea....I think...

    Here is my sub: {https://dmoj.ca/submission/4415779} Ive submitted 3, but this was my first Submit & the only one that got 2/10 vs 0/10 Haha...

    Gonna take a break..

    *EDIT: I looked up the answer. After looking it over & continuing in the book im reading to study Python, I understand better how I was coding incorrectly, and understand nested if statements better too.


    • 4
      Spitfire720  commented on March 14, 2022, 2:10 p.m.

      It seems many people fumble on the bad wording of the question. Your goal is not to see how many HONI-blocks you can make by rearranging, but simply by iterating.

      Your code would fail Sample Test Case 2, and I have explained how it works below.

      Hope this helps :)


      • 1
        JustChaz  commented on March 15, 2022, 2:29 a.m.

        So, as of right now, If I run Sample Case #2, in my test environment, Using the code I posted, my printed output shows 1. Which is what this question states should be outputed.

        Im still at a loss.

        Ive finally got back to spend some time on this, so I only have had a chance to reply, I will be continuing on this a bit more, then may proceed on my reading and come back to it. I did read the threads below prior to posting. Unfortunately I'm still getting stuck, & in my Case, I am Successfully Passing Sample Case #2 with user_input('HHHHOOOONNNNIIII')

        Your help is very much appreciated!!

        Sidenote: I am also outputting [2] when unser_input = 'PROHODNIHODNIK'


      • 1
        cjord1  commented on March 14, 2022, 5:03 p.m.

        the hero this question needed lol


  • 0
    CoolHand  commented on March 13, 2022, 3:15 p.m. edited

    Took me a second to understand the problem but then it clicked. Essentially you can iterate through the string checking for an 'H'. Once you get an 'H' start checking for 'O', etc... once/if you get an 'I' you have one HONI. Repeat and increment your HONI count accordingly.


    • 2
      thisGuyCodes  commented on March 29, 2022, 10:48 p.m. edit 2

      By your logic, wouldn't test case #2 - HHHHOOOONNNNIIII - be 4? There are 4 Hs, 4 Os, 4 Ns, and 4 Is.

      EDIT: Nevermind, solution seems to require a subsequent search. I am going to see if I understand the problem now.

      EDIT2: Yup, I got it. You scan the input from left to right only once, building up the word 'HONI' from the letters H, O, N, and I in sequence. At the end, you see how many words you have built.


  • -4
    Ousama  commented on Feb. 27, 2022, 10:22 p.m.

    isn't right that sample input 2: HHHHOOOONNNNIIII suppose to output: 4


    • 3
      Spitfire720  commented on Feb. 28, 2022, 11:58 a.m.

      The comment thread

      literally below you

      explains why


      • 7
        hathimerasathi  commented on March 12, 2022, 10:03 p.m.

        This person is literally helping our every soul on here . God bless you good human .


  • 1
    carlosg22  commented on Feb. 24, 2022, 6:01 p.m.

    Can anyone help me understand the problem? I don't understand why SAMPLE input 2 is only 1. Isn't the question asking how many HONI blocks can be made out of the input?


    • 1
      Spitfire720  commented on Feb. 24, 2022, 7:14 p.m.

      No, it's asking how many HONI-blocks you can make by iterating through the string.


      • 1
        carlosg22  commented on Feb. 25, 2022, 2:18 a.m.

        How can I 'throw out' letters when I iterate using a for loop?


        • 4
          Spitfire720  commented on Feb. 25, 2022, 2:26 a.m.

          You can sort of visualize it like this:

          When the next letter of the "HONI" string appears, you add it to the HONI-block. A complete HONI-block gets added to a count and the HONI-block is reset.

          For Sample Input 2, by following this visualization, you can see that although the letters can make up 4 HONI-blocks, iterating in the above manner will only give you 1.

          Hope this helps :)


          • 1
            carlosg22  commented on Feb. 25, 2022, 3:15 a.m.

            Thanks! appreciate the patience! This helped.


  • 1
    Lemon_Licker123  commented on Jan. 9, 2022, 10:07 p.m.

    I'm still trying to understand what a HONI-block is


    • 6
      Spitfire720  commented on Jan. 9, 2022, 10:18 p.m. edited

      I will send you the word of length N and you will throw out as many letters as you want (it might be none as well) so that in the end there are as many HONI-blocks as possible in the word.

      A HONI-block would be, after throwing out some or no letters, you get the string "HONI". For example:

      HONIHONIHONI has 3 HONI-blocks

      HOHONINI has 1 HONI-block, because you cannot rearrange letters

      HIONHION would also have 1 HONI-block, which you can find by throwing out letters.

      Good luck :)


      • 1
        nick1986  commented on Nov. 29, 2022, 5:25 p.m.

        Thanks a lot. It seems the description is there to be found but cryptic as hell. Thanks for clarifying it.


  • 1
    mohamad92  commented on Jan. 7, 2022, 6:55 p.m.

    Can any kind soul, help a brother out. I've tried most of the test cases I can think of and more, yet I always seem to fail the last couple of batches. Any tips would be hugely appreciated. Thanks


    • 4
      Spitfire720  commented on Jan. 7, 2022, 8:31 p.m.

      Try this test case:

      HNOIIONI

      The correct answer should be 1


      • 2
        mohamad92  commented on Jan. 10, 2022, 6:00 p.m.

        Holyy, I completly misunderstood the question, I thought we were trying to find naturally generated HONI blocks, got it now. What a legend


  • 0
    darthvader2021  commented on Jan. 1, 2022, 4:41 p.m.

    Is the sample output for 2nd example supposed to be 4 and not 1?


    • 1
      Spitfire720  commented on Jan. 1, 2022, 5:06 p.m.

      No, if you go through the string from left to right, you'll only get one HONI-block.