like!

The network in a train could be really instable, I have suffered several times because of this.

Hope to see you in IOI! ^.^

If you mean a JavaScript alert that popped out about 30 minutes ago (for me), it's a change to the rules:

Attempting to digitally extract other contestant's code during the hacking is considered cheating. You may not use any technical/digital tools to obtain other contestant's code, including (but not limited) ORC, traffic capture, browsers plugins and so on. The only allowed method to analyze other contestant's solution is reading it in a hacking window. However it is allowed to manually retype the solution or it's parts to run it locally.

(Can-do's and Can't-do's, item 8)

If you mean the pop-up a few minutes ago, the theme of the announcement was 'Hacking during the contest'. It said, that we aren't allowed to use any technical help in form of tools etc. to extract defenders code. We are only allowed to analyse it by looking or we may also write parts of the code down manually. Edit: ah, a few seconds too late.

copying contestant's code to hack using any plug-in is considered cheating, but it's OK to retype it

Глупо задавать такой вопрос, если уже прочитал это оповещение, тем более не в том топике.

Продлили на 10 минут же

А мы уже задачи почти обсудили.

I passed and I got WA on pretest6 ...

And I found that I may got WA on this test

4
1 0 5
1 2 3
2 1 2
2 2 1

The answer should be
NO
YES

But sometimes even i passed this case, i got WA on pretest2 again.

Я смог посмотреть решения других людей, прежде чем контест продлили на 10 минут. Это нормально ?

Да, кстати? Учитывая то, что раунд еще идёт, а решения можно было посмотреть, наверное, стоит сделать его всё же нерейтинговым.

Я писал странную симуляцию, но без очередей, просто после каждого хода я отмечал тех, кто в этот раз кого-то убил, и в следующий раз рассматривал только их. Поскольку если человек никого не убил, то больше уже и не убьёт, ему остаётся только ждать смерти или конца игры. Это будет работать за линию, потому что количество убийств — O(n), и количество раз, когда мы убедились, что человек больше никого не убьёт и выкинули его из списка — тоже O(n).

same to me

Agree to delete hacks and submissions after 01:59.

agree!! with the second

I think no one can see others' solution until judging is started.

I think that cancelling the submissions made after the contest ended (01:59) would be the best solution. Also, please tell us as soon as a decision is taken.

you speak in your case , not generally , in Div2 i saw Problem "C" solution so if i submit it and gain points and my rate increased you don't mind about this ?

But the contest was extended, because there were problems with server in the end of the contest and while someone was not able to submit his solution in last 5 minutes in contest it would be unfair for them.

and only 50 solutions which passed pretests sent on this interval

I gauss it will be unrated because of the extra time.

Sorry, mixed with div2 C

I think you have integer overflow in bad function

long long overflow in bool bad(int a,int b,int c)

I think I understand your idea. would you explain more about your code? what do the add & query functions do?

Can you please describe this convex hull trick in your own words.I would be pretty thankful if you do.

One can use generator for this ;-)

edit: I misunderstood the first version of your question. I thought you are asking how to use it for hacks. Now I cannot remove my comment...

Put i in a queue(kill list) if a[i] > a[next[i]] and i is not dead, then go through the queue and start killing people and update the next[i], you might need to use 2 queues to do this.

In your tes case, there is only 1 number in the queue every time, so O(n).

Store a list for psychos, who will be killed. And in each turn recreate this list by the previous list(it is possible, because in next turn only those psychos can be killed, who was next after psycho from previous list(who were killed in previous turn))

if a > b and a^x < b^x, it is mean that "^x" operation is chenge first different digit in a and b.

If bit i is 1, then A0B > A1C (A contains i — 1 bits, B and C contain n — i bits).

If the first bit of x is 1, we swap two halves of array, that gives us 2^n - 1 × 2^n - 1 inversions. The i-th bit gives inversions in the same way, but we swap halves of 2ⁱ arrays sized 2^n - i, for 2^2n - i inversions. Clear to see every bit is independent from the others.

I wrote down all the numbers in binary when n = 3 and x = 111, instantly I found the beauty of the answer:)

The least significant bit affects each pair of subsequent numbers ((0)-(1), (2)-(3), (4)-(5), etc): if LSB of x is 1, then we count each pair (2^(n-1) at all), else we don't.

Next bit affects pairs of subsequent groups of 2 numbers ((0,1)-(2,3); (4,5)-(6,7), etc), each pair of groups adds 2 * 2 pairs.

