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

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 of this problem, where you need to output all the roads

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?

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

My AC program prints wrong answer on this test:
9
6 7 1 6
1 8 2 6 5 1
1 2
1 3
2 4
2 5
3 4
4 6
5 6

Correct answer is NO

#include <iostream>

using namespace std;

int main()
{
    int a;
    cin>>a;
    if (a>=7)
        cout<<"Yes";
    if (a<7)
        cout<<"No";
    return 0;
}

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]?

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

input:
1000000000000000000

output:
524638269999999991

optimized search + cross product)

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 use DP.

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)

see what your program outputs for an integer answer
ps it should output .00

посмотрите, что выводит ваша программа при целом ответе
ps она должна выводить .00

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

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)?

1 5
/\/\X
.\X\\
ans: 4

#include <bits/stdc++.h>
using namespace std;

int cal(int x){
    int ret = 0;
    while (x > 0){
        ret += x % 10;
        x /= 10;
    }
    return ret;
}

bool lucky(int x, int mm){
    int a = x / mm;
    int b = x % mm;
    if (cal(a) == cal(b)) return true;
    return false;
}

int main(){
    int n;
    cin >> n;
    int nn = round(pow(10, n)) - 1;
    int mm = round(pow(10, n / 2));
    int tot = 0;
    for (int i = 0; i <= nn; i++){
        if (lucky(i, mm)) tot++;
    }
    cout << tot << endl;
}

if your code is simple and fast enough, brute force can work.

what is wrong with my code:

#include <iostream>
#include <algorithm>
#include <climits>
#include <string>
#include <cstring>
#include <cmath>
#include <vector>
#include <stack>
#include <map>
#include <set>
#include <iomanip>
#include <unordered_map>
#define ll long long
#define fri(a, b) for (ll i = a; i < b; i++)
#define frj(a, b) for (ll j = a; j < b; j++)
#define frk(a, b) for (int k = a; k < b; k++)
#define frh(a, b) for (int h = a; h < b; h++)
#define frz(a, b) for (int z = a; z < b; z++)
#define rfri(a, b) for (int i = a; i >= b; i--)
#define rfrj(a, b) for (int j = a; j >= b; j--)
#define yes cout << "YES" << "\n";
#define no cout << "NO" << "\n";
#define fast                          \
    ios_base::sync_with_stdio(false); \
    cin.tie(NULL);                    \
    cout.tie(NULL);
const int mod=100000007;
using namespace std;
ll dp[50][1005];

ll func(ll n,ll s){
  if(dp[n][s] != -1) return dp[n][s];
  if(s == 0) return 1;
  if(n == 0){
    if(s == 0) return 1;
    else return 0;
  }
  ll ans = 0;
  fri(0,10){
    if((s - i) >= 0) ans = (ans + func(n-1,s-i)) ;
  }
  return dp[n][s] = ans;
}

int main() {
    fast
    ll T = 1;
    // cin >> T;

    frz(0,T){
      ll n,s;
      cin >> n >> s;
      memset(dp,-1,sizeof(dp));
      if(s%2) cout << 0 << "\n";
      else {
        ll ans = func(n,s/2);
        cout << (ans*ans) << "\n";
      }
    }
}