I was trying to solve this problem yesterday : Beautiful Numbers
I've written this blog after reading : Errichto's Asking for Help and the other blog post on asking for help here by dalex or Enchom if I remember right so I hope it's fine :)
Thought Process
And my first thought was this :
If the array is $$$4 , 5 , 3 , 1 , 2 , 6$$$ , I'll have a position array (1-indexed) like
$$$pos[1] = 4$$$
$$$pos[2] = 5$$$
$$$pos[3] = 3$$$
$$$pos[4] = 1$$$
$$$pos[5] = 2$$$
$$$pos[6] = 6$$$
Now for $$$ i = 1 $$$ and $$$i = n $$$ , it will always be true as for $$$i = n $$$ it is a permutation and all elements have to be present and for $$$ i = 1 $$$ , the number $$$ 1 $$$ will be present somewhere in array
Now for $$$ i = 2 $$$ , we have to look at positions of $$$ 1 $$$ and $$$ 2 $$$ which are $$$ 4 , 5 $$$ , These are contiguous so yes .
Now for $$$ i = 3 $$$ , we have to look at positions of $$$ 1 $$$ and $$$ 2 $$$ and $$$ 3 $$$ which are $$$ 4 , 5 , 3 $$$ , These are contiguous like $$$ 3 , 4 ,5 $$$ so yes .
Now for $$$ i = 4 $$$ , we have to look at positions of $$$ 1 $$$ and $$$ 2 $$$ and $$$ 3 $$$ which are $$$ 4 , 5 , 3 , 1 $$$ , These are NOT contiguous as $$$1 , 3 , 4 ,5$$$ is NOT contiguous so answer is NO
And similarly to find yes/no status for other indices.
My thought was initially to store max and min for each $$$ i $$$ from $$$1$$$ to $$$n$$$ and check if max-min+1 = i but I was not sold on that idea so I tried a sorta different "weird" approach .
I try to describe it here : As I had described my thought process above , the part I was finding kinda hard was efficiently coming up with a way of checking whether the groups of indices are contiguous or not like $$$1 ,2 , 3$$$ and $$$ 2 , 3 , 4 ,5$$$ are contiguous but $$$ 1 , 3 , 4 , 5$$$ is not
So I was thinking and time was ticking fast :(
Beginning of somewhat outlandish part
Say the input array was : $$$ 4 , 5, 1 , 3 , 2 , 6$$$
Position for elements $$$ 1 , 2 , 3 , 4 , 5 , 6 $$$ were $$$ 3 , 5 , 4 , 1 , 2 , 6 $$$
So I denoted first element of position array by say $$$p$$$ , here $$$p = 3$$$ ,
Next element is $$$5$$$ which is $$$p + 2$$$
Then $$$p+1$$$ , $$$p-2$$$ , $$$p-1$$$ and $$$p+3$$$ which altogether is
$$$p$$$ , $$$p+2$$$ , $$$p+1$$$ , $$$p-2$$$ , $$$p-1$$$ , $$$p+3$$$
So to check whether at any index $$$i$$$ , if the answer is Yes/No or 1/0 , I need to go the indices up to that point and check if those are contiguous or not
For example , $$$i=3$$$ I have to check if any arrangement of [ $$$p$$$ ,$$$p+2$$$ , $$$p+1$$$ ] is contiguous , here it is simple as $$$p$$$ , $$$p+1$$$ , $$$p+2$$$ is contiguous so yes , the way I checked in program is if sum of these : $$$ p + p + 1 + p + 2 $$$ i.e. $$$3p+3$$$ ,ignoring $$$p$$$ , the other number should be equal to the sum of natural numbers from $$$1,2......i-1$$$ , i.e $$$(i*(i-1))/2$$$
There's another problem when $$$i=4$$$ , see $$$p$$$ , $$$p+2$$$ , $$$p+1$$$ , $$$p-2$$$ , this $$$-2$$$ negative kinda offsets things off , so I maintain the largest negative(here largest means if p-3 , p , p-4 are there , -4 is largest) offset , here the largest negative is -2 and Sum so far is 0+2+1-2 = 1 , I add 2 to every element so I add $$$2*i$$$ = $$$8$$$ to the sum already computed and do the same check if it is equal to $$$i*(i-1)/2$$$
Doubts
1)Is the above linked solution that I have come up with correct ? How to prove a solution's correctness ? Be it whether the solution is greedy or non-greedy?
2)Does there exist a DP solution to this as each answer is sort of associated or related with the previous value
3)Do high rated coders also face some difficulty in these problems ?. These type of problems are the ones I currently enjoy solving because they have no prerequisite algorithm or data structures and are slightly above my level and there's a rush of euphoria when you succeed :)
4) How do you tackle a problem ? Is my thought process absurd/good/bad. Apart from practise what is needed to improve and solve stuff really fast in contest?
Doubt Clearance
Say the position for elements [1,2,3,4,5,6] is [3,5,4,1,2,6]. For i = 3, we have [3, 5, 4]. If we subtract the offset it will look like [0, 2, 1]. According to you, if the sum is 3 then it is beautiful. It will be a problem if we get the sum = 3 for different sequence of number other then [0, 2, 1]. Now imagine, as the elements are distinct, you can't change any of them from the sequence [0, 2, 1] without changing the sum. So, we can say that there is only one sequence corresponding to sum = 3. That means your solution is correct. And you can understand by yourself if the solution is greedy or not by reading this blog post.
I am not sure about the DP solution of this problem. But using DP for this problem will be like firing a cannon to kill a mosquito.
From my perspective, I didn't find it difficult. It took me 10 minutes to get ACCEPTED. Some of them solved in just 3 minutes.
It's all about practice. You solve more problems, you will get to learn new things. As a beginner there is nothing wrong in your thinking process. You need to practice with lot of problem to solve stuffs so fast in contest.
Thank you so much for the clarification :) I will keep practising.
Let me provide some thoughts on the thought process.
Here is how I approached this problem.
Let $$$L$$$ be the left most index we have encountered so far.
$$$R - (L - 1)$$$ cannot be smaller than $$$i$$$ since we have done $$$i$$$ steps.
This means that all the elements in $$$[R, L]$$$ are filled. This means that $$$[L, R]$$$ is a permutation of $$$[1, i]$$$ as these are the only elements which we have inserted so far.
This means that there are empty spots in $$$[L, R]$$$. So, it is not possible for $$$[L, R]$$$ to be a permutation of $$$[1, i]$$$
Now, the final solution looks elegant because we are only keeping track of the left most and right most index we have encountered so far.
I want to talk about the thought process for a minute. Like chess, it is all about pattern recognition. You asked about whether this question was difficult for higher rated coders. Now, it is true that there are ad-hoc problems which are sometimes difficult for higher rated coders if they are very new, but I don't think this problem would have been.
Why was I able to solve this problem ? The idea of starting with an empty array and then inserting the problems in ascending order is a very common idea. It occcurs in many problems involving segment trees, particularly in the classical problem of counting inversions in an array in $$$O(N \log N)$$$ time.
So, the main reason I solved this problem is because I recognised the pattern of starting with an empty array and then inserting the elements. I also recognised the idea that we only need to keep track of left most and right most index.
Also, I strongly discourage having a negative mindset and asking questions which beat yourself up like 'Why do I keep missing it ? Why didn't I solve it ?'
Whenever I solve a challenging problem, I write about the ideas/patterns I recognised in the problem. When I can't solve a problem, I write about the ideas and patterns I recognised and the ideas I missed. This self-awareness will help you relate problems to other problems and will strengthen your mindset. Enrichen your mental library of patterns and motifs :)
Thanks for sharing insights into your thought process :) As I had described in the blog , my initial idea was also sort of similar to keep track of min and max for each insertion and check if $$$max-min+1$$$ , the no of elements are equal to $$$i$$$ but unfortunately I doubted myself and didn't implement that and ended up using a different approach :( I have to practise a lot , haha :')
Have to enrich my mental library of patterns indeed :)