COCI '18 Contest 3 #1 Magnus
View as PDFMagnus 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 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
, 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
MAGNUSSample Output 1
0Sample Input 2
HHHHOOOONNNNIIIISample Output 2
1Explanation 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
PROHODNIHODNIKSample Output 3
2
Comments
I can't submit my code, I think it works pretty welll but the judge seems to not like it would somebody help me figure out why?
It took a while to understand the directions. I appreciate all the different ways contributors have explained it. Here's how I finally understood it:
Go through the word (left to right) only once.
Start at the first letter of the word and move right. After you find one letter, you are only looking for the next letter in HONI. No other letters matter.
If you find a letter "H", continue your search to the right for the first occurrence of the letter "O". Ignore all other letters, including any additional "H" you come upon.
If you do NOT find a letter "O" to the right of the "H", there are no HONI instances. Stop here.
If you do find a letter "O", continue to the right, looking for the first occurrence of the letter "N".
If you do NOT find a letter "N" to the right of the "O", there are no HONI instances. Stop here.
If you find a letter "N", continue to the right, looking for the first occurrence of the letter "I".
If you do NOT find a letter "I" to the right of the "N", there are no HONI instances. Stop here.
If you DO find a letter "I", count it as one HONI instance.
If there are still more letters in the word following the letter "I" you just found, continue moving right from your current position, looking for the letter "H" (then "O", then "N", and finally "I").
If you find all the letters again in order, count it as another HONI instance.
Keep this up until you run out of letters in the word.
Report the number of complete HONI instances you found.
This is a reminder to not post your code in the comments. If you need help with the problem, you can visit the Discord. If you want a place to post your code, you can use a service like GitHub. If you want to be banned from making further comments, you can contact the admins.
A worthy task that confused me, but in the end it turned out to be very simple.
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.
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!
Don't try solving with recursion. It will blow up on large input.
Wow that was difficult to wrap my head around but it was a simple solution in the end
lol the implementation was harder than the solution itself
I don't understand the instructions tbh. Could anyone restate this more clearly for me?
This comment is hidden due to too much negative feedback. Show it anyway.
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.
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.
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.
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.
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!
I'm using the Zingaro book as well! This problem was fun. Good luck!
Any chance you could drop a hint? I'm using that book too and my solution appears to be bunk.
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.
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
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
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.
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.
In your latest submission, take a closer look at line 14.
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.
All tests give me the correct number of HONI blocks, but the judge only gives me 4/10. I don't get it.
Is there a way to see the input of the test cases that are failing? Without that, It's hard to adjust my code.
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!
This is a good test to try: HONIIONIHHONI should return 2, not 3.
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.
God as a beginner programmer this has been tough but extremely satisfying.
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.
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 :)
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'
the hero this question needed lol
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.
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.
isn't right that sample input 2: HHHHOOOONNNNIIII suppose to output: 4
The comment thread
literally below you
explains why
This person is literally helping our every soul on here . God bless you good human .
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?
No, it's asking how many HONI-blocks you can make by iterating through the string.
How can I 'throw out' letters when I iterate using a for loop?
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 :)
Thanks! appreciate the patience! This helped.
I'm still trying to understand what a HONI-block is
A HONI-block would be, after throwing out some or no letters, you get the string "HONI". For example:
HONIHONIHONIhas 3 HONI-blocksHOHONINIhas 1 HONI-block, because you cannot rearrange lettersHIONHIONwould also have 1 HONI-block, which you can find by throwing out letters.Good luck :)
Thanks a lot. It seems the description is there to be found but cryptic as hell. Thanks for clarifying it.
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
Try this test case:
The correct answer should be
1Holyy, I completly misunderstood the question, I thought we were trying to find naturally generated HONI blocks, got it now. What a legend
Is the sample output for 2nd example supposed to be 4 and not 1?
No, if you go through the string from left to right, you'll only get one HONI-block.