AlexArdelean's blog

By AlexArdelean, history, 10 months ago, In English,

Hello ! I am having trouble with Codeforces round #477 Div. 2 D — Resource distribution.

I cannot find any special test case in which this type of thinking is wrong :

Explanation of the code

First we can binary search the minimum k1 such that the value of the smallest element >= x1 / k1, after that we can just sort the vector and remember the initial positions of the elements that so we can just verify that the (k1 + 1)-th element >= x2 / (n — k1), because n — k1 is the maximum number of elements for the second service that we divide x2 by. If the inequality is correct then we can just output the solution(meaning we output the indices of elements in the vector because we stored them). Do the same by finding the minimum k2. If you find no solution output No

Explaining :

Observation : if the smallest elements of the groups respects the condition of value >= x / k then the rest of the elements will respect it.

Fact : The smallest element of the vector needs to be in a group also.

A conclusion of the fact : We can just find ki(where i is 1 or 2, we analyze both), then to be sure that we can build the other group we can find the most suitable case to be biggest n — ki.

Another Conclusion : We can binary search ki, and to have the largest numbers, so by the observation we made earlier, we can just grab the smallest elements for this group after which we get the most suitable condition,

Conplexity : Complexity of O(N + log2(N) * 2 + N * log2(N)) = O(NlogN).

But with this type of thinking i get a WA on test 5 ! I would really thank anybody who helps me ! This is my submission 39044055

Read more »

  • Vote: I like it  
  • -4
  • Vote: I do not like it  

By AlexArdelean, history, 16 months ago, In English,

hello ,

i know i didn't totally listen to the editorial but i don't understand why my implementation could be wrong and why i get WA at test 9 on problem E of contest 896.

My implementation is 33780827.

i thought about keeping the square in which my element 1 and element 2 are and i am keeping it using a global variable k which i use to mark the square in which my element is. i am introducing new squares by increasing k and increasing by it, removing a square with a matrix whatwasthere and decreasing by the value of whatwasthere[line][column] of the first element of the query , and display yes if the square in which the first element is equals to the square in which the second element of the query is

Read more »


By AlexArdelean, history, 17 months ago, In English,

i started simulating round 445 8 minutes after i registered , but then when i submitted my solution to problem A i was sent to a bad gateway 504 time-out (servers in maintenance or something). after that it all froze, and i left the simulation but i want to know why did this happen to me

504 Gateway Time-out


Read more »

  • Vote: I like it  
  • +2
  • Vote: I do not like it