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?
