What's Jubilee?

Actually that's interesting point. You can generalize it a little bit. I saw previously some comments whether it would be 0,25 rated, 0,1123 rated, etc. I would go even further. For example it could be 2 rated, which means that rating change would be doubled. It could even be -1 rated, which means the better you do, the worse rating gain.

It could be an x rated round with x being a real number. We could also count the expected value of rating ratio. I think currently it might be something around 0,75-0,8 rated round.

NANI!

Why would we do that? My skills have regressed so much that I can't even clear a div2 round ... (*sobbs in a corner)

Google translate has left me even more confused

"Bro if someone will choke me and chill, lots of fun will do the code for fores"

i am, although not red yet :(

I only realized it wasn't a person when I clicked it.

Meanwhile in China we have the ICPC East Continent Final in the upcoming weekned, failing final exams here I coooommmmmeeeeee

Because div2 users> div1 users.

it is hard to create hard div1D-div1F problems so just relax

May God bless you too !! Hope so you will not become newbie as you seem again. I would suggest work on the problems rather than just complaining. Also in case of server doesn't work well it will anyway don't affect your performance because you are still not capable of solving even C problem in any contest :D

Reminds me of Lucy

Okay, maybe not as easy as I thought. we can't just do "distribute k sweets among i students" because we also need to make sure gcd doesn't become some multiple of x.

Try

4
1 3 4 2

Test cases in C : 6
2 3 4 1 5 6

6
1 3 2 4 5 6

2
2 1

Probably: 2 2 1 Not sure though, ans = 1

Link?

doesn't to_string() works on codeforces ??

https://oeis.org/A000740

I tried the same thing but I got WA

Yeah, even I got it that far then I didn't know how to proceed

DIV2 D https://ideone.com/PvYJio This is the link to my DP code. Just got 1 minute late in the contest.The DP code itself is self-explanatory.

Inclusion-exclusion:

1. add the number of ways when the numbers are multiple of g.

2. remove the ways when the numbers are multiple of g multiplied by a prime

3. add the ways when the numbers are multiple of g multiplied by two distinct primes

4. ... and so on

B: Java BigDecimal with "a lot" of extra decimal places, then just string.indexOf(c). That pass the system pretests.

For B, you could actually code it like you'd do long division in real life. Store the digits of the quotient in a vector. Whenever an intermediate dividend is attained twice, break the loop, possibly using a set. Then just check if c exists in the vector. If it does, just print the position(1-indexed) and if it doesn't print -1.

For C maintain a map/dictionary/hashset with int, bool with values for if the number is a record before removing any number. Then take max(p[0], p[1) as maxsofar and the other as secondmax. Now iterate through all numbers. If they are bigger than the secondmax then that means you only need to remove the maxsofar element to make that element a record. Store the frequencies of what number must be removed in a map. Then just check the max value of frequency and in case of a clash, the minimum of the two. You'll also need to subtract one of the frequency for a particular element if it was previously a record because in removing that number you'll also reducing a pre-existing record.

Yes

sorry my poor englishh, you can compute current records, if i'th element less than only one element on previous all elements, you can push vector <pair<int, int>> these elements, first is p[i], second is only one element that (p[i] < p[j] && j < i) p[j], if i'th element equal this vector's second element current_ans + number of vector's elements (v[i].second == p[i]) then, if i'th element also record element current_ans — 1, you can finish this problem.

A somewhat different(maybe) approach:

For each element find number of elements less than it and before it in the permutation. Get all elements such that there is exactly one element before it that violates the condition of this element being a record. Say we store them in c Now for each element find all elements greater than it c. Observe that we can get number of records in O(1) for each element being dropped.

Note: All of the above computation can be easily done by a merge sort tree

semi rated meaning ? sorry I am new !

In my opinion problem B,C,D,E were from almost same difficulty level.

Please tell me it is joke.

if you tell me about it during contest, i would solve D, E.

yes with fft we can find from what all positions there is a possibility of t being there. the idea is for finding at pos i we need ((s[i+j]-t[j])^2)*(s[i+j]) summation over j from 0 to m-1 to be equal to zero assuming value for character '?' to be zero and rest some positive value. This we can find for all i using convolutions(which can be solved by fft).

NOTE: We are not using any special knowledge about t here.

Yes, the idea was finding the number of wildcard matching in strings, which can easily be solved using FFT. I was trying the same, fell short of time. After this was a simple DP solution.

For fft, technique try to find the following sum, . The places, it is 0 are the places where the string T can match string S, from position i. Expand the expression, which is simply prefix sums and one convulution using FFT. Using FFT in this problem, we can do it for general strings as DP is independent of it.

This is actually what is explained in above comments too.

http://codeforces.me/blog/entry/49613?#comment-335977 this can be used to solve it for any pattern (not limited to "ababababa...")

Nice background for coding :P

is that corner case?, if yes too sad

I couldn't find any answer greater than 50. You can prove a bound O(B) using the pidgeonhole principle on the number of steps until finding a cycle.

And why should the answer be 1 and not -1 can you please explain?

4/22 is a repeating fraction and 5 never comes in the sequence. Please have a look once before posting

Ummm.. Answer is definitely -1

4/22 = 0.(18)

5 cannot be found.

There was no repeating numbers in the sequence, so your example is invalid.

From the statements: a < b.

If n <= 2 output is always 1

You basically keep current maximum and second maximum on the array as you iterate. Removing maximum element will add record if(a[i] > maximum2 && a[i] < maximum). The rest is easy from here.

I implemented a solution which is n log n

No, if we remove 1 the record numbers are (9) and removing 9 they are (5,8)

The sequence will be 4 3 5 2 .. 4 (larger than 3) and 5(larger than 3 and 4) are records.

since 1 < 3 then the answer will be 1

The problem isn't asking for the longest increasing subsequence, it's asking for the number of indices such that a[i] is larger than a[j] for all 1 <=j < i

Something is wrong with the input. The numbers are permutation of the first n numbers.

Also in the question it was mentioned that we need to print the smallest of all the elements which when removing gives us the maximum number of records

Dynamic Programming