Common Boardthe output part states that: "The only line of the output must contain the minimal sum followed by the optimal route (one of possible routes with minimal sum)", but I got wrong answer! why? my output for sample input is: 5 e2 e1 d1 d2 e2 e3 I think it's also right. um I think so Yes Right! my AC program outputs "5 e2 e1 d1 d2 e2 e" for sample test :) 5 e2 e1 d1 d2 d3 e3 is another correct answer for the sample input. double res = ...; cout << setprecision(6) << fixed << res; program idiots; var n,i,h:integer; a: array [1..1000] of integer; begin readln(n); for i:=1 to n do read(a[i]); h:=1; for i:=1 to n do begin if a[i]=a[i+1] then h:=h+1; if a[i]<> a[i+1] then write(h,' ',a[i],' '); if a[i]<> a[i+1] then h:=1; end; end. but, I don't understood! for i:=1 to n do begin if a[i]=a[i+1] then h:=h+1; if a[i]<> a[i+1] then write(h,' ',a[i],' '); if a[i]<> a[i+1] then h:=1; end; You must get error in this stroke if a[i]=a[i+1] then h:=h+1; because your for loop is going untill n this must give Indexout of range exception isn't? Nope, its neither c++ nor Java. It`s Pascal. Here you can do a lot of forbidden things without getting runtime error or Exception How to use dynamic programming to solve this problem? I used fibonacci. As far as I understand, this problem is about combinations and not about fibonacci. If there was only the first condition, then for any N we have only 2 possibilities to create the flag. That is, f(1) = 2, f(2) = 2, f(3) = 2, f(4) = 2, ..., f(N) = 2; This is true, because the choice of the first stripe determines the rest of the flag automatically. If you choose the first stripe to be white-colored then you are destined to choose the red stripe to be the second one. And vice versa. Don't make my words a HOLY WISDOM - think about it till you can feel it yourself. Don't read next, until you fully and completely get it. The second condition is here to complicate your life. It doesn't do anything to our function f(x) if x equals to 1 or 2. That is, f(1) and f(2) are still equal to 2. (By the way, I've just noticed that I've pulled the function from under the pillow. Well, in my mind this function returns the amount of different flags that can be created if you need to make it from x stripes. Ok, now we're moving on...) But it allows us to INSERT the blue stripe between the two: white and red stripes. This concept of INSERTION is really the key here. Think about it. If you were supposed to gain anything intellectually from solving this task at all, I bet, it was this very concept. If we have some sequence of 2-colored flag: WRWRWRWRWRWRWR (White and Red), and this sequence contains all the N stripes that we need, then we really don't have any place to INSERT our blue stipe. You think, ok, that's fair, and remove one of the stipes (e.g. the left-most). Now you have the place for your blue stripe ... and you can insert it in many ways: wBrwrwrwrwr or wrBwrwrwrwr or wrwBrwrwrwr ... well, you get the point :) This way, by removing one of the stripes you have created X COMBINATIONS. This word is also important, that is why it is all upper-case :) If you remove ONE MORE stripe (think about removing as n - 1 or better n--), you now have to INSERT 2 blue stripes somewhere in the sequence wrwrwrwrwrwr... E.g. wBrBwrwrwrwrwrwr, or wBrwrwrwrwrwrwBr. Now there should be more COMBINATIONS than in the previous case (figure out yourself, how many :) ). The last point I want to make is that you have to know your limits. That is, you have to understand when to stop removing stipes from the flag and stop INSERTING blue stripes in it. When you get to this point (keeping in mind all the previous points), you will figure this out by yourself easily... Edited by author 20.08.2015 02:16 Edited by author 20.08.2015 02:18 Edited by author 20.08.2015 02:23 Edited by author 20.08.2015 02:23 Edited by author 20.08.2015 02:25 Edited by author 20.08.2015 02:26 Edited by author 20.08.2015 02:27 Edited by author 20.08.2015 02:27 Edited by author 15.10.2016 20:15 Edited by author 15.10.2016 20:16 Edited by author 15.10.2016 20:20 Edited by author 15.10.2016 20:21 Edited by author 15.10.2016 20:21 This is really extremely helpful in reasoning about the problem, thank you Егору зачет! За крутое решение и за знание англ) Please, give me some tests! #include <stdio.h> #include <stdlib.h> int main(int argc, char *argv[]) { int a,k=-1,fact=1,term=1,i=0; char c; scanf("%d",&a); getchar(); do{ c=getchar(); k++; } while(c==33); if(k>a) fact=-1; while(fact>0){ term*=fact; fact=(a-i*k); i++; }
if(k<=a) printf("%d",term); system("PAUSE"); return 0; } Edited by author 01.07.2012 19:03 #include <stdio.h> #include <stdlib.h> int main(int argc, char *argv[]) { int a,k=-1,fact=1,term=1,i=0; char c; scanf("%d",&a); getchar(); do{ c=getchar(); k++; } while(c==33); if(k>a) fact=-1; while(fact>0){ term*=fact; fact=(a-i*k); i++; } if(k<=a) printf("%d",term); system("PAUSE"); return 0; } I always get WA on test 4,who can give me the testdata of test4.Help me!Thank you. Triviality(1)=0 Thank's for help! You're completely right! AC now! Thanks.I got AC now. Of course I have same bugs. AC now I also have the same mistake.thanx a lot. Thank you very much!!!!!!! It is a very good advice! Thank you for your advice. I've gotten AC now.I wrote "1" if i=1. а как выглядит второе число? ведь тест - 2 числа, через пробел. Can you tell how look test4? the first is one, and the second is ..? Triviality(1) = 1 Triviality(1)=0 Edited by author 17.09.2015 23:28 Edited by author 17.09.2015 23:28I keep getting WA2, but none of the threads posted here seem to help me: every example i found worked on my program, and i just can't see what's wrong with it. Can someone please tell me if they see anything that doesn't work within my program? Thank you in advance. #define DM 8101 #define DN 901 #include <iostream> #include <set> #include <queue> using namespace std; int n, v, vp, s, sp, cf[DN][DM], dp[DN][DM]; multiset <int> ord;//ordering the elements queue <int> q;//rebuild void formare(int nrc, int car, int sum, int ptr)//no of digits, digit, sum, sumof squares { if (nrc > 100 || (cf[sum][ptr] && cf[sum][ptr] <= nrc)) return; cf[sum][ptr] = nrc; dp[sum][ptr] = car; for (int i = 9; i >= 1; --i) formare(nrc + 1, i, sum + i, ptr + i*i); } void realc(int s, int sp) { if (!s || !sp || !dp[s][sp]) return; q.push(dp[s][sp]); v+=dp[s][sp]; vp+=dp[s][sp]*dp[s][sp]; realc(s - dp[s][sp], sp - dp[s][sp]*dp[s][sp]); } int main() { cin >> n; for (int i = 9; i >= 1; --i) formare(1, i, i, i*i); cf[0][0] = 1; dp[0][0] = 0; while (n--) { cin >> s >> sp; if (s > 900 || sp > 8100) cout << "No solution\n"; else if (s == 0 && sp == 0) cout << "0\n"; else { realc(s, sp); if (q.size() <= 100) { while (!q.empty()) { if (v == s && vp == sp) ord.insert(q.front()); q.pop(); } for (auto i:ord) cout << i; ord.clear(); if (v != s || vp != sp) cout << "No solution"; cout << '\n'; } else { cout << "No solution\n"; while (!q.empty()) q.pop(); } } v = vp = 0; } return 0; } Nevermind, apparently I was calculating the number the wrong way, I found the mistake. What is the test 19? Help please! Timus Sistem have: Test1: n = 4 Test2: n = 2 Test3: n = 3 Right answers for n = 15 1 14 3 12 5 10 7 8 9 6 11 4 13 2 15 1 3 5 7 9 11 13 15 14 12 10 8 6 4 2 n = 16 1 15 3 13 5 11 7 9 8 10 6 12 4 14 2 16 1 3 5 7 9 11 13 15 16 14 12 10 8 6 4 2 Enjoy by problem) Oh. My. God. JEBUS! I ACed it! Just use suffix array + Kasai and it will work out just fine. Trust me :) But also here is what I collected about test 30 : * Size of the string = 250000. * All letters of English alphabet are being used. * If we divide the string into heterogeneous and homogeneous regions, then the latter forms a majority. Moreover, longest homogeneous region = 396 and heterogeneous = 6. * The amount of divergent adjacent characters is between 5000 and 10000. Hope it helps :3 I submitted some algo which on my computer gives correct result for sample input given in problem statement and I got WA in test #1. Then I tried this code: public class Problem_1285 { public static void main(String[] args) { System.out.println("1.00"); } } ...and got the same WA #1. What's going on??? Seems like test #1 is not the sample test Seems like test #1 is not the sample test It is often the case. There is a restiction for X and Y values: −10000.0 ≤ x, y ≤ 10000.0. Does .0 (sigle zero) means that only one digit after the decimal point is possible? Or if there any restriction for number of digits after the decimal point? You can check it on your own... Throw a division by zero or reach a memory limit or whatever, if you meet a number with more than one digit. If you still reach the same test, then there's no such numbers. Thanks. The 6th test have numbers with 8 digits after decimal point. In test #13 there are numbers with 21 digits after decimal point In test #13 there are numbers with 21 digits after decimal point It bothers you? Do you want to talk about it? This is a test case with only 6 digits after decimal point: 2 999.969732 999.984915 1414.181493 0 1 0 0 And it needs about 20 digitd precision to resolve it corectly, Doubles can fail on such tests. Using 21 digits it is possible to create tests which can be solved correctly using long arithmetic only. Does this problem requires to compare distances with no error, or there is an accepted tollerance? Bad news if it is so. I have figured out that 1e-10 difference bewtween dx * dx + dy * dy is accepted Good job, and thanks for the valuable info! You used Voronoi? I've got accepted with O(N * M) solution. But in my main idea i use voronoi and have WA17 - there are some precision errors in voronoi building, but i hope that i can fix it ) I've got accepted with O(N * M) solution. O(N * M) for 1.762 seconds??? Is it Voronoi with following "modification": instead of binary tree you use just a linked list? N sweep line motions * M increemnts of iterator during binary search in linked list (but still log(M) parabolas' intersections)? Or something else? But in my main idea i use voronoi and have WA17 - there are some precision errors in voronoi building, but i hope that i can fix it ) What is the cause of WA? Symmetic cases (more then 3 sites on vertex?)? Is it true, that there are four cockroaches maximum may be close to each sweet piece? 1) 1.762 - is voronoi solution. O(N * M) works more than 3 seconds. There were smome implementation issues. My O(N * M) just check eahch to each with no precalcs. 2) definitely no. points (-5, 0) (-4, -3) (-3, -4) (0, -5) (3, -4) (4, -3) (4 3) (3 4) (0 5) (-3 4) (-4 3) have the same distance equal to 5 from the point (0, 0). Using a floating point values there are possible thousands of cockroaches close to some sweete pieces Edited by author 04.06.2016 15:25 If I use general precision arithmetic and algebraic numbers, then I get WA even being correct. 1) 1.762 - is voronoi solution. Can you say is the following algorithm right?: 1.) Firstly lexicographically sort all the cockroaches and all the sweet pieces. 2.) In first pass, make Voronoi for cockroaches using Fortune algorithm. Voronoi data struct is graph of vertices and edges. For each edge there are pointer to "left" site and pointer to "right" site. For each vertex there is a set of pointers to edges, which supported by this vertex. 3.) Vertices are produced by algorithm in previous step, are already sorted lexicographically (or sort them otherwise). 4.) In second pass, events are sweepings of vertices and sweepings of sweet pieces. For each edge there is bounding box. We can track appearing and lefting of bounding boxes for each edge and infer the belonging of each sweet pieces for each cell. I am very doubted with 4.). 1) 1.762 - is voronoi solution. Another possible algorithm is "inline" version of Fortune's algorithm: during sweep line motion if parabolic arc disappears, then we have a pair of edges, that meets in corresponding new vertex. Check all sweeped sweet pieces for belonging to cone, supported by this two edges. I some sweet piece is inside (or on the edge (2 cockroaches), or matches the vertex (greater then 2 number of cockroaches are closest)), then move it from list of already sweeped sweet pieces to result. 1) I think that both of this algos are incorrect. Bounding boxes of the edges is not good idea because some sweets can be out of any bounding box 2) Check all sweets when parabolic arc disappears needs to much time. There could be the sitation when all of the sweets are located in the same voronoi cell, and is is located in such place the there are a lot of cells before PS I don't that it is good idea to discuss here a correct solution. We can discuss it out of timus forum for example in vk.com (my name is Александр Пак) There are a plenty of your namesake in vk.com. It is almost impossible to distinct you from the others. to avoid decreasing precision error we can find delaunay triangulation of m points and for each n points we can first find which delaunay triangle it is in, compare these three points and its adjcent triangle. at least one of the point with minmum distance in these three triangles, if we find three point of one triangle if equal to minimum distance, continue to find its adjcent triangles. sorry for so many dumplicate post with so fucking network Edited by author 21.10.2016 14:59 to decreasing precision error we can find delaunay triangulation of m points and for each n points we can first find which delaunay triangle it is in, compare these three points and its adjcent triangle. at least one of the point with minmum distance in these three triangles, if we find three point of one triangle if equal to minimum distance, continue to find its adjcent triangles. to decreasing precision error we can find delaunay triangulation of m points and for each n points we can first find which delaunay triangle it is in, compare these three points and its adjcent triangle. at least one of the point with minmum distance in these three triangles, if we find three point of one triangle if equal to minimum distance, continue to find its adjcent triangles. to decreasing precision error we can find delaunay triangulation of m points and for each n points we can first find which delaunay triangle it is in, compare these three points and its adjcent triangle. at least one of the point with minmum distance in these three triangles, if we find three point of one triangle if equal to minimum distance, continue to find its adjcent triangles. I thought about Delanau triangulation. I have nD implementation of Quickhull algo, which can give me triangulation, when applied to projection onto paraboloid. Bit it is not too hard to imagine bad case for BFS on triangulation graph. E.g. well known concentric points. It is the same bad case as for quadtree. Edited by author 10.11.2016 18:12 Does your last solution use this algorithm? NO, my AC sol directly find voronoi diagram but when Location the point, you mustn't find the intersection point of x==x0 instead you should find the nearest Thiessen polygons directly using Euclid distance to sort it.. in a word you should use original point as much as you can to inprove your accuracy btw seems there is some clever k-d tree sol also get AC... Edited by author 20.12.2017 21:58 What do you think, are top 3 solution implemented via Voronoi? I implemented Fortune's ( https://github.com/tomilov/sweepline), but I can't overcome precision errors in case of regular grids and concentric points, even if I use a little cheating: I modify input by rotation on some small angle. Some of points became a points-in-general-positions. Then I use something like this ( http://www.link.cs.cmu.edu/15859-f07/papers/point-location.pdf), but invented by myself - it is much simplier for Voronoi diagram. I interested to talk with you (I will not bother you much), can you give any contact? Edited by author 21.12.2017 19:51you can contact me through 441766573@qq.com my qq is always online... you can contact me through 888888888@qq.com my qq is always online... You can remove the number and add me to your contacts =). import java.math.*; import java.util.*; public class BigNumbers { final int nmax=5005;
public static BigInteger Px[], Py[], z[]; public static int n;
public static boolean Equal(BigInteger x1, BigInteger y1, BigInteger z1, BigInteger x2, BigInteger y2, BigInteger z2) { BigInteger A = (x1.multiply(z2)).subtract(x2.multiply(z1)); BigInteger B = (y1.multiply(z2)).subtract(y2.multiply(z1)); return (A.compareTo(BigInteger.ZERO)==0 && B.compareTo(BigInteger.ZERO)==0); }
public static boolean Less(BigInteger x1, BigInteger y1, BigInteger z1, BigInteger x2, BigInteger y2, BigInteger z2) { if(Equal(x1,y1,z1,x2,y2,z2)) return false;
if(y1.compareTo(BigInteger.ZERO)==0) return x1.compareTo(BigInteger.ZERO)==1; else { if(x1.compareTo(BigInteger.ZERO)==1) { if(x2.compareTo(BigInteger.ZERO)!=1) return true; BigInteger v=(y2.multiply(x1)).subtract(x2.multiply(y1)); return v.compareTo(BigInteger.ZERO)==1; } else { if(x1.compareTo(BigInteger.ZERO)==0) return x2.compareTo(BigInteger.ZERO)==-1; else { BigInteger v=(y2.multiply(x1)).subtract(x2.multiply(y1)); return (x2.compareTo(BigInteger.ZERO)==-1 && v.compareTo(BigInteger.ZERO)==1); } } } }
public static boolean More(BigInteger x1, BigInteger y1, BigInteger z1, BigInteger x2, BigInteger y2, BigInteger z2) { return Less(x2,y2,z2,x1,y1,z1); }
public static void QSort(int L, int R) { int m=(L+R)/2; int i=L; int j=R; while(i<=j) { BigInteger xi,yi,zi,xj,yj,zj,xm,ym,zm;
xm=(Px[m].multiply(z[n-1])).subtract(z[m].multiply(Px[n-1])); ym=(Py[m].multiply(z[n-1])).subtract(z[m].multiply(Py[n-1])); zm=z[m].multiply(z[n-1]);
xi=(Px[i].multiply(z[n-1])).subtract(z[i].multiply(Px[n-1])); yi=(Py[i].multiply(z[n-1])).subtract(z[i].multiply(Py[n-1])); zi=z[i].multiply(z[n-1]);
while(Less(xi,yi,zi,xm,ym,zm)) { i++; if(i<=n) { xi=(Px[i].multiply(z[n-1])).subtract(z[i].multiply(Px[n-1])); yi=(Py[i].multiply(z[n-1])).subtract(z[i].multiply(Py[n-1])); zi=z[i].multiply(z[n-1]); } }
xj=(Px[j].multiply(z[n-1])).subtract(z[j].multiply(Px[n-1])); yj=(Py[j].multiply(z[n-1])).subtract(z[j].multiply(Py[n-1])); zj=z[j].multiply(z[n-1]); while(More(xj,yj,zj,xm,ym,zm)) { j--; if(j>=1) { xj=(Px[j].multiply(z[n-1])).subtract(z[j].multiply(Px[n-1])); yj=(Py[j].multiply(z[n-1])).subtract(z[j].multiply(Py[n-1])); zj=z[j].multiply(z[n-1]); } }
if(i<=j) { BigInteger v; v=Px[i]; Px[i]=Px[j]; Px[j]=v; v=Py[i]; Py[i]=Py[j]; Py[j]=v; v=z[i]; z[i]=z[j]; z[j]=v; i++; j--; } } if(L<j) QSort(L, j); if(i<R) QSort(i, R); }
public static void main(String args[]) { Scanner sc=new Scanner(System.in); n=sc.nextInt();
Px=new BigInteger[n+1]; Py=new BigInteger[n+1]; z=new BigInteger[n+1];
for(int i=1;i<=n;i++) { Long x, y; x=sc.nextLong(); y=sc.nextLong(); Px[i]=BigInteger.valueOf(x); Py[i]=BigInteger.valueOf(y); }
for(int i=1;i<=n-1;i++) { Px[i]=Px[i].subtract(Px[n]); Py[i]=Py[i].subtract(Py[n]); z[i]=(Px[i].multiply(Px[i])).add(Py[i].multiply(Py[i])); }
for(int i=1;i<=n-2;i++) { BigInteger v1=z[n-1].multiply(Py[i]); BigInteger v2=z[i].multiply(Py[n-1]); if(v1.compareTo(v2)==-1) { BigInteger v; v=Px[i]; Px[i]=Px[n-1]; Px[n-1]=v; v=Py[i]; Py[i]=Py[n-1]; Py[n-1]=v; v=z[i]; z[i]=z[n-1]; z[n-1]=v; } }
QSort(1,n-2);
Px[n-1]=Px[n-1].add(Px[n]); Py[n-1]=Py[n-1].add(Py[n]);
int m = (n-1)/2; Px[m]=Px[m].add(Px[n]); Py[m]=Py[m].add(Py[n]);
System.out.println(Px[n-1]+" "+Py[n-1]); System.out.println(Px[m]+" "+Py[m]); System.out.print(Px[n]+" "+Py[n]); } } input test 2 is: 1 1 Edited by author 06.02.2016 22:45 Thanks, mate! Serves me right for being too impatient and not considering the basic corner cases! :-) I just have implemented "Copy on Write" strategy suggested in other tread and it helped me pass through tests #9 and #10 where I got MLE/TLE earlier. But I cannot pass #19. I tried StreamTokenizer suggested by "Getting Stated" page, then I even implemented my own parser without any cheking for input errors just to speed up my solution. But still too slow! There seems nothing can be done about algo itself: rollback/relearn fiddle with one variable, check prints, clone makes new entry in ArrayList<Clone> without actually doing anything. Only learn seems to be doing something: copying ProgramsList if it's needed, clearing abolished programs and adding new one. Not that much to find something excessive to remove. But why it take so much time in test #19? How did 26 genii get their AC with Java? Is there some kind of trick or fundamental improvement to achive better time? I lost my mind searching solution. Please, help! p.s. And sorry for bad English... Update: I removed clearing ArrayList<Integer> in learn command, it waste memory a little and save time a little and made some cosmetic improvements. But still too slow! Edited by author 21.12.2017 04:38 Can anyone help me please? I don't understand what is three prime number? :S My english is not good... Let my try to explane you on example: ************************************** 1274 - not this is not three prime number because 127 - this is 3.-digit prime nubmer , but 274 - this is not 3.-digit prime number... *************************************** 1137 - is this is three prime number because 113 - this is 3.-digit prime number, and 137 - this is 3.-digit prime number *************************************** So every 3 consecutive digits in number X must be 3.-digit prime number... I hope this help... It's not true number is three digits prime number if any three digits are prime "Pasha calls an integer a threeprime number if any three consecutive digits of this integer form a three-digit prime number." So if we write number A as A[1]A[2]...A[n] (A[i] - i-th digit of this number), than whole number A will be 'threeprime' if and only if for each i=1,2..., n-2 number A[i]A[i+1]A[i+2] is prime number. I understand now. Thanks a lot guys. The problem won't be problem anymore :) Edit: Except one more thing? 3 digit number is threeprime only if the number is prime right? Example: 101 is prime number so that means it's also a threeprime number right? Or that's not always right? Edited by author 04.05.2008 06:39 Edited by author 04.05.2008 06:47 |
|