| Show all threads Hide all threads Show all messages Hide all messages |
| Is there actually an O(N^5) solution? | PrankMaN | 1452. Pascal vs. C++ | 1 Jun 2020 14:26 | 1 |
I've tried to come up with solution from the story part of the problem, but the worst algorithm I came up with is O(N^4). Is there an O(N^5) algorithm? |
| using sieve method in c++.. | Shuvro Chandra Das | 1086. Cryptography | 1 Jun 2020 10:48 | 1 |
#include <bits/stdc++.h> using namespace std; #define MAX_SIZE 1000005 void SieveOfEratosthenes(vector<int> &primes) { bool IsPrime[MAX_SIZE]; memset(IsPrime, true, sizeof(IsPrime)); for (int p = 2; p * p < MAX_SIZE; p++) { if (IsPrime[p] == true) { for (int i = p * p; i < MAX_SIZE; i += p) IsPrime[i] = false; } } for (int p = 2; p < MAX_SIZE; p++) if (IsPrime[p]) primes.push_back(p); } int main() { int t; cin>>t; vector<int> primes; SieveOfEratosthenes(primes); while(t--){ int n; cin>>n; cout<<primes[n-1]<<endl; } return 0; } |
| Пишите краткое содержание в таких задачах | 👑OmegaLuL230👑 | 1700. Awakening | 30 May 2020 02:23 | 1 |
В задачах с условием, на прочтение которых уходит 10 минут (или более) предлагаю писать краткое содержание в форуме! |
| WrongAnswer #28 | GOR ABELYAN | 2102. Michael and Cryptography | 29 May 2020 13:26 | 4 |
Edited by author 29.05.2020 13:26
Edited by author 29.05.2020 13:26 Try to change this
for (int i = 3; i <= Convert.ToInt32(Math.Ceiling(BigInteger.Log(n, 2))); i += 2)
to this
for (BigInteger i = 3; i * i <= n; i += 2)
Btw, you do not need BigInteger here, long is enough.
Edited by author 30.05.2020 21:39 After this you will receive TLE39, try to handle the case with two big multiplied prime numbers, for example 1000000007*1000000009.
Edit: this is even easier, than I thought. Just change your for to
for (BigInteger i = 3; i < 10000000; i += 2)
Edited by author 29.05.2020 03:42
Edited by author 29.05.2020 03:42 |
| Some test cases | Smilodon_am [Obninsk INPE] | 2048. History | 27 May 2020 11:32 | 3 |
My accepted program gives below answers for tests:
Test:
1919 1000000000
Answer:
0: 0
1: 427499181
2: 424999184
3: 147499717
4: 0
5: 0
6: 0
7: 0
8: 0
9: 0
10: 0
11: 0
12: 0
Test:
100000 2000000
Answer:
0: 0
1: 812251
2: 807500
3: 280250
4: 0
5: 0
6: 0
7: 0
8: 0
9: 0
10: 0
11: 0
12: 0 Have you used info that Gregorian calendar repeated for each 400 years? test:
9876 9876
answer:
0: 0
1: 1
2: 0
3: 0
4: 0
5: 0
6: 0
7: 0
8: 0
9: 0
10: 0
11: 0
12: 0
test:
1234567890 987654321012345678909876543210123456789
answer:
0: 0
1: 422222222232777777733972222221800000004
2: 419753086430246913536697530863777777784
3: 145679012349320987639206790123311111112
4: 0
5: 0
6: 0
7: 0
8: 0
9: 0
10: 0
11: 0
12: 0
Right or wrong?
Edited by author 27.05.2020 11:35 |
| WA #17 | Lebedev_Nicolay[Ivanovo SPU] | 1774. Barber of the Army of Mages | 27 May 2020 01:33 | 3 |
WA #17 Lebedev_Nicolay[Ivanovo SPU] 29 Dec 2011 01:41 Could anyone help me with 17th test? Re: WA #17 Lebedev_Nicolay[Ivanovo SPU] 29 Dec 2011 02:08 AC now.
I forgot the following:
when building flow graph we need to set capacity equal to 1 when edge is mage->time and capacity equal to 0 when edge is time->mage.
Edited by author 29.12.2011 02:09
Edited by author 29.12.2011 02:09 Re: WA #17 Toshpulatov (MSU Tashkent) 27 May 2020 01:33 If use Dinis -> remember that Oriented Graph |
| how to solve this problim with geometric way? | vnyemets | 1956. Fire Signals | 26 May 2020 12:19 | 2 |
I really like geometric problems. The problem can be solved using LP, PCA, analysis. But how to apply computational geometry (convex hull) to the problem? The optimal line goes through two points; it's not some arbitrary line. This could lead to O(N^3) solution if you enumerate every of N(N-1)/2 lines and compute the distance in O(N). A better solution is doing two-pointers optimization for every point. For each point you have to sort all the other points according to their polar angle with the fixed point; and then computation of O(N) lines for a fixed endpoint takes linear time with two pointers. Complexity of this solution is O(N^2 log N). Just recall that point-line distance is given by the formula abs(a*X+b*Y)/sqrt(a*a+b*b) (as one of endpoints is treated as an origin there is no constant term in abs()). So you could group points (X,Y) into two groups: those that have a positive sign of (a*X+b*Y) and those that have a negative one — this is precisely what you need two pointers for. Then the answer for each line will be computed as (a*sumX_PositiveGroup + b*sumY_PositiveGroup - a*sumX_NegativeGroup - b*sumY_NegativeGroup)/sqrt(a*a+b*b).
Edited by author 26.05.2020 12:21 |
| (to Admin) What correct answer for 1 2 2? 1 10 10? | maslowmw | 1114. Boxes | 26 May 2020 00:06 | 1 |
Is it 6 for all where n=1 and a,b>0? Because my AC solution gives 9 (yes, I implement idea from forum). For test 1 10 10 my solution gives 121
0
x
y
xx
yy
xy
Edited by author 26.05.2020 00:20
Edited by author 26.05.2020 00:20 |
| WA#13 | nirkhut | 1052. Rabbit Hunt | 24 May 2020 13:57 | 1 |
WA#13 nirkhut 24 May 2020 13:57 does anyone know what is this test?
thanks |
| WA4 pls give test | Andrey Ladeyschikov | 2112. Battle log | 23 May 2020 16:43 | 4 |
You can shoot in dead player |
| What's wrong with my Test 2? | Garin | 1036. Lucky Tickets | 23 May 2020 10:15 | 6 |
I can get the right answer of 50 500,but I can't AC the second test..What's up? What's the data? Maybe
for test 2 3 answer 0 thanks very much for your advice Than you: for test 2 3 answer 0 > test 2 3
This test is not correct cause S must be even.
Update:
Sorry, S can be odd! And yes, this is the second test case.
Edited by author 23.05.2020 10:20
Edited by author 23.05.2020 10:20
Edited by author 28.09.2007 16:34 |
| Чёрт знает почему это так | Mahilewets | 1104. Don’t Ask Woman about Her Age | 22 May 2020 21:26 | 3 |
Ну я вспомнил что число в десятичной системе счисления
Делится на 9 (то есть на 10-1)
Если сумма его цифр делится на 9
Я предположил что в любой k-ичной системе счисления верно
Что если сумма цифр некоторого числа делится на k-1 то и это число делится на k-1
И это оказалось правдой для тех k
Которые содержатся в тестах к этой задаче. Большое спасибо! Эта подсказка мне помогла. Доказательство вашего утверждения:
Пусть мы сейчас в k-ой системе счисления и если прочитать наше число X слева направо, то получим цифры a_n, a_{n - 1}, ... , a_1, a_0 (при этом 0 <= a_i <= k - 1 для всех i). Тогда в десятичной системе счисления оно будет равно X = a_n * k ^ n + a_{n - 1} * k ^ {n - 1} + ... + a_1 * k + a_0. Так как k = 1 (mod (k - 1)), то X = a_n + a_{n - 1} + ... + a_1 + a_0 (mod (k - 1)). Значит, X делится на (k - 1) тогда и только тогда, когда его сумма цифр делится на (k - 1). |
| Wrong on test 1 ???????? | DanGeros | 1880. Psych Up's Eigenvalues | 22 May 2020 16:09 | 1 |
#include <iostream>
using namespace std;
int v[4001],w[4001],q[4001];
int se_gaseste (int val , int inceput , int sfarsit,int v[4001]) {
int mijloc=(inceput+sfarsit)/2;
if (v[mijloc]==val) return 1;
if (inceput >= sfarsit) return 0;
if (val>v[mijloc]) se_gaseste(val,mijloc+1,sfarsit,v);
else se_gaseste(val,inceput,mijloc-1,v);
}
int main()
{
int n,m,t,nr=0;
cin>>n;
for (int i=1;i<=n;i++)
cin>>v[i];
cin>>m;
for (int i=1;i<=m;i++)
cin>>w[i];
cin>>t;
for (int i=1;i<=t;i++)
cin>>q[i];
for (int i=1;i<=n;i++) {
if ( se_gaseste(v[i],1,m,w) && se_gaseste(v[i],1,t,q)) nr++;
}
cout<<nr;
return 0;
}
i tested this algorithm on many exemples and all works how i can't pass the first test, please help , thx.
A little explication : i take every number from first vector and i check if exist in last both vectors . i use binary search
Edited by author 22.05.2020 16:12 |
| Useful tests | Levon Oganesyan | 2113. Survive the flood | 21 May 2020 22:18 | 1 |
5 5
5 1 10 1 1
10 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
2 2
1 3
Ans: 9
5 5
10 8 8 7 6
8 8 7 6 5
8 7 6 5 4
7 6 5 4 3
6 5 4 3 4
2 2
1 2
Ans: 1
5 5
10 8 8 7 6
8 8 7 6 5
8 7 6 5 4
7 6 5 4 3
6 5 4 3 7
2 2
1 2
Ans: 2
3 3
1 1 1
1 1 1
1 1 10
1 1
2 2
Ans: -1
5 5
1 10 25 30 35
50 1 24 30 35
1 10 23 30 35
10 50 22 30 35
1 39 21 30 39
1 1
1 5
Ans: 9 |
| Runtime error java | Schwarz | 1025. Democracy in Danger | 21 May 2020 02:02 | 2 |
Прекрасно работает в IDE, а на сервере ошибка. Объясните в чем дело
import java.util.LinkedList;
import java.util.Scanner;
import static java.util.Collections.sort;
public class Bird {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int i = sc.nextInt();
sumGol(minKol(i), toConteiner(i));
}
public static LinkedList<Integer> toConteiner(int i) {
Scanner sc = new Scanner(System.in);
String[] str = sc.nextLine().split(" ");
LinkedList<Integer> in = new LinkedList<>();
for (int j = 0; j < str.length; j++) in.add(Integer.parseInt(str[j]));
return in;
}
public static int minKol(int i) {
if (i % 2 != 0) i = i / 2 + 1;
else i = i / 2;
return i;
}
public static void sumGol(int i, LinkedList<Integer> l) {
sort(l);
int sum = 0;
for (int j = 0; j < i; j++) {
sum = sum + minKol(l.get(j));
}
System.out.print(sum);
}
} На этот вопрос есть где-нибудь ответ?
У меня другой код, та же ошибка. ( |
| why wa10? | Felix_Mate | 1987. Nested Segments | 20 May 2020 23:29 | 4 |
I found my mistake. Helpfull test:
4
1 2
3 100
4 5
6 7
2
1
7
ans:
1
4
HINT:This problem can be solved O(n) with stack.
Edited by author 31.08.2016 10:07 Try to use 'longint' instead of 'int64'. In some problems it helps if you have WA. Thank you so much for the test! |
| Code not producing any output? | Naman Sharma | 1654. Cipher Message | 20 May 2020 13:21 | 2 |
#include<bits/stdc++.h>
using namespace std;
stack<char> S;
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
string s;
cin >> s;
int len = s.length();
for(int i = 0; i < len;i++)
{
char c;
if(S.empty())
c = 0;
else
c = S.top();
if(c == s[i])
S.pop();
else
S.push(c);
}
string ans = "";
len = S.size();
for(int i = 0; i < len;i++)
{
char c = S.top();
ans += c;
S.pop();
}
reverse(ans.begin(),ans.end());
cout << ans;
} You should do S.push(s[i]) in your else clause inside the for loop. |
| What about WA16 ? | Khujamurod | 1671. Anansi's Cobweb | 20 May 2020 00:58 | 9 |
I used DSU and I have WA16. Can you help me? I can't help you without code.
I have never WA#16.
I only have several MLE's before AC. "/*
const int maxn = 100100;
int a[maxn], b[maxn], c[maxn];
bool order[maxn];
int cnt;
int p[maxn], rank[maxn];
int find_set(int x) {
if(p[x] == x) return x;
return p[x] = find_set(p[x]);
}
int unite(int x, int y) {
x = find_set(x);
y = find_set(y);
if(x == y)
return 0;
if(rank[x] > rank[y]) {
p[y] = x;
} else {
p[x] = y;
if(rank[x] == rank[y])
rank[y] ++;
}
return 1;
}
int main() {
int n, m, q;
scanf("%d%d", &n, &m);
for (int i = 0; i < m; i ++) {
scanf("%d%d", a + i, b + i);
}
scanf("%d", &q);
for (int i = 0; i < q; i ++) {
scanf("%d", c + i);
order[--c[i]] = true;
}
for (int i = 0; i < n; i ++) p[i] = i;
cnt = n;
for (int i = 0; i < n; i ++) {
if(order[i] == false) {
cnt -= unite(a[i], b[i]);
}
}
c[q] = cnt;
for (int i = q - 1; i > 0; i --) {
cnt -= unite(a[c[i]], b[c[i]]);
c[i] = cnt;
}
for (int i = 1; i < q; i ++)
printf("%d ", c[i]);
printf("%d", c[q]);
}*/" You have a cycle where you are calculating cnt for q.
The limit is wrong.
i<n is wrong.
i<m is correct.
Because of m is number of edges not n.
I changed n to m in your code and got AC again. Thanks Mahilewets!!! Is your idea same or not ? Idea is the same.
I was getting MLE because of critical mistake in find_set.
There was an iterative implementation. My iterative function was equivalent to :
return (par[x] == x) ? x : par[x] =find_set (x) ; Thanks for your answer ! cause i made the same problem! The good part is
Initially I made such mistakes incredible often
But after only few months of regular basis practice
Such blunders almost completely disappeared i do exactly same mistake and get wa at test 16
thnx Mahilewets Nikita [BSUIR] |
| Test 13 | gvsmirnov | 1728. Curse on Team.GOV | 19 May 2020 20:23 | 3 |
Test 13 gvsmirnov 18 Oct 2009 23:22 If you fail there, maybe you have forgotten that there could be only one person in a party at some contest.
Edited by author 18.10.2009 23:32 Re: Test 13 Oleg Strekalovsky aka OSt [Vologda SPU] 22 Oct 2009 22:56 I think, you is wrong.
By your logic - in second demo test answer may be Fominykh (team contains only Fominykh) It's not true. gvsmirnov meant that you can get on input team of 1 person
Edited by author 19.05.2020 20:44
Edited by author 19.05.2020 20:44 |
| if n = 0 or n = 1 ? | Tanim | 1014. Product of Digits | 19 May 2020 18:51 | 4 |
what will the output if
input = 1 or 0 and why? if n=0 then q=10
if n=1 then q=1 Should be 11 though, I don't know why authors decided on 1. The solution requires a product of digits. 1 by itself isn't a product at all.
Edited by author 19.05.2020 18:51 |
