Comments
|
0
Thank you, fixed |
|
+8
because judge system loves Mike Mirzayanov too) |
|
+5
|
|
0
You should sort all numbers inside every list (because lists like {2,3,1} and {1,3,2} should be equal) and use a trie instead of sorting all of lists. |
|
+26
It can be solved using trie that should implemented using hash-table (it is not hashing:) ). You can find list of friends for every vertex. Now you should sort all of them and insert into trie. In some vertices of the trie you can count a number of lists that end in such vertex. So, we have exact solution in O(MlogM) time with small constant. |
|
On MikeMirzayanov →
Mirror of ACM-ICPC NEERC Southern Subregional Programming Contest 2011 (Saratov QF), 7 months ago
+5
for testcase aaaabcdefghij answer is 1 3
in the all rest you are right |
|
0
omg... thank you)) i fixed it
|
|
0
Yes, my mistake. I'll fix it.
|
|
-1
Sum of sizes less than 30KB. Don't panic, please)
|
|
+16
Yes.
|
|
+6
2 VArtem (I dot'n know why I cannot answer in that branch)
Codeforces does not support GIF, but APNG works. In the statement will be APNG picture and link to separated GIF-picture. |
|
0
Codeforces does not support GIF, but APNG works. In the statement will be APNG picture and link to separated GIF-picture.
|
|
0
|
|
+12
Mike Mirzayanov is ACM ICPC team coach.
|
|
0
I think that your idea is good. I was uncomfortable in samples of that problem, too. But the idea of numbering samples just didnt come into my head.
|
|
0
There is an auto formatting of a system for preparing problems. Writers cannot change some labels like "Input", "Output", "Sample test(s)", "Note". It may be changed only by developers of the system. You may request this feature from them :)
|
|
0
You can also use a double click on a cell to display a code (it may be don't work in some browsers).
|
|
+4
May be you compile your code in the debug mode or in the release mode without -O2 flag.
|
|
0
You are right. It can be calculated by your way. Also it is calculated in this way in the author's solution.
|
|
0
I will rewrite editorial more detail later.
|
|
0
I agree. UPD. A beautiful idea came into my head. For integer numbers we can put A = P + (Z, 1) (Z is large). Because gcd(Z, 1)=1 there are no integer points inside AP. So aglorithm will be always correct. |
|
0
I agree that probablity of wrong answer is vanishingly small. But I think that it must be declared that this probability is nonzero.
If you use the magic constant in a competition like ACM - it is ok (in WA case you can just change magic constant). In case of competition like TopCoder/Codeforces you may be challenged/hacked. Also you may be hacked if you use rand() without srand() and run test only once. |
|
0
There are some problems when one or more of vertex of the polygon lies on the (A, P). When we go from A to P and intersect one of such point, the next part of the segment AP may lie inside or outside of the polygon equiprobably.
What we can do if AP contains one of sides of the polugon? It may be fixed if we try your test more times (for example, 100) and at end choose a version, which happen more times than another version. It is some probabilistic algorithm :D. |
|
0
In the task C 4 × 108 operations will work no more than 4 sec on C++. It fits in the limit of 7.5 sec. If you will use "break" in cycle, it can decrease run time to 0.1-0.5 sec.
|
|
0
I want some pagination too.
|
|
0
int ans=0;
FOR(a,1,n) if (rank[a]<k) ans=max(ans, k-rank[a]+a-1); cout << ans; |
|
0
Good luck:)
|
|
0
Solving process... I just read problem and sometimes solution emerges from subconscious. Else I must to little analyze problem for to see a solution.
Practice - yes. The more I solve the faster I find solution. But reading of algo books is good idea too. For fast solving hard problems you must solving more and more problems a lot of time. I solve nonstandard problems from primary schools. And now I cannot solve some hard problems whatever. |
|
0
No, we will have path (1,2)->(2,3)->(3,4) in new graph what is path 1->2->3->4 in old graph.
|
|
0
Let build new graph where nodes are edges of current graph and edge between (a,b) and (b,c) exists if (a,b,c) is not bad triple. Finally just run BFS in new graph. I used hash-table for checking bad triples and my solution has O(NM) time. |
|
On Ripatti →
A little bit of classics: dynamic programming over subsets and paths in graphs, 21 month(s) ago
0
Thanx! Very nice problem)) I added it.
|
|
0
I used hashing and got AC.
|
|
0
можешь даже попрактиковаться
https://www.spoj.pl/problems/SORTING/ |
|
0
it can be solved easy with O(NlogN) by DP.
|
|
On Ripatti →
A little bit of classics: dynamic programming over subsets and paths in graphs, 2 years ago
0
http://www.cs.ust.hk/mjg_lib/Library/Kwong_Ham_94.pdf
it is very old paper:) |
|
On Ripatti →
A little bit of classics: dynamic programming over subsets and paths in graphs, 2 years ago
+1
Counting hamiltonian circuits on a grid is quite different from problems which was viewed there. In article I view foremost masks over subsets and paths in graphs. But in your problem motzkin words and matrix multiplication are used:)
Maybe I will view your problem in fiture article:) |
|
On Ripatti →
A little bit of classics: dynamic programming over subsets and paths in graphs, 2 years ago
0
спасибо, задача очень понравилась)) действительно, дп по подмножествам, только вот без графов и маршрутов в них. поэтому пока не знаю, стоит добавлять ее в статью или нет.
пусть пока повисит тут. потом, возможно, добавлю. возможно в новый раздел:) |
|
+3
и все таки не могу найти что почитать на эту тему оО только разве что порешать.
самому что ли сделать доброе дело - накатать статью :D (а если потом ее кто нибудь переведет на английский - будет совсем замечательно) |
|
+3
нашел что то отдаленно напоминающее
http://informatics.mccme.ru/moodle/mod/statements/view3.php?id=477&chapterid=77 и разбор: http://informatics.mccme.ru/moodle/mod/book/view.php?id=489 а вообще весьма странно что подобные вещи плохо в инете находятся... или я плохо ищу)) |