We are following b users and have limit of 2 * a + 100 users so we can follow 2 * a + 100 - b more users.
Time O(1) | Space O(1)
Since constraints are small, we can iterate from 2 to 1000 and find which number has most GCD-ness.
Time O(n * 1000) | Space O(1)
Optimization — We can also reduce time complexity to O( n * log(max(a)) ) by finding prime factorization of numbers in log(a[i]).
Length of number can be atmost 18 we can use bitmasks to try out all combinations of numbers and take the one in which we remove minimum numbers.
Time O( n * 2 ^ n) | Space O(1) where n is length of number
Optimization — If sum % 3 == 0, answer will be 0. If sum % 3 == 1, we need to remove digits which have % 3 equals (1) or (2, 2). You can find cases for sum % 3 == 2. So this can also be done in O(n).
For each index i, keep track of cumulative sum and also maximum positive value encountered so far. Then answer will be max of current position + maximum positive distance you can travel.
Time O(n) | Space (n)
For every bulb, find the nearest blocked cells in all for directions(left, right, up and down). From that you will know how many cells that bulb will lit up in both directions(horizontally and vertically). Finding those lit cells will be slow if you do it by brute force. Instead you could mark the those start and end for both directions. And after marking it for all bulbs, you can check if that cell is lit by any of the bulbs. If yes then add it to answer.
Time O( n * m ) | Space O ( n * m )
How to solve F? Does it use the fact that sequence is super increasing.
For problem E, I used an optimization method as I was too lazy. All I did was that I bruteforced but I saved on each cell the direction I last covered. If I activated another bulb and found that this square is lit in the direction I covered, then I stop continuing the row/column. That is an $$$O(N^3)$$$ but off-course optimized. Passed in around $$$250ms$$$.
For problem C, I stored the remainder of 0,1,2 and handled some conditions(number theory) resulting in a complexity of $$$O(log_{10}(N))$$$ without using any DP.
If you are stopping after you are seeing the bulb its not $$$O(N ^ 3)$$$, its $$$O(N ^ 2)$$$ since you will visit every point only once
I visited each bulb and then visit each column and row from each bulb but with the optimized way I stated above.
Yeah but this optimization becomes $$$O(N ^ 2)$$$ because you dont visit the same vertice again, you are stopping when you saw the vertice that have been already illuminated
Not really. As it can be illuminated from another direction causing WA. So I only save where it was illuminated(its direction, either left, right, up, down). A case like(B=bulb, L=Left, R=Right, U=Upwards, D=Downwards, otherwise empty):
B...
.B..
..B.
...B
Would simulate for each bulb in my code:
BRRR
DB..
D.B.
D..B
BURR
LBRR
DDB.
DD.B
etc...
Edit: Complexity was wrong. I mixed up with N of height and width and multiplication of them.
Employed the same idea for my "dfs", passed in ~400ms. I only assumed that up/down and left/right directions are equivalent: if some cell is directed upwards and is luminated, then the light should have been emitted from downwards, which means that everything in upward and downward directions till the first block is luminated (same for left/right). Most cells are visited only 1 time, with a small minority being visited up to 6-15 times (to check and abort moves in already visited direction).
Link for my submission
Another easier approach for E
Consider only 1 row. You can break row into multiple segments by blocked cells. If a segment contains bulb then this whole segment will be lit else it won't be lit.
Do this for every row and column.
Code
For E, it seems that you assumed that find the nearest blocked cells in one direction takes O(1) time. I used binary search to do this, which is O(logN). Can you elaborate on this?
If
a[i][j]is blocked thenl[i][j] = jelsel[i][j] = l[i][j - 1]. Do the same for other 3 directions.Can anyone help me on B to find the only case I'm getting wrong..
My Submission
I think your solution is not right if I understand your code correctly. You are checking the gcd for all pairs of Ai and Aj. But the answer does not have to be gcd. You should just check all possible values from 2 to the max of Ai.
I solved B and C just a few hours ago.I am practicing to solve B and C fast.I have a question.Will this method help me to solve Div-2 C consistently in Codeforces??
I don't think solving B and C is sufficient to solve Div 2 C on codeforces. You should practice D too. And you can keep track of your progress on kenkoooo(just append your handle at the end of url) along with appropriate difficulties.
Does solving C consistently lead one to become expert or does it lead to become specialist only?
Yes solving C consistently should lead to expert.
PS — I was talking about D on Atcoder not on Codeforces.
space?
space complexity
I saw the solutions for E and I think i gave a simpler and more intuitive one.
Create the matrix itself, and just go over every column and row and do the following:
If you see a bulb, go back until you see another bulb/blocked cell, while marking all the cells as lit. Then continue forward while remembering that you saw a bulb (i.e 'light=true'), and mark cells you see as lit.
If you see a blocked cell, simply set 'light=false', which means that when you continue forward you will not mark cells as lit (unless you see a bulb later, in which case you will go back and set these cells as lit).
With this method you are going over every cell at most 4 times, once in each direction. which means the complexity is n*m.