No, Because it is almost-copy-pasted-part

May not. I think it's just a general idea so that almost every contest could use this template. ^-^

Reply code challenge : https://codeforces.net/blog/entry/74502

sorry, misunderstanding from sentence!

Athena Chu <3

The same to u <3

getting a good rating in Div3 is even tougher :(

The "almost-copy-pasted-part" is almost equal in the announcements of most contests

Good luck and high rating <3

So many downvotes :( . I haven't asked anything wrong :( .

I think you are highely inspired by TVF Pitchers.

Reply code challenge : https://codeforces.net/blog/entry/74502

No, you won't

Would you like to share your secrets... with us :)

if you think you can't, so you can't.

Believing in yourself is the first step to success.

Well, you can jump through the centre.

same

really that's i waited for

Same here :(

Glad to see I wasn't the only one who faced the same issue.
Made me wonder if my account got hacked or something :/

Yes,this happened with me also. Maybe a coincidence, but it happened mostly when I clicked submit button.

Me too. I thought it was my browser problem or something like that and erased cache and it happend again... :(

Same to me ((

me!!!

Yes :/

me，especially problem a

yeap, understanding Problem A was harder than solving it

problem E is difficult to understand

E was the most difficult to understand. I understood A maybe because I had played that game before.

Exactly!

E was really confusing, in the examples they didn't even specify the mod h part

The contest will be rated for those participants who have a rating below 1600. However, participants with rating greater than or equal to 1600 can participate unofficially. Separate standings are available for official and unofficial+official participants.

Even I faced this issue around 4-5 times.

I didn't count but it was infuriating.

Faster than Lightening! Thanks!

Thank you

.

You can use binary search. create a diff array such that diff[i] = teacher[i]-student[i]. sort this array. at a particular point i calculate how much you'll need to compensate for when you choose j. e.g if teacher[i]-student[i] = -2. then we know we need diff[j] >= 3, so as to make teacher[i]+teacher[j] > student[i] + student[j].

you can easily binary search this value in diff array.

Let $$$c_i = a_i - b_i$$$. Now you have to count the number of pairs of $$$c_i$$$ with the positive sum. It can be done in $$$O(n log n)$$$ with binary search.

Create an array of differences of a[i]-b[i] then use lower bound to find good pairs for negative numbers and zero numbers and for positive use binomial coefficient (ncr).

I used PBDS.

It can also be done with sorting; if you have a sorted array $$$c$$$ and you want to know for particular $$$i$$$, how many $$$j$$$ satisfy $$$c[i]+c[j]>0$$$, then you can decrement $$$j$$$ from $$$n$$$ down to the first index where $$$c[i]-c[j]<=0$$$, and count $$$n-j$$$. Then if you iterate over increasing $$$i$$$, this $$$j$$$ can only decrease.

What is wrong with my approach ? ;-;

problem is similar to inversion count, so used BIT tree to solve it, after compression.

Let c[i] = a[i] — b[i]. Now we have to count the number of pairs with positive sum. Sort array c.

Set two pointers, one at index 0 (pointer j) and the other at index n-1 (pointer k). In each iteration decrease k by 1 and find the corresponding index j, by running a separate loop within the previous loop. Exit when j >= k.

Initialize ans = 0, and keep adding (k — j) in each iteration, i.e. ans += k — j

Note that j keeps on increasing in each iteration. We do not restart j from 0 each time.

Time Complexity: O(n)

thanks for taking your time to write an explanation.

Gradually sort?

sorting them will change the order of the indices

and in the problem you need $$$j$$$ to be $$$>$$$ $$$i$$$

Make an array of Ai — Bi, sort it and binary search the right one for each. That's the solution I think.

Maybe you can use the Binary Indexed Tree in value.

First discrete all $$$a_i - b_i$$$ and $$$b_i - a_i$$$.

Then for every $$$i \in [2, n]$$$, calculate all for $$$j \in [1, i)$$$ which $$$b_j - a_j < a_i - b_i$$$

The time complexity will be $$$O(n \log n)$$$.

There is a 12 hr hacking phase, after which system testing will begin.

Me too!

Same here !

I believe it's called dynamic programming.

Dynamic programming. $$$dp_{i, j}$$$ is the number of good times when we consider the first $$$i$$$ times ($$$0$$$-indexed) and did this $$$-1$$$ "operation" $$$j$$$ times. The answer is $$$\max\limits_{j=0}^{n} dp_n$$$.

state are index and modulo

I think a bound of 10^(7-8) is good for 2 secs, 10^10 is taking it too far.

In fact, you can first discrete all $$$a_i - b_i$$$ and $$$b_i - a_i$$$.

Then use a Binary Indexed Tree to count all the values.

The time complexity will be $$$O(n \log n)$$$.

Use a binary indexed tree.

Insert $$$a_i - b_i$$$ into it after checking how many elements there are before $$$i$$$ which satisfies $$$a_j - b_j > b_i - a_i$$$. Discrete all $$$a_i - b_i$$$ and $$$b_i - a_i$$$ first thing first.

Do you write is serious? The "subSTRING" problem, as you say, is not "more interesting" and can be solved in $$$O(n)$$$ considering $$$3$$$ or $$$4$$$ consecutive characters.

D — data structure problem? The problem "sort the array and do (lower bound or binary search)" is data structure problem?

Can't the substring problem be solved in O(N)?, I did that only after I misread the problem! :( Just check all "3 consecutive characters substring" and "4 consecutive characters substring".

Speed is really need. lol

vovuh made them easy to please div3 ppl

here

I think that this is the perfect difficulty level for Div 3. Myself being an Expert (Rating: 1734), I was only able to solve A, B, C, D. So, I believe that it justifies my claim.