It's nice to know that you idea for hard problem (Div 1 C) (for me certainly) is absolutely right=) But not enough time for debugging and AC=(

I have solved the div1 A problem using the mentioned algorithm, but I still receive that TLE error on the 31st test. I use Ruby. Is there a Ruby solution, which will pass the time test?

Here is my algorithm:

q = gets.chomp
left = []
right = []
i = 0
q.each_char do |char|
  i += 1
  ((char == 'l') ? right : left) << i
end
puts left
puts right.reverse

Thanks in advance!

Can't view images from the problem Div1 D: 403 forbitten. :-(

I assume you meant “when i is a divisor of x” instead of “when i is a multiple of x.”, in Good Sequences.

For Div2 D Good Sequences, I don't understand why the sum of the number of the diviser from 1 to n is O(nlogn). Can someone prove it?

Div1 A / Div2 C Escape from Stones (Author: DEGwer) :

My solution is in O(2n), But code is so simple like it,

int main(){
	string a;
	cin>>a;
	for(long i=0; i<a.size(); i++)
	if(a[i]=='r') cout<<i+1<<endl;
		
	for(long i=a.size()-1; i>=0; i--)
	if(a[i]=='l') cout<<i+1<<endl;
	
    return 0;
}

Div1 A/Div2 C

Finally, you should print the integers in the first vector by default order, after that, you should print the integers in the second vector in the reverse order.

should be: Finally, you should print the integers in the second vector by default order, after that, you should print the integers in the first vector in the reverse order.

2 problems of 7 are made by round author)

I solved DIV 2 C by looking at the input and output, I never understood the problem statement !!

Could someone explain DIV1-C in more detail? Thanks.

Div2 C Escape from Stones can also be solved using Doubly Linked Lists.

Maintain a pointer operatingPointer which is initialized to the head of list (head of the list contains 1).

if we encounter 'l' at ith position of input add i+1 to the left of operatingPointer and update operatingPointer to newly created node.

Similarly if we encounter 'r' at ith position of the string add i+1 to the right of operatingPointer and update operatingPointer to newly created node.

Then print the whole list.

Implementation using Doubly Linked Lists

For Div 2 D/ Div 1 B, why do we have to update d[i] for all divisors of x? Can someone explain? Thanks in advance.

Could a top-down approach be used for div1 B/div2 D? I tried a top down approach but I am not able to memoize it.

In Div A/Div2 C Escape from Stones the algorithm is easy to understand if someone explains it,

but I don't understand how this solution came to be, which trail of thought led to this solution.

can someone please explain it.

I don't think editorial nor comments explanation on solution 264A - Спастись от камней are intuitive so I'll try to explain how I came up with a solution.

You can visualize the problem as a binary tree. Each node is responsable for a interval [a, b]. Starting from the root, responsable for [0, 1], if you go left then root will have a left child responsable for interval [0, 1 / 2]. Since you're a left child, last time the stone fell on position 1 / 2, the end point of the interval.

Note that from that child, it doesn't matter if you go left or right: the stone will never fall on a position bigger than 1 / 2 (the end point). The ideia is: since a stone always fall on the midpoint (a + b) / 2 of the lower and end points, it can never fall after the endpoint. In fact, the stone must fall infinitely many times to the right to reach that endpoint. So, we were on a node [0, 1], the stone fell and we jumped to the left, creating a left child [0, 1 / 2] and we now know that there is no way the stone will every fall to a position > 1 / 2. This means that in the final solution, the current node [0, 1 / 2] will come AFTER all nodes (descendents) that come after this one.

If we jumped to the right instead, creating a right child responsable for interval [1 / 2, 1] we can show the same way that the stone will never fall before the starting point 1 / 2. This means that the current node will com BEFORE all nodes (descendents) that come after this one, since we know that the stone can't fall on a postion < 1 / 2 from now on.

This is an algorithm: if in the i'th stone we jumped to the left, we now that stone i will become AFTER all next stones. If we jumped right, stone i will become BEFORE all next stones.

Code: 23071895

Strange! My C++ code got accepted with printf but got TLE with cout. This is too harsh

I'm unable to solve Escape from Stones in java. In spite of using fast io, it always gives me a TLE now matter how much i optimize it sol did anyone get it AC in java?

In DIV 2 C I took 2 variables hi = 1 and lo = 0, if character is 'l' then I just change hi = (hi + lo) / 2 otherwise lo = (hi + lo) / 2 and mapped the value, sort them and print them, but got WA on Testcase 11, could you please tell me what is I'm missing?

In Div 1 A Stones falls in 'k' position and print the stone position from left

I calculated 'k' and 'd' as k=(X+Y)/2 and d=(Y-X)/2 And if 'l' then x-=d otherwise y+=d. then sorted the array which contains 'k' s value and its position no. but my implementation isn't matching with the test case..

Did I misunderstood the ques or my idea is wrong?

CODE

For those facing TLE in the problem Div1 A (Div2 C Escape from Stones) in C++ even with O(N) time complexity the reason can be endl vs '\n'.

'\n' inserts a new line to the output stream while

endl inserts a new line as well as flushes the output stream.

So using '\n'can solve the TLE issue.

Also you can use fast IO with cin/cout too instead of using scanf/printf by adding these lines in your code.

ios::sync_with_stdio(false);

cin.tie(0);

cout.tie(0);

I solved div1A using a binary tree, if character is l then i add to the left of parent node otherwise i add to the right, then an inorder traversal will give the answer but im getting TLE at testcase 31 idk why since my code is implemented in O(n) complexity. My solution(https://mirror.codeforces.com/contest/264/submission/54413614)

Something is wrong with the testing of the question Div 1(A)/ Div2(C) . Got 2 TLE's on a O(n) solution [Test Case 31] , changed endl and to '\n' and then got runtime error on test 41.

TLE — https://mirror.codeforces.com/contest/265/submission/63245660 Runtime Error — https://mirror.codeforces.com/contest/265/submission/63246396

I have an another approach for div1B. for each number check the maxm times a divisor has occurred from all the divisors of a number and then increase the maxm by 1 and iterate again and update all the divisors

code 87253298

Can someone please explain problem div2 B in more detail?

DIV 1B / DIV 2D is there any other way to solve this problem without dp because i am not able to understand the editorial solution.

great contest

Good