| Show all threads Hide all threads Show all messages Hide all messages |
| Problem 1548 "Sakura and Statistics" has been rejudged | Problemset Maintainer | 1548. Sakura and Statistics | 27 May 2016 00:03 | 8 |
A bunch of new tests have been added. 33 of 38 authors lost their AC. A little hint: this problem do has a polynomial solution, and it's not so tricky as you may think. Edited by author 28.01.2016 15:20 spam random @ pray Didn't really expect it to work, especially after such a dramatic rejudge. And i didn't even get to use sorts of «clever» random with GA and mutating solutions. Apparently, most of my WAs were because of inappropriate process of building candidate rectangles, or so i believe... Also, here's a test that helped me, though quite likely it won't be too helpful for anyone else: 7 5 10001 11011 11111 11111 11110 11010 10010 --- 5 1 1 7 1 2 1 6 2 3 1 5 4 2 4 7 4 1 5 4 5 spam random @ pray The hint is clear: there is deterministic polynomial algorithm (~O(s^2)). Some useful tests (for that algorithm): 4 9 010000010 111010111 101111101 000101000 9 --------- 4 4 1100 1110 1111 0111 3 ---- 4 4 1100 1110 0111 0010 3 ---- 5 5 11100 11110 11111 01111 00111 3 ----- 4 3 001 111 011 010 3 --- 4 3 010 111 011 001 3 --- 4 4 0010 1110 0111 0101 4 ---- 4 4 0101 1111 1110 0010 4 ---- 4 3 011 010 110 100 3 --- Oh, good job, and thanks for the tests~ I do have a certain algo in mind actually, but i'm afraid i'll be too lazy to try and code it yet — not until some test that breaks my program is added, haha. Well, and here's another test case then, simple but could be useful. I had a bunch of WAs on 3 and 4 initially; i was building candidate rectangles by expanding them from corners. But then i realized there can be H-like cases, and that horizontal row isn't supported by any corners. 3 5 10001 11111 10001 I do have a certain algo in mind actually, but i'm afraid i'll be too lazy to try and code it yet — not until some test that breaks my program is added, haha. Your smart randomized brute force approach is incredible at my mind. I sure eventually there will be Sakura v2 (something like N=10000 (nonsensible) and M=500) and optimized O(s^2) algorithm became unavoidable. Edited by author 27.05.2016 06:42Edit: affirmative, remove it~ Edited by author 27.05.2016 00:09 Roger that. Removed. Edited by author 27.05.2016 00:11 |
| Just for interest | IlushaMax | 2066. Simple Expression | 25 May 2016 18:45 | 3 |
[code deleted] This code Accepted so A can be 0 or 1; B can be 0 or 1; C can be 0 or 1 in tests. But if we will see on combinatons then there are only 4 combinations (if a<=b<=c) and there are 8 tests as min. The paradox Edited by author 14.03.2016 01:18 Edited by moderator 24.11.2019 13:45 Please do not writeln your code there. > This code Accepted so So no run-time checks if a, b, c are in [0-1] interval. Example: [code deleted] Edited by author 25.05.2016 18:45 Edited by moderator 24.11.2019 13:45 |
| i got Ac use 0.02s | ruwelcome | 1118. Nontrivial Numbers | 25 May 2016 14:39 | 5 |
[code deleted] Edited by moderator 19.11.2019 23:41 nuuu.. che skazat nu krasavchik. thanks you , my pro is TLE :) |
| Some tips (got AC using 0.031s) | hebzxl | 1118. Nontrivial Numbers | 25 May 2016 14:37 | 4 |
First, triviality of 1 is 0. Second, we can judge number i from 2 to 1000000, if i is a prime number, then prime[i] is true. Third, we traversal i from b to a, because if j>i and prime[j]==true, prime[i]==true, we can get 1/j<1/i. if we get prime[i]==true,just output it and break. if we can not get such a number, calculate triviality of i and output the minimum. Thus, we can get AC with a little time spended,but larger memory. My English is poor, if you cannot understand me, I would say sorry for it.^__^ your english are good) i got it. may be i got it because my solution is similar yours=) Your english good enouth to speak with Russians) |
| Why compilation ERROR?!?!?!?!? WTF?!?!?!? | Ivan Metelev | 1964. Chinese Dialects | 25 May 2016 11:30 | 3 |
var a,i,b,n,k: int64; begin readln(n,k); for i:=1 to k do begin read(a); b:=b+a; end; writeln(b-n); end. In the "For" can not be used "int64" |
| Hint | Nivranshu | 2000. Grand Theft Array V | 24 May 2016 14:45 | 1 |
Hint Nivranshu 24 May 2016 14:45 To play optimally, both players would first move towards each other and then from the point of their intersection they will take all the numbers from that point to their nearest boundaries. Let Player 1 start from X and Player 2 start from Y. Then, if (X < Y), player 1 will take all the numbers from A[1] to A[X] and player 2 will take all the numbers from A[Y] to A[N] and also player 1 will take the numbers from A[X] to A[(X+Y)/2] and player 2 will take the numbers from A[(X+Y)/2+1] to A[Y]. if (X > Y) same as above but now player 1 will work from X to N and player 2 will work from 1 to Y. if (X == Y), calculate the sum from A[1] to A[X-1] and another sum from A[X+1] to A[N], add A[X] to the greater sum and give it to player 1. |
| Java. Runtime error on #4 test. Why | Arderun | 1100. Final Standings | 24 May 2016 14:31 | 2 |
here is my code import java.io.PrintWriter; import java.util.*; public class Problem1100 { public static class Busket extends LinkedList<Long>{} public static void main(String[] args) { Scanner in = new Scanner(System.in); PrintWriter out = new PrintWriter(System.out); int times = in.nextInt(); Busket[] list = new Busket[100]; long id =0; int score =0; for(int i =0;i<times;i++){ id = in.nextLong(); score = in.nextInt(); boolean insert=false; if(list[score]==null){ Busket busket = new Busket(); busket.add(id); list[score]=busket; } else{ list[score].add(id); } } StringBuffer result = new StringBuffer(); for(int i = list.length-1;i>=0; i--){ Busket busket =list[i]; if(busket!=null) for(Long mId: busket) { result.append(mId); result.append(" "); result.append(i); result.append("\n"); } } out.println(result.toString()); out.flush(); } } Edited by author 24.05.2016 13:57 Edited by author 24.05.2016 14:01 Edited by author 24.05.2016 14:09 Edited by author 24.05.2016 14:11 new Busket[100] means indices 0..99. Use [101] for 0..100 indices. Edited by author 24.05.2016 14:33 |
| Here's a hint | jk_qq | 1690. Army of Mages | 24 May 2016 02:49 | 2 |
This problem is very easy, try to solve it when 4 * (n-1) + 1 points are given. Another hint: imagine if you got n points and you could cheat and make them all respect each other by stretching or compressing the coordinate grid (while keeping the points static); what would be the simplest way to transform the grid? In this problem you can't cheat like that, but on the other hand you only need to have n/5 points work together. |
| Why WA1? | double | 1659. Regular Triangles | 23 May 2016 22:03 | 3 |
Can somebody give some tests? Thank you.. input 0 30 -25.9807621135 -15 25.9807621135 -15 output -8.2902573694809689e-012 -4.7855053253442748e-012 8.0829037686437069 13.999999999999361 16.165807537287968 -3.1885605267234496e-013 -1.6580514738954005e-011 -29.999999999980858 -25.980762113541445 15.000000000004786 25.980762113533153 15.000000000019146 input 0 0 5 8.6602540378443864676372317075294 10 0 output 5 2.8867513459481291 3.9106836025229588 0.99999999999999989 6.0893163974770417 0.99999999999999989 10 5.7735026918962582 0 5.7735026918962582 5 -2.8867513459481291 WA1 could also be too low output precision! |
| Fast reading | Aisultan Kali | 2040. Palindromes and Super Abilities 2 | 23 May 2016 20:14 | 2 |
If you have TLE on 9 and you are using Palindomic tree, You should write cin/cout with "ios_base::sync_with_stdio (false);" instead of scanf/printf cin/cout with "ios_base::sync_with_stdio (false);" got TLE on 9 for me. But these lines are faster: scanf("%s", input); ..... puts(answer); where input and answer are char arrays. |
| WA#3 | ~ SiriuS ~ | 1602. Elevator | 23 May 2016 14:06 | 4 |
WA#3 ~ SiriuS ~ 13 Mar 2014 15:47 UP! Can someone explain why it happened? import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Lift { public static final float LIFT_DELAY = 15; public static final float PETYA_DELAY = 5; public static void main(String[] args) throws IOException { BufferedReader reader = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(reader.readLine()); float petyaFloor = Float.parseFloat(st.nextToken()); float liftFloor = Float.parseFloat(st.nextToken()); float petyaSpeed = Float.parseFloat(st.nextToken()); float liftSpeed = Float.parseFloat(st.nextToken()); float timeByFootToTheFirstFloor = ((petyaFloor - 1) * petyaSpeed); //время, если идти до 1го этажа пешком float firstLiftDescentTime = ((liftFloor - 1) * liftSpeed) + LIFT_DELAY; //время, затраченное лифтом при спуске и простое на 1м этаже Float numOfFloorToGoByFoot = firstLiftDescentTime / petyaSpeed; //количество этажей, которые может успеть пройти Петя за время спуска лифта int numOfFloors = numOfFloorToGoByFoot.intValue(); //см. предыдущее Float numOfSeekingFloor = petyaFloor - numOfFloors; //искомый этаж float timeLiftWithPetya = (((numOfSearchingFloor - 1) * liftSpeed) * 2) + firstLiftDescentTime + PETYA_DELAY; //время на спуск, подъём к Пете на новый этаж и спуск с ним до 1го этажа if (timeByFootToTheFirstFloor < timeLiftWithPetya) { System.out.println("1"); } else if (timeByFootToTheFirstFloor == timeLiftWithPetya) { String s = numOfSearchingFloor.longValue() + ""; System.out.println(s); } else { String s = numOfSearchingFloor.longValue() + ""; System.out.println(s); } } } Re: WA#3 Oleg Baskakov 23 May 2016 13:38 50 49 0.99 0.28 Answer 21, yours 22. I've rounded up this float, now I get the same answer as you, but it still gives me WA#3 :( Could you please give me one more hint? Edited by author 23.05.2016 14:07 |
| If you have WA#8 | Izaron | 1438. Time Limit Exceeded | 22 May 2016 14:24 | 1 |
Change while (getline(cin, s)) { //... } to while (getline(cin, s)) { if (s == "") continue; //... } Test case: goto Main END: end MAIN: print 1 if 1 == 2 goto end print 2 if 1 == 2 goto end Edited by author 22.05.2016 14:25 |
| to admins | Vladimir Leskov | 1269. Obscene Words Filter | 21 May 2016 21:31 | 2 |
What is real TL? In statements it is 0.5s, but in solutions rating there are solutions which passed with time bigger than 0.5s. For some tasks, they had a bigger time limit before, but after it changed, old solutions might have not been rejudged for whatever reasons. |
| Golang 1.3: Extremely Slow fmt.Scanf | Linh Tran Tuan | 1004. Sightseeing Trip | 20 May 2016 21:26 | 1 |
!!Please be aware of fmt.Scanf poor performance!! I did everything to test it on Timus and feel so sorry for it. My code logic is ok except this! It took a day to figure out. I got AC with FreePascal before, and now Golang. So my advice is: read all input first using bufio and ioutil like this: input = bufio.NewReader(os.Stdin) output = bufio.NewWriter(os.Stdout) _wholeText, _ := ioutil.ReadAll(input) numbers := strings.Fields(string(_wholeText)) |
| How to DP without Bitmark | yeguzi | 1152. False Mirrors | 20 May 2016 13:42 | 1 |
I solved this problem by used recursion without DP. I'm trying to find a solution using DP, I found a public solution using DP + Bitmark, but it's hard to me to understand. How can I solve this problem using DP without Bitmark??? |
| little hint | 🕴 | 1226. esreveR redrO | 17 May 2016 18:44 | 3 |
All symbols are important, not "only printable". Pay attention to EOL, EOF, and symbols with codes below 32. what is EOL, EOF symbols??????? "end of line" (ascii 13 and 10) and "end of file" |
| Why WA?----------ural 1226 | + Calculous + | 1226. esreveR redrO | 17 May 2016 17:41 | 3 |
here is my code: I don't know wht's the error ,anyone help me? Const u=['a'..'z']+['A'..'Z']; Var s:string; ch:char; i:integer; Begin read(ch); while not eof do begin s:=''; while (ch in u) and (ord(ch)<>26) do begin s:=s+ch; read(ch); end; for i:=length(s) downto 1 do write(s[i]); while (not (ch in u)) and (ord(ch)<>26) do begin write(ch); read(ch); end; end; End. check whether you output EOF. If you output it you will get WA. I got really angry when I understood that my program didn't work, because I print EOF!!!! |
| why this is WA? please hepl | blackhole | 1226. esreveR redrO | 15 May 2016 23:55 | 1 |
#include<iostream> #include<algorithm> #include<string> using namespace std; int main() { string text; while(getline(cin,text)) { string s=""; for(int i=0;i<text.size();i++) if(('a'<=text[i]&&text[i]<='z') ||('A'<=text[i]&&text[i]<='Z')) s.push_back(text[i]); else { reverse(s.begin(),s.end()); cout<<s; s=""; cout<<text[i]; } cout<<endl; } //system("pause"); return 0; } |
| WA 3 (question) | Combatcook [YarSU] 🐸 | 1488. ACM Poker | 15 May 2016 15:42 | 1 |
Can anybody give some useful tests to pass test 3? And what about that situation: there are two the same cards in Dima's sleeve and there is the same card in Dima's or Sasha's set? For example: AC QH 10H JC KC 4D AC AC Is that possible? UPD: as I understood, yes... though doesn't matter, AC now. Edited by author 15.05.2016 21:18 |
| Be careful that L>=2 | teoy | 1023. Buttons | 14 May 2016 04:40 | 3 |
I got a WA because I think L can be 1 thnx man .. that should help 5 years later, same trap grabbing me :( |