OJ Board

Hello.

I have tried to solve the problem 11630 : Cyclic Antimonotonic Permutations, but I repeatedly got Wrong Answer.

This problem is very easy to validate my outputs, so I can ensure that my solution is correct, but Online Judge gives WA again and again !

Validation requires Special Judge but ...

Krzysztof Duleba, Thanks very much.
I will keep in mind that a trivial but very important rule!

I can't know why it gives me CE.

please, help me. :)


//uva 10986 sending e-mails

#if 1
typedef long long xint;
#define format "%lld\n"
#else
typedef __int64 xint;
#define format "%I64d\n"
#endif

#include <stdio.h>
#include <queue>
#include <vector>
#include <algorithm>
#include <functional ...

To kalinov :

Thanks for pointing out my wrong thoughts! I was just a fool.
and I am sorry I posted hastily although I haven't implemented it,

Now I got how to make it using Plane-sweeping.
Thank you very much.^^

I think there is an another approach of this problem.

Its complexity is surely O(NlgC), where C is the upper bound of input scores, or coordinate-value : 10^9


Although balanced binary search tree (or, RB Tree) is virtually the most simple solution to this problem, I think, but there may be an ...

How about think of Divide and Conquer?
Divide a large rectangle into four smaller rectangles.

Coordinates are lower than 10000,
therefore at the worst cases time complexity is about O(10000 * 10000 * lg(10000) ).

But this rarely happens.
In fact, N is quite small (N ≤ 100), so it will fit in the ...

This problem is not so difficult.
Once you got a simple idea, you can make out a linear algorithm.

Another Hint)
The manhattan distance
between (0, 0) and (2, 3)
between (0, 0) and (3, 2)
between (0, 0) and (5, 0)
...
is same.

Your output is correct.
I think there are some other counterexamples.


This problem is not so difficult.
A simple idea will lead to an O(n) algorithm.

I have an another question.
I also know how hashing works, and how trie works, (and surely how BST or set-dictionary works, too),
but in this situation how should I implement tries?

|∑| = 26, i.e. the number of available letter is 26 ('a' through 'z'),
and almost string's LENGTH is about 10,

so ...

Can anybody give me some tricky inputs?

I think my algorithm is not too slow;
It gave me "1.4 sec WA".

maybe.. O(NlgN * 10 + M(2^p + p * (2^p) * 10 + 2^p * lgN * 10)),
where the constant 10 comes from comparing strings.

That's enough. The constant 2 is not so important.

If your implementation of this algorithms into source code is right, you will get accepted.


But when you want to make it faster, you need some optimizations.
The operation phi <- phi * (i - 1) / i takes 2 operations, one multiplication and one ...

Do you know how it becomes O(N lgN)? Where the notation "lgN" comes from ?

For every integer K,
the number of prime factor(may same) that divides K is less than O(lgK).

More clearly,
e1 + e2 + e3 + .... < lgK, where integer factorization K = p1 ^ e1 + p2 ^ e2 + p3 ^ e3 + ....


Because, for ...

well, I also did not use STL. I wrote my own writeen PQ - a heap.

I think your implementation into source-code is not efficient enough, maybe.
Optimization is required, or, get rid of inefficiency-making-elements.

I have been bothered, too.
My AC Program outputs


1.224323
2361.005761


In fact, at first, my output format was rounded to four decimal digits after the decimal point,

i.e.
if(-EPS <= area && area <= EPS)
printf("0.000000\n", area);
else printf("%.4lf\n", area);

This gave me WA.
I didn't ...

A simple one :

input
25
2 3
2 4
2 5
2 7
4 73
5 29
6 329
1230 3728
23529 55444
50000 60000
90888 90888
2 100000
100001 200000
1000000 2000000
1999999 2000000
2000000 2000000
2 2000000
182 298149
16871 199290
34 28711
6163 6163
7777 7777
12345 12345
1725777 1725777
10 10

output
3
5
8
13
325
94 ...