| Show all threads Hide all threads Show all messages Hide all messages |
| How come there are solutions that are 0.015 sec and less than 0.1 sec | Sergey | 2130. Alice + Bob | 31 Jul 2025 19:45 | 4 |
my solution is the following:
start with least common multiple = 1
make char array of 1000 000 to track forbidden divisors
let div be the divisor and ans the answer
if ans == 1 make new lcm of the previous lcm and current divisor. if it is over 10^12 - fail. find all the divisors of div, check that they are not forbidden in the forbidden array
if ans == 0 - check if lcm is divisible by the divisor and fail if it is.
complexitiy O(n * sqrt(1000000)) (sqrt from the "find all divisors)
my solution gets 0.5 sec (using cin,cout with tie(null))
what is the solution that gets less than 0.1 sec? Is there any hint? no need to find all divisors. u can just use lcm and mod operations. i can send you easy solution if u r still interested need to pray to god for quick solutions
#pragma GCC optimize("Ofast")
#pragma GCC optimize(O3)
#pragma comment(linker, "/stack:200000000")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,sse4.1,sse4.2,popcnt,abm,mmx,avx,avx2,tune=native")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("profile-values,profile-reorder-functions,tracer")
#pragma GCC optimize("vpt")
#pragma GCC optimize("rename-registers")
#pragma GCC optimize("move-loop-invariants")
#pragma GCC optimize("unswitch-loops")
#pragma GCC optimize("function-sections")
#pragma GCC optimize("data-sections")
#pragma GCC optimize("branch-target-load-optimize")
#pragma GCC optimize("branch-target-load-optimize2")
#pragma GCC optimize("btr-bb-exclusive")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks") |
| suffix automaton | datym | 1769. Old Ural Legend | 30 Jul 2025 20:33 | 1 |
|
| JUDGES!!! SEE HERE!!!! | DonNTU Team (Akulshin, Belikov, Trofimenko) | 1303. Minimal Coverage | 30 Jul 2025 01:17 | 3 |
Hello to all. I've (Trofimenko:)) solved this problem.
In my program I used constant MAXM=5000. I've got WA5. When I changed MAXM to 6000 I've got WA too. But when I changed maxm to 60000 I've got AC. It's so stupid... The set contains at least one and at most 99999 segments!
What's means of your MAXM??? The number of segments? If yes,you are wrong without doubt! No, I was using it to limit M which should be <=5000 |
| Hint | __Andrewy__ | 2174. Dualism of Numbers | 29 Jul 2025 22:32 | 1 |
Hint __Andrewy__ 29 Jul 2025 22:32 Hint 1:
The original graph is not bipartite.
However, you may notice that even numbers are included in one set, and odd numbers > 1 are included in another. Separately, you need to understand what to do with 1.
Hint 2:
Kuhn's Algorithm for Maximum Bipartite Matching for bipartite graph (even numbers, odd numbers > 1 and ones)
Some tests:
10
2 4 6 8 5 7 1 1 9 2
->
YES
2 5
4 7
8 9
6 1
2 1
6
2 4 6 8 1 5
->
NO
12
1 1 1 1 1 2 3 4 5 6 7 8
->
YES
8 3
2 5
6 7
4 1
1 1
1 1
Edited by author 29.07.2025 22:35 |
| my AC solution is very simple | sahand | 1047. Simple Calculations | 29 Jul 2025 15:29 | 2 |
Hello guys
in this problem we have n equation with n unknown
than solved with Gause-Jordan modification
a0 a1 a2 a3 a4 a5 .... an
if a1=(a0+a2)/2 - c0 then
2a1 - a2 = a0- 2c0
if a2=(a1+a3)/2 - c1 then
-a1 +2a2 - a3= -2c1
....
2a1 - a2 = a0- 2c1
-a1 +2a2 - a3= -2c2
-a2 +2a3 - a4= -2c3
-a3 +2a4 - a5= -2c4
....
-an +2an-1 - an+1 = -2cn
e.g for n=5:
2 -1 0 0 0 a0-2c1
-1 2 -1 0 0 -2c2
0 -1 2 -1 0 -2c3
0 0 -1 2 -1 -2c4
0 0 0 -1 2 a6-2c5
and now you must solve the top diagonal "-1" of
matirs ( start of last row)and finish.
the order is O(n)
sudo code is:
m[0 ... n]
a=2;
while(--n){
f= 1/a;
m[n-1]= m[n-1]+ f*m[n];
a = 2-f;
}
cout<< m[0]/a ;
Edited by author 01.03.2008 22:56 I did the same stuff in my solution, but I used Cramer's rule to calculate the answer. I used recurrent sequence for calculating determinants. Final complexity is O(n), but the it is easily can be calculated in O(logn). |
| I thought it would be more difficult. | Спажев Артемий Сергеевич | 1496. Spammer | 29 Jul 2025 15:10 | 1 |
n = int(input())
b = []
c = []
for i in range(n):
a = input()
if a in b:
if a in c:
a = " no matter"
else:
c.append(a)
else:
b.append(a)
d = len(c)
for s in range(d):
print(c[s]) |
| Make second version | andreyDagger`~ | 2179. Need More Roads | 24 Jul 2025 17:13 | 2 |
Make second version of this problem, where you need to output all the roads |
| Is there any solution aside from DP? | Aleksander | 2173. Meta-statement 3 | 23 Jul 2025 12:06 | 2 |
I solved it using pretty straigtforward DP O(n * m^2), obviously it's just a complexity without any additional factors but it doesn't seem to be fitting time limit. Somehow it did. But I wonder, is there any more intricate idea for a faster solution? pretty straigtforward DP O(n * m^2) it doesn't seem to be fitting time limit Most likely, your solution is actually O(N*M), because the statement says "It is guaranteed that the total number of wishes does not exceed 2 · M." |
| a good test | LeTim | 2182. Broken Rum | 22 Jul 2025 19:16 | 1 |
60
12
1 2 3 4 5 6 10 20 30 40 50 60
answer:
1152921504606846975 696452200133064741 342302865262561731 352599748013672291 114454761937119805 50063861 75394027567 4191844505805496 118264581564861425 4191844505805496 75394027567 2 |
| Why wrong answer?:((((( | Anasyasia | 2012. About Grisha N. | 19 Jul 2025 22:33 | 3 |
#include <iostream>
using namespace std;
int main()
{
int a;
cin>>a;
if (a>=7)
cout<<"Yes";
if (a<7)
cout<<"No";
return 0;
} yes and no are in capital , please check output carefully |
| how should i know what numbers are in n-element array? | Thedelka | 1264. Workdays | 15 Jul 2025 16:22 | 1 |
given number N, quantity of elements in array. so? SO?
for examplr, n = 5
is array = [1,2,3,4,5]? or [1,0,1,0,1]? or what? or [0,1,2,3,4]? |
| Why doesnt my code work? | Gopi | 2034. Caravans | 9 Jul 2025 00:47 | 1 |
I am doing standard BFS, and then finding the max of all min over all shortest paths #include <bits/stdc++.h>(ignore this) using namespace std; void solve() { int n; int m; cin >> n >> m; vector<vector<int>> adj(n+1); for(int i=0;i<m;i++){ int a; int b; cin >> a >> b; adj[a].push_back(b); adj[b].push_back(a); } vector<bool> vis(n+1,false); int s; int f; int r; cin >> s >> f >> r; vector<int> ds(n+1,0); vector<int> dr(n+1,0); //BFS from s queue<pair<int,int>> q; q.push({0,s}); ds[s] = 0; while(!q.empty()){ pair<int,int> v = q.front(); q.pop(); for(int j : adj[v.second]){ if(vis[j] == false){ ds[j] = v.first+1; vis[j] = true; q.push({ds[j],j}); } } } for(int i=1;i<=n;i++){ vis[i] = false; } // BFS from r q.push({0,r}); dr[r] = 0; while(!q.empty()){ pair<int,int> v = q.front(); q.pop(); for(int j : adj[v.second]){ if(vis[j] == false){ dr[j] = v.first+1; vis[j] = true; q.push({dr[j],j}); } } } for(int i=1;i<=n;i++){ vis[i] = false; } if(s == f){ cout << dr[s] << endl; return; } int ans = -1; // Final BFS q.push({dr[s],s}); bool found_f = false; while(!found_f){ int k = q.size(); while(k--){ pair<int,int> v = q.front(); q.pop(); for(int j : adj[v.second]){ q.push({min(dr[j],v.first),j}); if(j == f){ found_f = true; } } } } int k = q.size(); while(k--){ pair<int,int> v = q.front(); q.pop(); if(v.second == f) ans = max(ans,v.first); } cout << ans << endl; return; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); solve(); return 0; } Edited by author 09.07.2025 00:48 |
| if you have WA10 | LeTim | 1564. Counting Ones | 8 Jul 2025 15:03 | 1 |
input:
1000000000000000000
output:
524638269999999991 |
| simple geometric solution | Sssswwwppp | 1139. City Blocks | 4 Jul 2025 23:09 | 1 |
optimized search + cross product) |
| Input issues | irkstepanov | 1006. Square Frames | 28 Jun 2025 15:31 | 1 |
To read the input in C++, the following helped me: unsigned char x = cin.get().
Then I used some ifs in the form of if (x == 218) { ... }
Also, the first test case seems to be different from the one suggested in the statement. |
| I WA 10# | 1898098 | 1002. Phone Numbers | 27 Jun 2025 19:07 | 2 |
same. My previous solution was dfs approach, and it is too slow, since it is completely full bruteforce. However, I came up with dfs approach optimization.
And here I am with WA 8# :) I have absolute no idea what is wrong. |
| wa3 idk why, python | nekrip | 1297. Palindrome | 26 Jun 2025 03:00 | 1 |
b = input()
s = ''
d = []
for i in b:
s += i
if s == s[::-1]:
d.append(s)
if s != s[::-1] and len(s) % 2 != 0:
s = s[1:]
if s == s[::-1]:
d.append(s)
if s != s[::-1] and len(s) % 2 != 0:
s = s[1:]
m = max(d, key=len)
if len(m) <= 1000:
print(m) |
| if you have WA | pon | 1192. Ball in a Dream | 16 Jun 2025 16:39 | 1 |
see what your program outputs for an integer answer
ps it should output .00
посмотрите, что выводит ваша программа при целом ответе
ps она должна выводить .00 |
| some tests | Felix_Mate | 1905. Travel in Time | 14 Jun 2025 15:53 | 2 |
1)
4 4
1 2 9 15
1 4 0 8
2 3 20 30
3 1 31 0
1 4 9 30
->
4
1 3 4 2
2)
2 3
1 2 0 5
1 1 110 80
1 1 90 0
1 2 100 6
->
3
2 3 1
3)
3 6
1 2 50 55
2 1 55 40
1 2 0 1
1 3 41 80
3 2 80 12
2 1 15 0
1 2 49 7
->
6
1 2 4 5 6 3 n= ; k= ; m=n*k <=100000
------------------------
n m
1 2 1 1
1 2 2 2
.......
1 2 k k
2 3 1 1
2 3 2 2
.......
2 3 k k
.......
.......
.......
n 1 1 0
n 1 2 1
n 1 3 2
.......
n 1 k k-1
1 1 k 0
---------------------------
for n=3, k=2 Ans. 2 4 6 1 3 5 |
| What algo? | bsu.mmf.team | 1842. Local Roots | 10 Jun 2025 22:26 | 7 |
Finally I've solved this problem using very hard optimised Main & Lorentz's algo, and 0.405s only.
But I noticed many people solved this problem very fast and using much less memory.
What algo do you use? I doubt it's possible to speed-up Main & Lorentz or Crochemore algos so much.
Is it some alternative (like suffix tree) solution, or just some strong idea can be applied to this particular problem? Is it possible to solve it in O(n)? I use something similar with manacher algorithm with some optimization.. I use this approach:
first for every position find the answer which cover outside the string(using kmp algo) as
estimate value, and sort the estimate value in desending order, then use
bruteforce(hash+enum) to calc the answer inside the string.when estimate value <=ans break;
this program make me 0.2s AC... Thank you, but your solution is either not very fast :)
I believe there's a strict approach exists with a strict algo for this problem. My algorithm is similar to Shen Yang.But I also use exkmp to calc another two situaion.
Then the estimate value will become smaller.I got AC in 0.046s. Look up Critical Factorization Theorem Lookup Two Way algorithm for finding critical position of string. Second number is period of the string. |
