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
    scarlihin85  commented on Dec. 5, 2022, 3: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!


  • 0
    Yashdeep007  commented on Nov. 18, 2022, 1: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. 19, 2022, 9:44 p.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


  • 0
    bodanc  commented on Nov. 6, 2022, 4:34 p.m. edited

    One of the most poorly phrased, ambiguous problem descriptions I've come across on this platform.


  • -1
    Nickthew  commented on Aug. 4, 2022, 12: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.


  • -1
    jordanof23  commented on Aug. 2, 2022, 11:55 a.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.


    • -1
      omaewamoushindeiru  commented on Aug. 2, 2022, 4:41 p.m. edited

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


  • -1
    nubblet  commented on July 28, 2022, 7: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.


  • -1
    jim95437  commented on July 13, 2022, 3: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.


  • -1
    CS7  commented on May 22, 2022, 1: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.


  • 0
    maltesp  commented on May 17, 2022, 2: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!


  • 1
    Elladan1337  commented on May 15, 2022, 12:31 a.m.

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


  • 1
    Dukkering  commented on April 11, 2022, 10:21 p.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, 6:36 a.m.

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


  • -1
    JustChaz  commented on March 13, 2022, 9:55 p.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.


    • 1
      Spitfire720  commented on March 14, 2022, 10:10 a.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 14, 2022, 10:29 p.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, 1:03 p.m.

        the hero this question needed lol


  • -3
    CoolHand  commented on March 13, 2022, 11:15 a.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.


    • 0
      thisGuyCodes  commented on March 29, 2022, 6: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, 5:22 p.m.

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


    • 1
      Spitfire720  commented on Feb. 28, 2022, 6:58 a.m.

      The comment thread

      literally below you

      explains why


      • 4
        hathimerasathi  commented on March 12, 2022, 5: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, 1: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, 2:14 p.m.

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


      • -1
        carlosg22  commented on Feb. 24, 2022, 9:18 p.m.

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


        • 2
          Spitfire720  commented on Feb. 24, 2022, 9:26 p.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. 24, 2022, 10:15 p.m.

            Thanks! appreciate the patience! This helped.


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

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


    • 2
      Spitfire720  commented on Jan. 9, 2022, 5:18 p.m.

      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, 12:25 p.m.

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


  • 0
    mohamad92  commented on Jan. 7, 2022, 1: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


    • 2
      Spitfire720  commented on Jan. 7, 2022, 3:31 p.m.

      Try this test case:

      HNOIIONI

      The correct answer should be 1


      • 0
        mohamad92  commented on Jan. 10, 2022, 1: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


  • -1
    darthvader2021  commented on Jan. 1, 2022, 11:41 a.m.

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


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

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