I am fairly new to CP and, frankly, don’t know much. I have solved quite some problems and am able to solve 2-4 per contest now. I have solved considerable amount of problems in the Practice(school) and Practice(easy) sections…But one thing I don’t get how to tackle is Challenge Problems
Like this. I am unable to solve a single one of these type of coder-judge interaction problems : (
Could you help me out by explaining how these work and how exactly are we supposed to tackle such problems? How do we “interact” with the judge. Also, answer regarding to the GUESSG problem, where judge can lie and stuff
Interaction with the judge simply means you need to take input at that time. The type and no of input is always mentioned in the question. So you take that input and proceed based on that and print your next output and the cycle continues until you reach an endpoint.
1 Like
Most of the time even i couldn’t understand what to do with these problems…Even if I understand the problem the main problem is debugging the error in an interactive problem can anyone help me with this problem how to handle?? I couldn’t score any challenge problem till now 
GUESSG wasn’t a challenge problem. It was interactive. Suppose that I’m the grader and I have to test your code. I’ll give some input and your program should output something. Now, based on what output I’ve got, I give some other (not necessarily different) input. This thing keeps repeating until some condition is satisfied. For example, let’s play a game where I say “Greater” for every number you guess that is greater than my number and “Lesser” if it’s less. I say “Game” when your guess matches the number. My number is x, \ 1 \leq x \leq n, \ x \in \mathbb{N}. So first I’ll say n.
Me: 10
WK: 5
Me: Greater
WK: 3
Me: Greater
WK: 2
Me: Greater
WK: 1
Me: Game
You could do a linear search which will take O(n) guesses. But you used binary search and did it in O(\log{n}) guesses. If n = 10^{18}, a linear approach will take 1 billion billion guesses but a logarithmic approach will only take 60. The idea is to use binary search and reduce the search area by a factor of 2 in every guess. You can easily do it for 15 points using binary search. You have to use one binary search for even guesses and one for odd. Eventually, you will be able to guess the number (think how).
This problem is inspired by IMO’12 P3 (IMO - International Mathematical Olympiad; P3 and P6 are usually the most difficult) XD.
1 Like
What do you mean by this?
Not trying to discourage, but it’s from an IMO problem and people with a strong math background are in div 1. Simple binary search can be used to solve subtask 1. I’ll delete that part.
According to me if it is a Long Challenge, you should read every problem (whether in Div-1 or 2) and at-least try to solve it. That is how you grow.
2 Likes