Sorry if I said something wrong, I didn't mean to to this...

Maybe he or she has 300wpm and 300iq :)

am I reading it wrong or this profile really solved QUE E in 6 seconds?

it's simple.. Cheating

Mabay he had solved them early in the constest but submit them later at the same time

The way I did it was using:

1. A segment tree with lazy updates to find the maximum
2. The painter's problem using disjoint-set-union to travel the array even after the 'deletion' of foster elements

It's a lot to know and implement. I'm assuming there's an easier solution because of that

u can use two ordered sets, where each element is a pair, and in first ordered set store each (val[i], i) and in second ordered set store (i,val[i]). this made it quite easy.

All I did was just kept track of the right and left index of any given index at any moment. And after each iteration, I updated them as necessary.

You can view my code here: 52867981

Just a normal implementation.

doubly-linked list + max-heap

I think the easiest way is using doubly-linked list + sorting the values. Using a set(as max heap) also seems easy to implement.

me, me too I pour my 1 hour on that problem

me too

yeah..i'd like to know ,too...

Just fix the gcd and find two smallest numbers with such gcd. I think that's very easy problem for G.

I did the following thing:

1. store the occurring index of each element in the range of a;
2. loop through the whole range;
3. which looping, just assume the current gcd we are checking is some multiples of current i, then the first two we find would be the local minimum, thus we should stop here.

The number of operations should not exceed 2.4e8.

You could check my implementation here: 52849391

Suppose we find $$$\underset{x | a_i \text{ and } x | a_j}{min} (a_i*a_j /x) $$$, Note that minimum lcm of any two values is the answer for the stated. Therefore solution to first problem is solution to second. Now to solve first, for a given x, for minimum, a[i] and a[j] must be minimum. Thus for each x, just consider its two multiples that exists in array.

I have a funny solution for G. ACC at the moment but probably hackable. The idea behind my solution is to try as many promising pairs as possible and stop just before we reach the time limit, hoping that we were lucky enough to find the best pair.

My implementation is here: https://codeforces.me/contest/1154/submission/52868067

The main computation is simply iterating all pairs in the order of smallest to largest. In order to speed up the computation we want to find a reasonable upper bound for lowest lcm before this main computation. This allows us to stop iterating i,j pairs when j>bound. I'm finding the upper bound by iterating all pairs of the lowest 30 non-duplicate items. Duplicate items can be used to construct a worst case scenario where we iterate the same pairs over and over again and reach the time limit before we get to try the optimal pair. We deal with duplicate inputs as a special case before the main computation. So the actual implementation is in this order:

1. Deal with duplicates as a special case
2. Find upper bound for lowest lcm by iterating all pairs of the lowest 30 non duplicate items
3. Main computation: try all pairs from smallest to largest, with a speedup using the upper bound.

Yeah, I think it will be good for everyone that rating below 1600 solve all the problems after contest.

I agree this was a great Div. 3 contest, although the tasks could have been explained better. I had to ask questions about 2 tasks because of ambiguities in the statements.

I, for one, spent 15 minutes to realize I've declared an array using 'bool' instead of 'int'. Yeah.

Maybe my code can give you some help?Actually problem E is not as complex as we thought...Your text to link here...

You can check out my soln- I did it using doubly linked list https://codeforces.me/contest/1154/submission/52864142

Got 37 TLE as well at first, but try using next/previous arrays instead of the boolean 'taken'. Where next[i] — the next student after i that isn't taken in any team. (so goes with previous)

EDIT : With the boolean array, the complexity can come close to O(n^2)

It was because of one of my testing solutions. I was not sure that it is correct and just forgot to tag it as "time limit exceeded or correct". All is ok now, the main solution is fast enough and written without bugs :)

Problem F:

F : Just consider k shovels with least cost. And store for each 1 <= i <= k, maximum number of shovels you'll get for free, if you buy i shovels. Rest is just knapsack.

Big OOF

Just curious how did this cause the bug in the checker ?

sure you can use your battery during sunlight whenever your battery > 0; but that's not optimal strategy

what according to you is a strong pretest?. There were only 5-6 conditions which were needed to be handled

Wait

Also, my contests tab shows "no items". Did I do anything wrong or it's not updated yet?

thank you, i hope my rating change to Specialist.

Radewoosh Swistakk Your worst nightmare became true :P #NOSTALGIA

try this, input : 1 2 3 it's supposed to print 5 because when you start on wednesday you can eat 2chicken, 2 rabbit and 1 fish, but yours print out 3

This may happen in many problems who have tight time complexity so it is better to use long long int only where it is needed and always use the fast input method. otherwise, in many cases, it becomes very frustrating to find these kinds of mistakes.

Arrays.sort on primitive types is quadratic worst-case. Try using Arrays.sort on Integer or Collections.sort.

This might help: soln

And so what? Did you see fast enough solution to our version of this problem in the link you posted? We have seen this link, but still gave the problem because we haven't found any fast solution in google.

My Approach :

We need to buy K shovels at lowest possible prices. We will obviously use the K lowest priced shovels. Thus sort the array.
Now we only need to save the offers (x,y) in which x <= K as we cannot buy more than K shovels.
Make hash array where hash[i] stores maximum number of free shovels we can get by buying exactly i shovels using one of the offers.
hash[j] = 0 implies no offer available on purchasing exactly j shovels.
Now time to apply DP!
let DP[i] be minimum cost to buy i shovels.
To calculate DP[i] iterate j = 1 to i, and find min of DP[j-i] + cost to buy j-hash[j] shovels starting from index i. (cumm[i]-cumm[i-j+hash[j]])
What we are doing is for every i simply apply every offer and check which gives minimum price and store it.
DP[k] is required answer.
Link to my solution.