I wish if they could make another round type with no pretests .. why is it so wrong that if I submit a solution I will get AC or WA instead of pretest passed and then a short sad story

Yes, awoo became orange a few days ago.

After 4 years of hard work, nothing is impossible.

Congratulations, awoo!

You should know that this is not your first round.

You should know whether or not it is rated.

[Again :( ] ^^ halyavin — The Hacking Machine

Halyavin is done hacking, looks like systests are over.

Binary Search on length and check the possibility in O(n) by traversing the string.

Two pointer

Binary search on substring size.

To check if you can get from a position to other in certain number of moves, the sum of absolute differences between positions in both dimensions has to be not bigger than the numer of moves, and be of the same parity.

I did binary search on the length of the subsegment.

I dont think G needs segment tree beats though it is nice if it can solved that way.

we can compute lcp array and then for each query we can keep 2*query size ranges and perform something like for how many pairs of a and b will particular range be minimum value (its similar to solving sum of minimum over all segments in an array but instead we have weights to elements here).

In general — digits and masks DP. Calculate the following dynamic programming: dp[pos][mask][f], where pos is the current digit of a number (starting from the greater one), mask is the binary mask of used digits and f equals one if prefix of our current number is the same as in the number n. You can calculate the sum of suitable numbers from 1 to n using this DP. Then the answer is calc(r) - calc(l - 1).

Probably DIGIT DP, however could not implement it ;(

I always try to make something recursive like answer(A, i) that is filling array A from 17 to 0 and i is the position where we can choose a value. Complexity would be 10^18, but if we make these optimizations complexity drops: If the number cannot be in the range [l,r] return 0; if it will always be in a range [l, r] ask the answer from another dp function.

Yes, the contest

stk.erase(x);
st.erase((*x).S);
x++;

This is undefined behaviour because you are doing something with an iterator that has been erased.

Use deque data structure , its pretty fast

The first booth we can't buy must supply the most expensive candies. So we can simulate this procedure. Calculate the current whole price and find the most expensive booth. Then we can compute how much we will spend before we buy the last candy in this booth. Then we subtract the cost and add the quantity.
Until None of candies can be bought.
We can use binary indexed trees or segment tree to compute the cost and the quantity.

did you check if diff in x is divisible by 2 and y ?

because if both is you need 2 chars to cancel each others

for example if you have RUR and x=1 y=0 then it would be RLR

are you failing on test 5 like me(http://mirror.codeforces.com/contest/1073/submission/44891148) i also implemented using two pointer kind of thing.

in test 5 all 'R' are 24 and all 'L are 27 in number and final destination's x coordinate is -59 which is unachievable if we even turn all 'R' to 'L' which will give 51 'L' hence we can at max go to -51 in x direction isn'it test case no 5 is ->

100 URDLDDLLDDLDDDRRLLRRRLULLRRLUDUUDUULURRRDRRLLDRLLUUDLDRDLDDLDLLLULRURRUUDDLDRULRDRUDDDDDDULRDDRLRDDL -59 -1

r=24 l=27 d=32 u=17 please comment how it is possible

I'm not sure, but I don't think there's a rule that difficulty(C) <= difficulty(D)... |-)

The problems aren't always sorted by difficulty in educational rounds, I think.

I figured out C easily and implemented it within 20 min, I had 1.1hrs to do D, but couldn't. :(

I did the pretty much same. :p

Binary Search for the answer. To check whether you can have a subsegment of length x as the answer iterate over all the subarrays of length x and then all you have to check is whether the difference between the expected position and the actual position is greater than the subarray length or not and also if the difference is less than the subarray length we need to check the parity of the difference between the 2 values.

can someone tell me why I get so much dislike, i dont think that my comment is annoying people like this. and I also wonder why my contribution is a negative number (-4). why this happened to me, plz help me, (T-T)

Nothing strange, since the newer compiler provides better optimizations for your code, therefore better time.

It seems to me like you didn't "change compiler to c++11" between the two submissions, both of them were submitted with GNU C++11. The difference is one of them uses fast input and int type, while the other one uses "slow" input and long long type. Obviously, the latter one will be slower. No surprises there.

P.S. your solution is already sub-optimal because it runs in O(n * logn) time. Had you implemented the optimal solution (which runs in O(n) time), then it wouldn't have mattered which types and what kind of input you used :)

On each iteration you have some money and sum of remaining candies. Just buy as much of every candy as you can and then, when your remaining money will be less than sum of every candy left, just try to buy them one by one in O(n). Also maintain sorted candies to check if remaining T is enough to buy highest costing candy. If not no need for them and just skip until you have one that is less. During that decrease sum of all candies left.

Apparently T's decrease is logarithmic so you end up with O(n log(n)). There are possibilities to improve performance in many ways, but none of them are needed to pass the tests, sadly (I did some and now regretting the lost time in implementation).

I solved it with just 1 BIT. You try to buy 1 candy for every booth, if you can't, then you can binary search the position where sum of 1...i becomes greater than T, and you erase it from the bit (you update position i, with -value[i]) and keep doing that until you can buy 1 candy for all remaining booths. At the end, you had to do N Binary search which is O(N*ogN*logN) or O(N*LogN) if you use the trick of binary search on BIT. My submission

Your forgot to use your fastread: 44876642

Maybe 'endl' (with flush?) issue? Try to change to "\n" (or '\n'). Reading 4e5 data, maybe use yours 'fastread'?

There can be two reasons for invalid input. 1. Make sure you have newline character at the end of the generator output. 2. Make sure the last integer or character or whatever variable of generator output is followed by new line character instead of a space i.e. run loop for n-1 numbers and print last number followed by new line character instead of space followed by newline character

In C, we can see that if we do change a substring of size k, then it doesn't matter if we change 1 or k elements in the substring. An easier approach would be to change all of them.

Let's say that we're at (x, y) and we have to go to (a, b). The shortest way between the two points is the Manhattan distance between them. However, if your k is greater than this Manhattan distance, you might want to 'waste' some moves before you reach there. It is easy to see that the number of moves you 'waste' will always be even.

So, if we do have to change this k subsegment, we can do it only if we can travel the Manhattan distance, and waste some moves if any. More formally, you get k >  = dist((a, b) , (x, y)) and (k)mod2 = (dist)mod2.

Another observation is that if you get a valid subsegment of size k, you can get it for k + 2 as well. However, we don't know about k - 2.

So, we would binary search over all the even sizes and odd sizes of k separately and pick the minimum. We can binary search as the function of whether k works or not is monotonic. Or in other words, it's of the form NN...NYY..Y.

what's wrong with him ??

Maybe that is sunzhihong's clone :))

cheat :))

After successfully generating the test data, print out one last endline character.

(This one is not required in manual hacking, yet mandatory for generator-based ones).

log(t) times in place of log(n) times

Can you tell the proof? I am only able to figure out by taking values.

How to solve E?

digit dp

DP is also a good choice!