Common Board| Show all threads Hide all threads Show all messages Hide all messages | | accepted | Mikhail | 1206. Sum of Digits of the Sum of Numbers | 16 Jun 2018 15:43 | 2 | ans1 = 0 ans2 = 0 for i in range(1, 10) : for j in range(1, 10) : if i + j < 10 : ans1 += 1 for i in range(0, 10) : for j in range(0, 10) : if i + j < 10 : ans2 += 1 n = int(input()) for i in range (1, n) : ans1 *= ans2 print(ans1) | | Python 3.4 "Time limit exceeded" test№19 What's wrong? | Danya | 1510. Order | 13 Jun 2018 20:51 | 2 | What is the test №19? "" from sys import stdin from collections import Counter def search(): tmp = Counter([int(x) for x in stdin]) return [i for i in tmp.keys() if tmp[i] == max(tmp.values())][0] search() """ Edited by author 22.10.2015 01:31 Maybe replace search() with print(search())? That was a joke, but when I tried to submit this code, i got WA1. The test is ok, but your code is not optimal. Your code calculates max(tmp.values()) every time, and it is a costly operation. And here is my optimized (WA23, because there is another drawback in your solution) version of it: from sys import stdin from collections import Counter def search(): tmp = Counter(map(int, stdin)) on2_to_on = max(tmp.values()) print(next((i for i in tmp.keys() if tmp[i] == on2_to_on))) search() Or: [code deleted] But with 1 additional line I got AC. Btw, the Python is relatively slow and uses a bit more memory too. Edited by moderator 24.11.2019 13:31 | | В чём проблема то? C++ | mNT | 1000. A+B Problem | 13 Jun 2018 00:35 | 1 | Wrong answer... Всё проверялось по 20 раз, толку никакого. Где тут ошибка то? #include <iostream> using namespace std; int main(){ int a,b; freopen("INPUT.TXT", "r", stdin); freopen("OUTPUT.TXT", "w", stdout); scanf("%ld%ld", &a,&b); printf("%ld", a+b); return 0; } | | TLE | Shahid-ul Islam | 1086. Cryptography | 12 Jun 2018 00:26 | 1 | TLE Shahid-ul Islam 12 Jun 2018 00:26 #include<iostream> using namespace std; bool isPrime(int a) { int i; if(a==1) return 0; for(i=2; i<a; i++){ if(a==2) return 1; else{ if(a%i==0) return 0; } } return 1; } int main() { int t,j,b,count=0; cin>>t; while(t--){ int k=1; cin>>j; while(count!=j){ b= isPrime(k); if(b==1) count++; k++; } cout<<--k<<endl; count=0; } return 0; } | | This problem seems to be unfair | Yaroslavtsev Grigory (SpbSPU) | 1109. Conference | 12 Jun 2018 00:04 | 26 | I think that this problem should be solved with bipartite matching. But the fastest algo for this is O(sqrt(V)*E). Did you send O(VE) and O(sqrt(V)E) solutions? Has it got TLE? I don't know implementation of O(sqrt(V)E), but Cormen writes that this is the fastest one. It can't get AC if the tests are OK, because V <= 1000 and it means E <= 10^6. Even this won't be able to fit into TL. I think that the tests are bad and would like to talk to someone who has already got AC. So I haven't sent any solutions for this problem yet. Edited by author 03.04.2005 00:56 I also haven't sent any solutions for this problem yet. But so many people had got AC... I think tests are not such terrible :) Sorry, Cormen writes only about algos using maxflow. There is another method, that uses chains and works in O(V^2), it is described in "Discrete Analysis" by Romanovsky. subj. The best algo I know (I mean I know that it exists) is ABMP algo (Alt-Blum-Mehelhorn-Paul algo, but I did not find it anywhere). It is almost 10 times faster than Hopcroft-Karp. Standart MaxMatch algos are not so slow as you think. Mostly they work in O(E) while worst time complexity is O(VE) or O(sqrt(V)*E). Actually it is VERY hard to construct worst case for max-match algo. For example if you try to fuck up QSort, you create some array. But! If you pick not middle element, but it's neighbour you will easily pass this test case... The same aplies to MaxMatch algo's... But since this algo is not so trivial, there exists a lot of almost equal implementations, which will behave absolutely different on critical tests... E is lot less than V^2, since you won't be able to read all edges in time limit =). Try submitting easiest implementation to this problem =). P.S. Is "Discrete Analysis" by Romanovsky available somewhere in the Internet? (On Russian or English or Ukrainian). Thank you very much for your reply. This is what I expected, so I said that this problem is a little bit unfair, because the worst case won't get AC. I wasn't able to find Romanovsky's book in the Internet, I think it can be found in St.Petersburg only, because Romanovsky is our SU lecturer. The algo written there is rather difficult and seems to be a little bit wrong, but I think it can be corrected, so it will be O(V^2). I couldn't find "Discrete Analysis" by Romanovsky. Can someone who had found it already give me I link. I would be very, very greatful :) In fact Romanovsky describes method that looks like Hopcraft-Karp, but in is O(V^3). (He thinks that adding a chain to matching is O(1)) there are so many discussions. That is why I have written to increase the number of dialogues. :) You are right! This problem is unfair and the tests are bad. I got AC with simple V^3 solution in 0.031 but for V=1000 it should be TLE. New test should be added. I'll add no test for this problem! Imagine the test with complete bipartite graph. It's size would be 8.5 MB! Reading routines would work at least 0.3 sec. As you have AC with time 0.031 you can see that tests are not so big. But most solutions will work very fast on such tests! I can't construct a graph that fail all O(V^3) solutions. My O(V^3) solution works faster than my O(V^2.5) solution on every test I can make. My O(V^3) solution is Greedy+DFS. It has only 60 lines! If I can't make the problem perfect then why should I change anything? I agree that failing all O(V^3) solutions is too hard. When I started this thread I didn't know about greedy initializing, which works really perfectly! Of course, it was obvious that there are not so many edges in this graph both because of TL and ML (and because of a lot of people getting AC). But why isn't it written in statement and we should guess this ourselves. Just writing that K <= "some value" will be much better I think. To Vladimir Yakovlev: please, pay attention to problem 1040 (Airline company), it seems that there it's possible to add some tests making problem much more difficult than it is now. On 1040: can you suggest a solution for this "much more difficult" problem? On 1109. I think, it is possible to fail most of greedy solutions. If you want, I will send to you several tests. 1040: I don't know solution for this problem, if there were some tests I would try to pass them combining simple idea and some heuristics. 1109: please e-mail me on grigory@inbox.ru, thanks in advance. And I would really like to know your real name and study place, as you got to the 2nd place on timus! Edited by author 05.01.2006 17:23 I agree with Yaroslavtsev Grigory. Just change the problem text, so the big tests will not be possible. If there are no tests with N=1000, so the limit for N should be decreased. Or you can add the limit for K, which is maximum K from tests. Why? Vladimir Yakovlev (USU) 5 Jan 2006 16:26 Such problems are often included in real problemsets. You just need to take the risk and write a solution that is not guaranteed effective enough. Re: Why? Yaroslavtsev Grigory (SpbSPU) 5 Jan 2006 17:14 It depends on problemsets, because I'm completely sure that I won't get such a problem on NEERC or just Northern Subregional contest. There such problems are treated as "bad" (especially like 1040). Also I think it's difficult to find such problem on acm.sgu.ru, all problems I solved there are "good". By the way, I think you know that many russian best programmers are training there. But "bad" problems are often found on IOI-like contests, where points are given for each problem, and it's ok there. So it completely depends on you to try making problems better (as you did with "Ships") or not. My opinion is that problems should be "better". As for me, I like this problem. Greedy init is ok, O(N^3) gets AC with flying colors meanwhile the test set is not as weak as you probably think. 1109 just shows that asymptotic complexity may be beaten sometimes. No test should be added imho. P.S. TLE? Weak tests? Bad problem? Well, there are 3 options: - create your own test set and solution, contact with the admin and prove your ones are better than we have now; - host your own acm-server and make all the problems there as good as you can; - join "the russian best programmers" on acm.sgu.ru... LOL ;))) No offence. Edited by author 05.01.2006 19:48 Sorry, I forgot to write the definition of "goodness". "Good" problem is the one, for which exists a solution which passes every possible testcase. This definition is a bit incorrect, because it doesn't include problems where some randomization is needed. But anyway it's obvious that 1040 is "bad". Unfortunately I lack time (because of my exam session) to find out whether 1109 is "bad" or not, but some people ("still alive") can even give tests. Anyway, I insist on adding limitation for K or/and N as "Sandro (USU)" said. I like timus, but some of my friends don't and left it because of similar problems with testcases and statements. It's sad. So sometimes I'm trying to pay admin's attention to the things I don't like. Re: Vladimir Yakovlev (USU) 6 Jan 2006 02:44 I don't think that all people that solve problems here compete in NEERC and Northern Subregional Contest as you do. Many other regional/subregional/local contests may contain such problems as 1109 and 1040. All types of problems should be presented on Timus. If you don't like a problem you need not solve it. Your posts made me sure not to change anything :) But for all people that like to solve only "good" problems I say that K < 60000 in this problem. And I won't add this to problem text. PS. 1. I also want to make Timus better. I improved many problems and I can say that this problem is good enough. I tried to improve it already, but I decided to leave it unchanged. 2. Please tell me why did your friends leave Timus? 3. Some problems on acm.sgu.ru are "bad" also :( I'll do my best to make the number of Timus's "bad" problems less than sgu's. 4. Question about 1040 is still opened. Wait some time. Re: Re: Yaroslavtsev Grigory (SpbSPU) 6 Jan 2006 03:46 Of course in some way you are right, because even problems in World Finals have multiple test cases but the number of tests isn't written. On some training I got TLE in such problem with N <= 10 solving it in O(N^4) and AC with O(N^3). I think it is "bad", but so it is. I really like NEERC-like problems, but after all it's just my opinion. It's your choice and it seems to be right, thanks for telling real limitation for K. 1.It's really great, that you are trying to do it. I understand how difficult it is, much more difficult than solving problems. 2.I think that one reason is bad tests and statements, there are usually a lot of bugs when a new problemset is added. The second reason seems to be that problems on timus differ from NEERC-like in ideas. I like it, but it is not so useful when you're preparing for the contest. 3.I also think so, I said that it is perfect just for contrast, anyway it seems to me that sgu is "better". 4.Thanks once more. I was really annoyed seeing no reply on Burunduk1's post about weak tests. Good luck! 1. I like to solve acm-like problems. 2. I like timus but IMHO sgu is better. Just one example... (I have more but they all alike) I wrote solution to problem 1005. Stone pile. Timus said that it's ACCEPTED. Then I generated about 20 random tests. My "AC" program FAILED on 50% of these tests! It's not good at all! BTW, I don't know about such examples on SGU. 3. Good luck to all who tries to make timus better! No need to be upset 'cause UVA is worse than TIMUS :) Why are you so sure you program failed them? It's rather difficult to check large random test without the correct answer (I mean, finding it yourself). In case it's TL, maybe your computer has less performance or you are using a different check system that counts astronomical time (if you have a lot of other processes it might have considerable effect). Who said my random tests were large? I can check them manually! So correct answer is pretty obvious. Problem 1005 is very old. Problemsetters of that time couldn't imagine that their problems will be solved in 2006 by thousands of people. I can't remake all problems in Volume 1 :) Please, appeal to weak problems of nowadays only. | | What's wrong with test #3? | Komarov && Kantorov | 1298. Knight | 11 Jun 2018 21:54 | 5 | I solved this problem using backtracking with optimization( you start from some position and then you go to the position that has the fewest future possible moves...//from other post). But it's WA 3. Then I checked the answers of my program myself and all was correct.Then I wrote a simple checker for this problem. And it said all right. Then I tried to save the answers(firstly my answers then answers from forum) as the constants in the program. And the answer was WA 3 again. Help me, please!!! P.S. Sorry for my English. Edited by author 12.09.2005 23:16 Edited by author 12.09.2005 23:21 But your solution is wrong! Thank you for answer. I found the mistake in my code and now I got AC! At me the same problem!!! I do not know in what a mistake. Help, please. | | test 30???????? | gooooooogol | 1285. Thread in a Hyperspace | 11 Jun 2018 18:21 | 1 | | | No subject | Zihan Abedin | 1086. Cryptography | 11 Jun 2018 13:20 | 1 | I am new in coding..please help me to solve this problem | | No subject | __Andrewy__ | 1949. The Best Picture in the Galaxy | 10 Jun 2018 23:02 | 1 | Edited by author 10.06.2018 23:09 | | WA8 | [ITMO] Semyon Stepanov | 1237. Evacuation Plan | 10 Jun 2018 09:44 | 1 | WA8 [ITMO] Semyon Stepanov 10 Jun 2018 09:44 I always have WA8, can you give me some tips about this test? | | Решение C# | Solution C# | Viktor | 1000. A+B Problem | 10 Jun 2018 01:46 | 2 | using System; namespace t1000{ class Program{ public static void Main(string[] args){ string[] s = Console.ReadLine().Split(' '); Console.WriteLine(int.Parse(s[0]) + int.Parse(s[1])); } } } using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks; namespace ConsoleApp1 {
class Program { static void Main(string[] args) { int a, b; a=Convert.ToInt32(Console.ReadLine()); b = Convert.ToInt32(Console.ReadLine()); Console.WriteLine(a + b);
} } } Why my method is incorrect? | | The dice sides 2, 3 and 6 are (probably) not symmetrical. | Alexander Vasilyev`~ | 1015. Test the Difference! | 9 Jun 2018 22:33 | 1 | It must be mentioned that two dice are considered equal if the numbers of points on corresponding faces are equal regardless of the orientation of the points on each face. For example, if you superimpose two dice and the numbers of points coincide but two corresponding faces look like this: #.. ..# .#. and .#. ..# #.. then the dice have the same schemes. Edited by author 09.06.2018 22:36 | | String takes 1 space count extra when input is !!. Please help me out | Saurav Jaiswal | 1083. Factorials!!! | 9 Jun 2018 19:53 | 1 | import java.util.*; import java.lang.*; public class Factorial{ public static void main(String[] args){ Scanner cin=new Scanner(System.in); int n=Integer.parseInt(cin.next()); String k=cin.nextLine(); int j=k.length()-1; int sum=1; for(int i=n;i>0;i-=j){ sum=sum*i; } System.out.println(sum); } } | | Why wrong answer ? | Logerator | 1068. Sum | 9 Jun 2018 19:23 | 1 | #include <stdio.h> void main() { int N,i,sum; sum = 0; scanf_s("%d", &N); if (N < 0) { for (i = N; i < 2; i++) { sum = sum + i; } } else { for (i = N; i > 0; i--) { sum = sum + i; } } printf("%d", sum);
} | | Help | Evgeniy | 1989. Subpalindromes | 9 Jun 2018 16:44 | 1 | Help Evgeniy 9 Jun 2018 16:44 I cant understand my mistake for TLE14. My code var s,s1,s2: string; z2,z1,a,i,f,p,code: integer;z,n:int64; ch:char; begin readln(s); readln(npalindrome? 1 100000); for i:=1 to n do begin readln(s2); if s2[1]='p' then begin a:=13;z1:=0;z2:=0; while s2[a]<>' ' do inc(a); val(copy(s2,13,a-13),z1,code); val(copy(s2,a+1,length(s2)-1),z2,code); z:=z2-z1+1; if z2>length(s) then z2:=length(s); s1:=copy(s,z1,z);
f := 1; p:=1; while (p<=length(s1)div 2)and(f<>0) do if (s1[p] <> s1[length(s1)-p+1]) then begin writeln('No'); f := 0; end else p:=p+1;
if f = 1 then writeln('Yes'); end else begin a:=8;z1:=0; while s2[a]<>' ' do inc(a); Val(copy(s2,8,a-8),z1,code); ch:=s2[a+1]; delete(s,z1,1); insert(ch,s,z1);
end; end; end. | | WA 50!!! what test???? | gooooooogol | 1075. Thread in a Space | 8 Jun 2018 05:04 | 1 | | | WA9? NEED HELP! | Khamidjon | 1028. Stars | 6 Jun 2018 22:14 | 3 | Check that arrays were initiated with zeroes. unfortunately it didn't help. | | accepted | Mikhail | 1026. Questions and Answers | 6 Jun 2018 02:00 | 1 | //#pragma GCC optimize("Ofast,no-stack-protector") //#pragma GCC target("avx") #include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds; using namespace std;
#define re return #define pb push_back #define eb emplace_back #define all(x) (x).begin(), (x).end() #define fi first #define se second #define sqrt(x) sqrt(abs(x)) #define mp make_pair #define pi (3.14159265358979323846264338327950288419716939937510) #define fo(i, n) for(int i = 0; i < n; ++i) #define ro(i, n) for(int i = n - 1; i >= 0; --i) #define unique(v) v.resize(unique(all(v)) - v.begin())
template <class T> T abs (T x) { re x > 0 ? x : -x; } template <class T> T sqr (T x) { re x * x; } template <class T> T gcd (T a, T b) { re a ? gcd (b % a, a) : b; } template <class T> int sgn (T x) { re x > 0 ? 1 : (x < 0 ? -1 : 0); }
typedef vector<int> vi; typedef vector<vi> vvi; typedef pair<int, int> ii; typedef vector<ii> vii; typedef vector<string> vs; typedef double D; typedef long double ld; typedef long long ll; typedef pair<ll, ll> pll; typedef vector<ll> vll; typedef unsigned long long ull; typedef tree <pair<int, char>, null_type, less<pair<int, char>>, rb_tree_tag, tree_order_statistics_node_update> _tree; const int maxn = (int) 1e5; int a[maxn]; int main() { int n, x; cin >> n; fo(i, n) { cin >> a[i]; } sort(a, a + n); string str; cin >> str >> n; fo(i, n) { cin >> x; cout << a[x - 1] << '\n'; } re 0; } | | (JAVA) Runs fine in Eclipse but judge says there's a runtime error. HELP! | Kenny Castro-Monroy | 1001. Reverse Root | 6 Jun 2018 00:28 | 3 | package timusreverseroot; import java.text.DecimalFormat; import java.util.*; public class TimusReverseRoot { public static void main(String[] args) { DecimalFormat f = new DecimalFormat("#0.0000"); Scanner keyboard = new Scanner(System.in); String inputs = keyboard.nextLine(); String[] parsed = inputs.split(" ");
for (String parsed1 : parsed) { int square = (int) Math.pow(Integer.parseInt(parsed1), 2); System.out.println(f.format(square)); } }
} I added in the package line but if I left that in, it would give me a compilation error, why is that? And this code runs perfectly fine in Netbeans but the judge gives a compilation error Edited by author 07.05.2018 22:48 Edited by author 07.05.2018 22:49 Edited by author 07.06.2018 01:49 | | accepted | Mikhail | 1931. Excellent Team | 4 Jun 2018 23:20 | 1 | //#pragma GCC optimize("Ofast,no-stack-protector") //#pragma GCC target("avx") #include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds; using namespace std;
#define re return #define pb push_back #define eb emplace_back #define all(x) (x).begin(), (x).end() #define fi first #define se second #define sqrt(x) sqrt(abs(x)) #define mp make_pair #define pi (3.14159265358979323846264338327950288419716939937510) #define fo(i, n) for(int i = 0; i < n; ++i) #define ro(i, n) for(int i = n - 1; i >= 0; --i) #define unique(v) v.resize(unique(all(v)) - v.begin())
template <class T> T abs (T x) { re x > 0 ? x : -x; } template <class T> T sqr (T x) { re x * x; } template <class T> T gcd (T a, T b) { re a ? gcd (b % a, a) : b; } template <class T> int sgn (T x) { re x > 0 ? 1 : (x < 0 ? -1 : 0); }
typedef vector<int> vi; typedef vector<vi> vvi; typedef pair<int, int> ii; typedef vector<ii> vii; typedef vector<string> vs; typedef double D; typedef long double ld; typedef long long ll; typedef pair<ll, ll> pll; typedef vector<ll> vll; typedef unsigned long long ull; typedef tree <pair<int, char>, null_type, less<pair<int, char>>, rb_tree_tag, tree_order_statistics_node_update> _tree; int main() { int n, x; ii ans = mp(-1, 0); pair <ii, int> cur; cin >> n >> cur.fi.fi; cur.fi.se = cur.se = 0; fo(i, n - 1) { cin >> x; if (x >= cur.fi.fi) ++cur.fi.se; else { cur.fi.se++; ans = max(ans, mp(cur.fi.se, cur.se)); cur = mp(mp(x, 1), i + 1); } } ans = max(ans, mp(cur.fi.se, cur.se)); cout << ans.se + 1 << endl; } |
|
|