I'm just so annoyed by all these cheater blogs by alt accounts (some with offensive usernames) made for the sole purpose of that blog.

And some comments are just mean, it's just people being petty and bullying :(!

Does that mean I'm okay with cheating? Absolutely not! But insulting or shaming someone will not get you anywhere? I believe everyone makes mistakes, and whether they cheated or not, they deserve a chance to redeem themselves by working hard on problem solving:)

What irks me the most are people who say omg I would have been CM if not for that guy cheating. Really? You're rated 800 :( Like People use this as an excuse to justify their lack of problem solving and practice because it is way easier to pull people down and use them as a shield than to actually work hard and get better.

I'm rated around 1100 because I don't upsolve at all and just give contests for fun (maybe, I suck, I should practise a lot) but definitely not because of some random people cheating.

[Posted From My Main Acc]

While solving Problem C of the recent contest, my thoughts were-

If $$$n$$$ is $$$1$$$, then Ashishgup cannot make any move and therefore he loses.

If $$$n$$$ = $$$2$$$, In the first turn Ashishgup will decrement the number providing $$$1$$$ to the opponent and thereby winning.

If $$$n$$$ is Odd, Ashishgup can always divide by the number itself and provide $$$1$$$ to the opponent, thereby winning

Otherwise, I tried to visualise the problem as prime factorization.

The Prime Factorization of any number can be of the form: $$$ 2^3 * 3^3 * 17^1 ...$$$ etc, where two is the only prime factor and rest are all odd as every prime no apart from $$$2$$$ is odd. Therefore, the factorization can be rewritten as $$$ evenPart * OddPart$$$ where the $$$evenPart$$$ consists of some power of $$$2$$$ and $$$oddPart$$$ is the full product of the rest of the prime numbers.

Ran a loop till $$$ \sqrt{n} $$$ and for every factor, I check if $$$n/OddFactor$$$ is even. The idea being that if we provide a number with no odd factors to FastestFinger on the next turn, Ashishgup will win.

The only caveat is that if $$$n/OddFactor$$$ is $$$2$$$ , then AshishGup loses.

Is my train of thought right?

Submission

Problem Statement

In short

You are given five integers $$$ n , a , b , c , d $$$ . You need to check if it is possible to form an array of $$$n$$$ elements such that each element's value is between $$$ a-b $$$ and $$$ a+b $$$ and the sum of the array is between $$$ c-d $$$ and $$$ c+d $$$

Initial Thoughts

My initial idea was to loop $$$ i $$$ from $$$ a-b $$$ to $$$ a+b $$$ and check if $$$ n * i $$$ lies in the range $$$ [ c-d , c+d ] $$$

But the problem with that is this assumes that all the array elements are same.

Counter Test

Let's have $$$ n = 4 , a = 2 , b = 1 , c = 7 , d = 1 $$$

This means that all the elements of the array we're trying to form is $$$ [ 1, 3 ] $$$ .

The sum we're trying to make is between $$$ [ 6 , 8 ] $$$

If we assume only same elements , the sum we can form are $$$ 3 , 6 , 9 $$$ ( All 3 elements are 1 or 2 or 3)

Intuition

Now in the previous case , this array is possible $$$ { 2 , 2 , 3 } $$$

How to generalize what sums are possible?

We know that the minimum sum possible is $$$ (a-b) * n $$$ (All elements are equal and are the smallest element)

The maximum sum possible is $$$ (a+b) * n $$$

Now are all the sums between $$$n * (a-b)$$$ and $$$n * (a+b)$$$ posssible ?

I took this example : $$$ n = 4 , a = 12 , b = 2 $$$

The goal is to prove that all sums from $$$ (a-b) * n $$$ to $$$ (a+b) *n $$$ are possible ie. between $$$ 40 $$$ and $$$ 56 $$$

Sum = $$$ 40 $$$ , Array = $$${ 10 , 10 , 10 , 10 } $$$

Sum = $$$ 41 $$$ , Array = $$${ 10 , 10 , 10 , 11} $$$ ...

