Common BoardI got WA#19 too! Any tricky test here? test 19 is like this 2 1 1 101 101 2 1 Your answer is probably 0 The right one is 1 Thank you, that was really helpful! Whoever made this problem, thanks a lot! Seeing group theory applied in cp felt pretty cool. Alos learnt a lot thanks to this problem I believe I am having precision errors when calculating the solution. I changed from doubles to long doubles and got one more test case, so I believe my solution is correct but not precise enough. Any tips to resolve this? Never mind, there was simplification in the calculations and then I just hard-coded printed out the decimals. This problem is just cancer Yes Some tests: a = 1 ans = 3.666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666667 a = 1.5 ans = 5.666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666667 a = 666 ans = 2663.66666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666674 a = 1000000000000000000 ans = 3999999999999999999.666666666666666666666666666666666666666666666666666666666666666333333333 Edited by author 03.06.2019 20:30 have no ideas. i've runned my random test generator and my program passed over 1000 tests, but wa. help, please. This hand-made test helped me with WA#16: 5 3 1 2 -2 4 3 2 4 2 -1 The possible answer is: Possible 0 1 3 0 2 Good luck. Глащенко Никита, thank you very much! Really useful test! can anybody help me with this problem? can somebody tell what kind of test is it Check array sizes. i have already checked. all right. maximum number of participants is 300. [code deleted] Edited by moderator 19.11.2019 23:09 Maybe you found the error, but i got stuck on this problem and tried your solution. I hoped to find the problem of my submission. When there are 300 different names without Isenbaev, your program added Isenbaev with number 301 and crashes because of the array index > 300 setting array to [1..301] did the trick and AC thank you! your reply help me a lot! thank you, you saved my day 1) Maybe, you are reading long long variable with this command : scanf("%d",&arr[i]); It is not right. You should do, for example, it with next command scanf("%I64d",&arr[i]); 2) Maybe, you were confused by statement. You have to choose such two points so line that passing through this points has maximal absolute value of inclination, not just inclination. 3) Maybe, you are doing something like this : for ( int i = 1 ; i <= n ; ++i ) { long long d = abs2(arr[i+1] - arr[i]); if ( d > x ) { x = d; m1 = i; } } There is a mistake in first line. Right way is for ( int i = 1 ; i < n ; ++i ) { It was my biggest mistake, because the problem itself is so simple. Thannnnnnnnnnnnnnnnnk youuuuuuuuuuuuuu verrrrrrrrrrrrry mucccccccccccccch! Thannnnnnnnnnnnnnnnnk youuuuuuuuuuuuuu verrrrrrrrrrrrry mucccccccccccccch! Thanks a lot! The definition of inclination is ambiguous in the problem statement. Thanks a lot! I have ignored "absolute value" too. Thannnnnnnnnnnnnnnnnk youuuuuuuuuuuuuu verrrrrrrrrrrrry mucccccccccccccch! Thannnnnnnnnnnnnnnnnk youuuuuuuuuuuuuu verrrrrrrrrrrrry mucccccccccccccch! Problem statement says "His friends write numbers from 1 to N on cards", but it doesn't mention that these numbers should be distinct. Yet, it seems like the problem only accepts solutions in which the numbers are distinct (i.e. the numbers on the N cards are a permutation of [1..N]). Since you're able to download it, you can actually decompile it and submit the code to get accepted. There's a Thread.Sleep(3000) in there that you'll need to comment out. The cases when all times are less than 6 seconds are neglected. So the cost of each plan should be zero as all calling will be free but adding the basic plan to the cost leads to AC. puts gets.split(' ').sum { |s| s.to_i } а вот так ок: puts gets.split(' ').map { |s| s.to_i }.inject(0) {|sum,x| sum + x } что не так с с sum? Edited by author 22.05.2019 11:43 Edited by author 29.05.2019 02:44 Any hints for solution? I am completely stuck at TLE. So, we can decompose like this any connected graph G = (V, E), |E| = 2k, k in Z+? This is lovely, this is nice (I proved it using induction, I'm proud of myself, yay!). I came up to this idea, but failed to proof. It is easy to solve this problem by using such recursive formula (k+1)P_k(N)=(N+1)^(k+1)-1-sum_(l=0)^(k-1) C_(k+1)^l P_l(N), where P_k(N) is a sum of powers k from 1 up to N, C_k^l is a binomial coefficient. I assume that P_0(N)=N. You can check this formula by summing up from 1 to N following identities (n+1)^k-n^k=sum_(l=0)^(k-1) C_k^l n^l. However, P_k(x) has non-integer coefficients, so it is better to introduce polynomials Q_k(x) by formula Q_k(x)=(k+1)!P_k(x). It can be proven by induction based on recursive formula above that Q(x) has integer coefficients!!! So, use BigIntegers in Java, otherwise you would have overflow. Good luck! Edited by author 08.05.2017 19:44 Edited by author 08.05.2017 19:44 You can make a system of linear equations with k+2 variables and equations, which would look like: A_0 * 1^0 + A_1 * 1^1 + ... + A_(k+2) * 1^(k+2) = 1^k A_0 * 2^0 + A_1 * 2^1 + ... + A_(k+2) * 2^(k+2) = 2^k ... A_0 * (k+2)^0 + A_1 * (k+2)^1 + ... + A_(k+2) * (k+2)^(k+2) = (k+2)^k So, you only need to find A_i coefficients using Gaussion elimination. n^3 is suitable for which n<=200 but pay attention to the collinear problem Edited by author 17.05.2019 14:43 #include <stdio.h> int main(){ int n; scanf("%d", &n); if (n == 2) { printf("10"); return 0; } if (n == 4) { printf("670"); return 0; } if (n == 6) { printf("55252"); return 0; } printf("4816030"); return 0; } Here is nothing interesting! It's cheating solution. You precalc all variants and nothing else. I don't think, that this solution is cheating, but it also isn't interesting. Just a simple problem.) It is easy to understand why it works but how did you calculate the numbers for 4, 6, 8? With a calculator?!! In Russian this solution call "Частный случай" hmm... [:||||:] "Частный случай" you are right! Every one has a chance to say some thing in mother language...i also saying... এতে ইজি কিছহু নাই। সব ই কথিন। Chinese: 卑鄙啊 oho~I found a partner, Chinese man বুকে আসেন ভাই :D @shahed adnan Edited by author 04.05.2019 21:05 Edited by author 04.05.2019 21:05 This code works but that's not real ans. Edited by author 16.05.2019 12:10 Well he wrote a programm to calculate the answers first, so this is a solution. And due to the performace it is the very good solution. So stop winning and be smart guy. Thanks for giving test data!! \*^_^*/ I thought my solution is quite "brute", are there any other solutions? And I have to say it is a really good problem for sufficient samples and a clear statement. And where is your solution? I cant ivent any tests that my solution will fail, but I have WA1! Can any body help... Give me some test! Plz... example tests 4 0110 0011 0001 1000 4 1 4 2 3 3 2 4 1 my output: No No No No 3 010 000 100 3 1 3 3 1 2 3 out: No Yes No Is it correct? Give some more tests! You should print "YES", but not "Yes"... WA 2 CODE: program china; var t:char; i,j,k:integer; a:array[1..100,1..100] of boolean; b:array[1..100] of integer; chk:array[1..100] of boolean; x,y,q,n,m:integer; procedure solve(k:integer); var i:integer; begin for i:=1 to n do begin if a[k,i] then begin if not chk[i] then begin chk[i]:=true; solve(i); end; end; end; end; begin readln(n); for i:=1 to n do begin for j:=1 to n do begin read(t); if t='0' then a[i,j]:=false else a[i,j]:=true; end; readln; end; for i:=1 to n do begin fillchar(chk,n,false); solve(i); for j:=1 to n do begin if chk[j] then b[i]:=b[i]+1; end; end; readln(q); for i:=1 to q do begin readln(x,y); if b[x]>b[y] then writeln('YES') else writeln('No'); end; end. may be this test will help you: 4 0010 0001 0100 0000 4 1 2 1 4 4 1 4 3 answer: YES YES YES No Why answer for 1 4 and 4 1 YES and what is the anwer for 4 0100 0000 0001 0000 7 1 2 2 1 3 4 4 3 3 1 1 3 3 2 Why answer for 1 4 and 4 1 YES Because you should print "No" only if nodex x and y have common predecessor. In other cases you should print "YES". My answer for your test: YES YES YES YES YES YES YES Thank you, your answer helped me mutch! Because you should print "No" only if nodex x and y have common predecessor. In other cases you should print "YES". Where this is written in the statement? Why can't I solve the problem this way: 1. Make transitive closure of the given graph (matrix A)using Floyd. 2. For every request (pair i j) print "YES" if A[i][j] = 1 otherwise print "No". Because you should print "No" only if nodex x and y have common predecessor. In other cases you should print "YES". Where this is written in the statement? Here: "In this case we say that the team A is stronger than the teams B and C (more formally, A is stronger than B if A has beaten B or if A has beaten a team C which is stronger than B)." Edited by author 18.10.2006 23:11 Edited by author 18.10.2006 23:114 1 anwer is No, because 1 better than 3, 3 better than 2, 2 better than 4 => 1 better than 4 |
|