And so on: i-th bit affects pairs of subsequent groups of 2^i numbers.

I just solved a simple case by hand:

101

000 101
001 100
010 111
011 110
100 001
101 000
110 011
111 010

1 * (4 * 4) + 2 * (0 * 0) + 4 * (1 * 1)

dp[i] — number of bad pairs in set with (2^i) numbers

dp[i] = (s[i] = 1)·(2²ⁱ) + 2·dp[i - 1]

0 ^ 0 = 0
1 ^ 0 = 1

0 ^ 1 = 1
1 ^ 1 = 0

so if x[i]==1 must inverse bit, and if x[i] == 0 the bit will not change.

eg.

x=10
MDC    NFC
00(0)  10(2)
01(1)  11(3)
10(2)  00(0)
11(3)  01(1)
ans is 4 = 1*2*2

x=01
MDC    NFC
00(0)  01(1)
01(1)  00(0)
10(2)  11(3)
11(3)  10(2)
ans is 2 = 2*1*1

x=11
MDC    NFC
00(0)  11(3)
01(1)  10(2)
10(2)  01(1)
11(3)  00(0)
ans is 6 = 2*1*1 + 1*2*2

I randomly guessed ans+=2^(i+length(n)-2) for '1' in ith digit.

No matter whether this contest will be rated or not, plz start system test first. Many people are waiting for the result anxiously。

really, can you do it after systest? It is rather more interesting for most copetitors.

What about people who left their computers immediately after finish of the contest?

I wrote a lot of scripts and found that no more than 8 persons from both divisions tried to see other's solutions and passed system tests after it. So I don't see any reason to make it unrated for all. Sorry again about the issue.

I think that it's quite unfair to distinguish those participants who have accepted their solutions after viewing the other's code and those who haven't viewed code in "intermission" but have also got accepted verdict. The reason is that one cannot be sure that they won't be able to get accepted without viewing the other's code. So, to my mind, they shouldn't suffer from the fact that they have viewed it.

P.S. I don't refer to any of above-mentioned groups.

Convex hull trick входит в моду.

Mine is O(n^3.5) ans passed in in 15ms, so you are the one slowing down the system test...

I think that a solution in O(N^4) should pass because 10^8 can pass in two seconds, indeed my solution is O(N^4)

Actually many people use this, such as myself...3944678

check tunyash comment: comment

It's third or fourth contest, that contains the problem, which has n ≤ 50000 or n ≤ 100000, and you have to solve using simple straightforward algorithm, and optimize it.

I don't know if it's good or bad, but all thinking skills you have to use when solving the problem are useless here, you just have to optimize it well.

I have c*n^2 + n^1.5 but c is small enough (4 seconds). But it's not a simple bruteforce.)

The actual solution has time complexity O(nsqrt(n)log(n)) and we didn't expect bruteforce solutions to pass the tests. Actually we're not ok with what happened! :(

Hi, actually I think I have a O(n^1.5+nlg^2n) solution. The nlg^n part took me too long to think of during the contest, so I was not able to finish it during contest time. The latter part requires hash, though.

The idea is that:

1. Note that we can implement a function cut(d) that given a length d, cut according the rule all XX s.t. length(X)=d. This should not be too hard so I'll skip the detail. The time required is O(n).

2. Suppose you have a oracle function foretell(d), that could tell you (ignore how for the time begin) in a fast enough time, whether there exists X | length(X)=d s.t. XX is in S. Once you have this, the rest is simple. Because if we only call cut(d) on d | foretell(d)=true, then there will be at most O(n^0.5) calls.

3. So the question remain: how fast can foretell(d) be? I came up with an overall O(n/d*lgd) one, and I think there may be better solution. Anyway my version is: For each d, partition the (current) S into segments where each except possibly the last is of length d. Then for each endpoint x of segments, we record two things:

• left_extend[x] = max{l|s[x-l..x]=s[x+d-l..x+d],l<=d};
• right_extend[x] = max{l|s[x..x+r]=s[x+d..x+d+r]},l<=d];

These could be obtained by binary search + hash (hmm..), and we just need to check whether there is x s.t. left_extend[x]+right_extend[x]>=d.

The overall runtime is clearly O(n^1.5+nlg^n), and could pass systest in a mere 109ms. I wonder if there is something better (in runtime / don't require hash .. etc) in the latter part though. Anticipating for great opinions.

285! The CodeForces community can't be undrstood:)

А рейтинг див. 2 уже обновлен

I think no. ;-)