Show all threads Hide all threads Show all messages Hide all messages |
Hint | Vineet Jain | 1098. Questions | 31 Oct 2020 21:23 | 1 |
Hint Vineet Jain 31 Oct 2020 21:23 Very Easy Josephus's problem. Look it on geek for geeks |
Seems that the O(lgn) algorithm is slower than the O(n) algorithm for these test cases. | some_programming_novice | 1098. Questions | 17 Nov 2018 17:57 | 1 |
For the classic Josephus problem, there exists two classic algorithms. The algorithm A has time complexity O(lgn) and comes from <discrete mathematics>. /* Algorithm A */ int solve(int N/*The magic number 1999*/, int m/*length of the text*/) { long long z = 1; while (z < (N - 1LL/*int may overflow here*/) * m + 1) { z = (z * N + N - 2) / (N - 1); } return m * N - z; } The algorithm B is the classic O(n) algorithm. int solve(int N/*The magic number 1999*/, int m/*length of the text*/) { int z = 0; for (int k = 2; k <= m; ++k) { z = (z + N) % k; } return z; } In my submissions, algorithm A costs 0.015s, and algorithm B costs 0.001s. Maybe arithmetic operations for "long long" is a little too slow? |
Wow, O(n^2) int Java got AC | Izaron | 1098. Questions | 20 Aug 2016 13:02 | 1 |
This code in Java: int v = 0; int n = 1998; while (buffer.length() > 1) { v += n; v %= buffer.length(); buffer.deleteCharAt(v); } Got AC in 0.109 time |
IO tips and other | lakerka | 1098. Questions | 3 May 2015 20:43 | 1 |
First of all make sure that you are not reading newlines and carriage return symbols. Input can be read like: char c; int scanfRez; do { scanfRez = scanf("%c", &c); if (scanfRez != EOF && c != '\n' && c != '\r') { chs[chCount++] = c; } }while(scanfRez != EOF); I was getting WA7 with this input reading: char c; int scanfRez; do { scanfRez = scanf("%c", &c); if (c != '\n' && c != '\r') { chs[chCount++] = c; } }while(scanfRez != EOF); If you get WA3 make sure that you are processing sequence correctly with given sequence length > N. For example: let N = 11, input sequence = "abcdefghijkl" (without quotes) then letters should be removed in this order: k 1 j 2 l 3 b 4 e 5 i 6 g 7 h 8 d 9 a 10 c 11 f 12 It does not matter if you put newline at the end of output. |
Stuck at WA#3 | begi | 1098. Questions | 8 Dec 2014 20:13 | 2 |
Can someone provide more tests? I am using scanner.nextLine() to read line.charAt(pos) == '?' to compare in java and also Josephus allgorithm: jos[1] = 1; for (int i = 2; i < max_n; i++) { jos[i] = (jos[i - 1] + 1998) % i + 1; } My code is so small that I don't even know where is the bug Ok, the thing is I misunderstood the problem. You read ALL the input ignoring new lines, and then do the 'process'. I was reading line by line and doing 'process' for each line. Hope it will help the others. |
Orz C++'s effectivity | StarForever | 1098. Questions | 25 Apr 2013 08:40 | 4 |
I just use two lines in my code. pos=(pos+N-1)%question.length(); question.erase(pos,1); and I got AC... though it is a bit slow. But still unbelievable. It is Josephus problem... Change your solution: for(int len = question.length(); len>0; len--) pos = (pos+ N-1)%len; printf("%d", question[pos]); cool. you don't need to delete the character in each loop What does "Orz C++" stand for? |
Test #1 | ძამაანთ [Tbilisi SU] | 1098. Questions | 27 Mar 2013 22:45 | 1 |
Test #1 ძამაანთ [Tbilisi SU] 27 Mar 2013 22:45 For those who are stuck at this point. The filtered (thus 0x0a and 0x0d removed) first testcase is: "a ?" (w/o quotes) |
ATTENTION, JUDGES!! | jedimastex | 1098. Questions | 12 Apr 2012 05:27 | 6 |
I wonder if it's true that the first test matches the sample. My program writes 'Yes' just like in the sample. But it gets WA1 ?? Will anyone answer my question? Many people have such problems because they don't skeep symbols #10 and #13. Send me your code (sk1@hotbox.ru) and I'll try to help you. PS: If you have WA #1 it is not a reason to ask for JUDGES' help. I am not asking for judges' help. I just want to know why my program gets WA. It's really annoying to have WA1 without an obvious reason. Thanks in advance. MB you output some additional adta? In this judge the first test isn't necessarily equal to the first example. Some problems only have few large tests. |
WA3 o_O | MOPDOBOPOT (USU) | 1098. Questions | 12 Sep 2011 00:57 | 1 |
WA3 o_O MOPDOBOPOT (USU) 12 Sep 2011 00:57 I have two different solutions and each of them gives me WA3 :( First - naive, here it is: ----------------------------------- read(s); l:=length(s); n:=1999; if l < n then if n mod l <> 0 then A:=n mod l else A:=l else A:=n; while l <> 1 do begin delete(s,A,1); n1:=n-(l-A); dec(l); if l < n1 then if n1 mod l <> 0 then A:=n1 mod l else A:=l else A:=n1; end; case s[1] of '?': writeln('Yes'); ' ': writeln('No'); else writeln('No comments'); end; readln; end. ----------------------------------- And the next one is recursive solution inspired by Josephus problem formula: ----------------------------------- function Jo(l: longint): longint; begin if l = 1 then Jo:=0 else Jo:=(Jo(l-1)+n) mod l; end; begin read(s); l:=length(s); n:=1999; case s[Jo(l)+1] of '?': writeln('Yes'); ' ': writeln('No'); else writeln('No comments'); end; readln; end. ----------------------------------- Please, help me with some tests information or tell me about my stupid bugs :) Maybe I miss some cases? Edited by author 12.09.2011 00:58 |
Test#7 | 我系花生我最捞 | 1098. Questions | 27 Jan 2011 12:31 | 1 |
Test#7 我系花生我最捞 27 Jan 2011 12:31 i've wa at Test#7 twice. At first,my program outputed "No comments.". Second,my program outputed "NO comments". |
for jury | vahan | 1098. Questions | 22 Nov 2010 23:59 | 1 |
the firdt test is wrong, my AC program gives "No comments" pls fixed that and change statement |
If you use Delphi | Vladislav Ivanishin | 1098. Questions | 29 Jun 2009 05:03 | 1 |
do not forget about {$H+} after debuging ;^) |
I have wa#5 andI can't understand my mystake: | h1ci | 1098. Questions | 3 Dec 2008 21:07 | 1 |
#include <iostream> #include <string> using namespace std; int main() { int n=1999; string s; int pl[100000], br=0, j=0, symb; while(getline(cin,s,'ç')) { for(int i=0; i<s.size(); i++) { if(s[i]=='\n'){ s.erase(i,1);} } symb=0; for(;;) { if(s.size()==1) { if(s[0]=='?'){ cout << "Yes" << endl; return 0;} else if(s[0]==' ') { cout << "No" << endl; return 0;} else { cout << "No comments" << endl; return 0;} } symb=symb+(n-1); symb=symb%s.size(); s.erase(symb,1); } } return 0; } Edited by author 07.03.2009 01:46 Edited by author 07.03.2009 01:46 |
What's the problem with test 8 | LAPI Team | 1098. Questions | 1 Nov 2008 00:37 | 3 |
I solved this problem as a Josephus Problem. Everything is ok as long as test8. I can't unterstand why WA8. If you think it helps I will give you my code in Pascal. In my opinion,there is only one character in test 8... i had WA on test #8, but i found a bug in my solution.. The 8th test contains one character - space (" ", #32) |
It is a Joseph problem.If you have read Concrete Mathematics,you can solve it easily in O(N), | Andrew | 1098. Questions | 6 Oct 2008 21:12 | 3 |
How's that? FE, it seems to me, my solution works for O(logn), where n is the length of text and the base of logarithm is 1999/1998. Igor, it seems wrong because your solution has exactly same asymptotical order. O(ln X/ln(N/(N-1)) = O(ln X/(ln(1+1/N))= O(N*ln X) |
test case 3 hint says 14 characters, tested that there is more than 20 | Neverauskas | 1098. Questions | 10 Sep 2008 11:01 | 2 |
What's wrong with this one i tested dozens of times and #3 always give me WA. Even hint says that question will consist of 14 characters when actually there is more than 20. Test#3 is not a third sample test. Look for a bug in your code. |
Test #7 | Tbilisi SU: Eldar Bogdanov | 1098. Questions | 2 Aug 2008 15:18 | 5 |
Test #7 Tbilisi SU: Eldar Bogdanov 11 Oct 2006 02:39 I've tried to solve this problem using lists and with the Josephus algorithm and both approaches had WA7, it seems I can't read the input properly. I've tried different approaches here, too: 1. while not eof do begin read(s[i]); if (ord(s[i])=13) or (ord(s[i])=10) then dec(i); inc(i); end; 2. repeat readln(ss); for i:=len+1 to len+length(ss) do s[i]:=ss[i-len]; len:=len+length(ss); until eof; And many others, but I always get WA7. What's that test?! Re: Test #7 Tbilisi SU: Eldar Bogdanov 16 Oct 2006 03:21 This input is OK: txt := ''; while not eof do begin read(c); if c in [#10,#13] then continue; txt := txt + c; end; Re: Test #7 Tbilisi SU: Eldar Bogdanov 16 Oct 2006 16:23 Thank you :) I've got accepted, but it turned out that my problem wasn't in reading the input and I realized it only after getting WA7 with your inputting fragment, too. I outputed 'No comment' instead of 'No comments'... :D Edited by author 16.10.2006 16:24 Edited by author 16.10.2006 16:24 The same trouble with you |
Josephus Problem (on russian) | -AlexandeR- (TNU) | 1098. Questions | 1 May 2008 12:22 | 1 |
|
FINALLY ! Got AC | Alexander Gyorev | 1098. Questions | 25 Apr 2008 19:19 | 1 |
Finally made it (party) =P for 0.156 268 KB |
it is too strange | lian lian | 1098. Questions | 26 Dec 2007 22:50 | 1 |
Could anybody tell me how should I read the input in "c"? |