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 mayb...

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 <...

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 anothe...

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 tim...

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 brut...

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 divis...

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 m...

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 2063 24...