Sum = $$$44 $$$ , Array = $$${ 10 , 10 , 10 , 14} $$$ or $$${11 , 11 , 11 , 11}$$$

Sum = $$$45$$$ , Array = $$${11 , 11 , 11 , 12} $$$

Sum = $$$46$$$ , Array = $$${11 , 11 , 11 , 13} $$$

Sum = $$$47$$$ , Array = $$${11 , 11 , 11, 14}$$$

Sum = $$$48$$$ , Array = $$${12 , 12 , 12 , 12}$$$

.....

Sum = $$$56$$$ , Array = $$${14 , 14 , 14 , 14}$$$

Doubts

My approach involved forming an array with $$$n-1$$$ equal elements and one same or different element , we can always from the sum $$$ n * (a-b) $$$ and $$$ n * (a+b) $$$

Do you try to prove such solutions especially if they're Div 2 , A

Is there an easy way to prove solutions

How to develop intuition ?

UPD Here is my attempt after reading Tzak's comment:

Proof

I was trying to code the problem Candies, yesterday and my logic was

In order to find a solution to

x + 2x + 4x ... = n

x(2^k — 1) = n

x = n / (2^k — 1 )

So I go through the factors of n in square root n time and check if they're of the same form as the denominator.

But apparently it times out, can someone shed some light on this?

Link to my submission

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$$$

My solution

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?

I recently participated in the div 3 contest and tried to solve problem D : Distinct character queries with Square Root Decomposition using a 2D array like block[denoting_which_block][charfreq] and it passed all the 50 odd pretests during contest and I was over the moon because I just recently learned this concept. But today morning, it was hacked sadly :( And I want to know why the solution fails? Should I have used seg/fenwick? This is my submission The thing is we keep looking for a small indication to denote our improvement every single time and feels bad to not grow despite practise

Thanks :)

Anyone?

I know that this will garner a lot of scepticism or downvotes but I want to put my point across and trudge on

I was planning on seriously working towards improving my competitive coding skills . So I thought I'd first get through mostafa.saad.fci Junior Training Sheet

But looking at the sheer size of it , it's a bit daunting . And when in doubt , to stay on track and be focused , you always raise a pack .

I'm looking for people with rating < 1400 mainly ,(greater rating people can of course join if they are so inclined) to solve problems with from the sheet Mainly motivated,honest,consistent people with a desire to be better and wouldn't throw lot of excuses

1. We'll try to solve problems on our own and discuss our different approaches
2. Help each other out in case one of us has been struggling on a problem for a long time .
3. Only see the editorial in case we've completely solved the problem to compare our approaches or are totally lost
4. Solve at least 1 problem per day from our codeforces profile

We can maybe form a telegram group and converse about the problems daily and post screenshots about the status of submissions and update the aforementioned excel sheet and post a weekly update blog here on codeforces

I am well aware that this is not going to be some Petr-level post/blog but just an aspiration of someone who wants to grow as a group

Now I know it might be absurd to some of ya that me , a gray coder is proposing all this but dreaming about what is impossible or hard to attain is what makes us beautifully fragile humans .

Interested People can reply in the comments

Thank You and Dream On

UPD : Link to telegram group for interested people : Link

I'm not all that proficient with Competitive Coding though I'd like to be .

I've been practising for some time now and before I struggled to solve 1 , now I solve 2 in contests and recently reached 3 star in Codechef

Started reading 10-20 pages of CLRS / Competitive Programmer's handbook every day

But sometimes the elegant solutions elude me . When I read the editorial I get it but don't know why I hadn't thought of it earlier and feel like I'll not get way better :/

Though my knowledge of data structures and algo are slowly improvin , I don't know how to hone my problem solving skills (I practise solvin')

And this is rare because my optimism never diminishes normally .

Have any of you faced this and how did you come out of this "code slump" and any tips on improving codin will be deeply appreciated ?

When normalcy is the only distinction in coding you feel you can reach not heights of greatness

And also , could anyone enlighten me on why my O(nlogn) solution in java failed :( : Subtraction

Thanks for your time , cp and the community are truly awesome :)