Did anybody get AC with the MaxFlow algorithm?

4
2 3 2 11.
.
2 3 0 10, 4 3 0 19.
.

4
2 0 0 47, 3 17 17 25, 4 0 0 38.
1 17 17 31, 3 0 0 23, 4 0 0 96.
1 0 0 96, 2 0 0 48, 4 17 17 91.
.
=
69
2 0, 3 17, 4 1.
1 18, 3 0, 4 0.
1 0, 2 0, 4 17.
.


8
.
1 0 0 39, 5 13 13 21.
5 0 0 87, 8 41 41 92.
5 38 38 85.
6 41 41 14, 8 10 10 49.
2 10 10 69, 3 41 41 58, 4 0 0 73.
6 3 3 59.
.
=
49
.
1 0, 5 13.
5 0, 8 41.
5 38.
6 40, 8 11.
2 10, 3 41, 4 0.
6 3.
.

Edited by author 16.06.2008 04:40

//#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 = 5;
int sz[2][maxn];
bool how[maxn];
int pos1[maxn], pos2[maxn];

bool check_intersection () {
    bool check = true;
    fo(i, 5) {
        fo(j, i) {
            check = false;
            if (pos1[i] + sz[how[i]][i] <= pos1[j]) check = true;
            if (pos1[j] + sz[how[j]][j] <= pos1[i]) check = true;
            if (pos2[i] + sz[!how[i]][i] <= pos2[j]) check = true;
            if (pos2[j] + sz[!how[j]][j] <= pos2[i]) check = true;
            if (!check) re false;
        }
    }
    re true;
}

bool check_area () {
    int x = -1, y = -1;
    fo(i, 5) {
        x = max(x, pos1[i] + sz[how[i]][i]);
        y = max(y, pos2[i] + sz[!how[i]][i]);
    }
    int s1 = 0, s2 = x * y;
    fo(i, 5) s1 += sz[0][i] * sz[1][i];
    re s1 == s2;
}

bool major_check() {
    bool ans = check_area() && check_intersection();
    re ans;
}

vector <pair <ii, bool> > v;

bool f (int mask) {
    if (__builtin_popcount(mask) == 5) re major_check();
    fo(a, 5) {
        if (((1 << a) & mask) == 0) {
            fo(q, 2) {
                how[a] = q;
                fo(i, v.size()) {
                    if (v[i].se) continue;
                    ii j = v[i].fi;
                    v[i].se = true;
                    v.pb(mp(mp(j.fi + sz[how[a]][a], j.se), false));
                    v.pb(mp(mp(j.fi, j.se + sz[!how[a]][a]), false));
                    pos1[a] = j.fi;
                    pos2[a] = j.se;
                    if (f(mask | (1 << a))) re true;
                    v[i].se = false;
                    v.pop_back();
                    v.pop_back();
                }
            }
        }
    }
    re false;
}

int main() {
    fo(i, 5) fo(j, 2) cin >> sz[j][i];
    v.eb(mp(0, 0), 0);
    if (f(0)) cout << "YES" << endl;
    else cout << "NO" << endl;
}

This problem is very easy.
I use idea similar dp.

Edited by author 30.05.2018 19:11

https://e-maxx-eng.appspot.com/string/prefix-function.html
https://ru.coursera.org/learn/algorithms-on-strings/lecture/exytr/prefix-function
https://brilliant.org/wiki/knuth-morris-pratt-algorithm/
https://stackoverflow.com/questions/13792118/kmp-prefix-table

GooD LucK!!!

I used an O(n*n) method and got TLE#9. Does anyone know of any O(n) method. I actually checked every cyclic shift to see if it is a valid expression.

Instead of "if you enemy..." it should be "if your enemy...".

The problem is very easy. If you solved every geometry problem up to this one you should be able to solve it easily, so you might want to stop reading this.
The axis of symmetry can be drawn in 2 places: through a pair of opposite point or through a pair of midpoints of opposite segments. Why only the midpoints? Because when you "fold" the figure your points must go one ever the other. If the distance is not equal, this is impossible(hint 1).
M A N
__.__
| \  \
|  \  \
|___\__\
      B
M is the top-left point
N is the top-right point
This figure for example. A and B are the midpoints. But this is clearly not an axis of symmetry. After the folding, the top-left point will go above the top-right point.
After the folding, the angle relative to the axis of symmetry will be the same. This is a midpoint. The angle with the center in A for example must have 180 degrees;
angle(MAB) + angle(NAB) = 180
angle(MAB) = angle(NAB)
x + x = 180
x = 90
It is now clear that the vector MN must be perpendicular on the vector AB(hint 2)
I think this is more that enough for you to solve the problem/
Good luck!

Edited by author 27.05.2018 15:16

Edited by author 27.05.2018 15:17

x[n] = J[n]/2^(n-1), J[n] - Jacobsthal number and J[n] = (2^n - (-1)^n)/3.

https://en.wikipedia.org/wiki/Jacobsthal_number

Help! What's wrong with my code?


#include <bits/stdc++.h>
#define forn( i, n )    for( int i = 0; i < n; i ++ )

using namespace std;

int main() {
   int qq[10000];
   int k, l; double m , n;
   l = 0;
   cin >> k >> n;
   forn( i , n)
     cin >> qq[i];
   forn( i, k+1 ){
     forn( j , n)
       if (qq[j] == i)  l = l+1;
    if ( i != 0 ) {
     m = (l / n * 100);
     l = (int) round(m*100)/100;
     if ( l - m == 0)
       cout << round(m*100)/100 << ".00%" << endl;
     else
       cout << round(m*100)/100 << "%" << endl;
     l = 0;
    }
     }
return 0;
}

//#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 + 10;
int a[maxn], b[maxn];

int main() {
    int n, m;
    cin >> n;
    fo(i, n) cin >> a[i];
    int x, pos, ans;
    cin >> m;
    fo(i, m) {
        cin >> x;
        x = 10000 - x;
        ans = (int)1e9;
        pos = lower_bound(a, a + n, x) - a;
        for (int i = max(0, pos - 1), end = min(n - 1, pos + 1); i <= end; ++i) ans = min(ans, abs(x - a[i]));
        if (!ans) {
            cout << "YES\n";
            re 0;
        }
    }
    cout << "NO\n";
    re 0;
}

#include <stdio.h>

int main(){
    int t=0,n=0,i=0,cont=0;
    int a[65535];
    for(i=0;i<1000;++i){
        a[i]=1;
        t=cont;
        while(cont!=0){
            a[i+cont]=0;
            --cont;
        }
        cont=t;
        i=i+cont;
        ++cont;
    }
    scanf("%d",&n);
    while(n!=0){
        scanf("%d",&t);
        printf("%d\n",a[t-1]);
        --n;
    }
    return(0);
}

using namespace std;
#include<iostream>
#include<stdio.h>
#include<algorithm>
long cnt=0;
long heapsize;
long heapsize1;
void heapsort(struct st a[]);
void buildmaxheap(struct st a[]);
void maxheapify(struct st a[],long index);
long left(long a);
long right(long a);
struct st
{
    long serial;
    long f;
    long l;
};


int main()
{
    long n;
    scanf("%ld",&n);
    long s1;
    long s2;

    struct st* a=new struct st[n+1];
    heapsize=n;
    for(long i=1;i<n+1;i++)
    {
     cnt++;
     a[i].serial=cnt;
     scanf("%ld",&s1);
     getchar();
     scanf("%ld",&s2);
     a[i].f=s1;
     a[i].l=s2;
    }
    heapsort(a);
    for(long i=n;i>0;i--)
    {
        cout<<a[i].f<<" "<<a[i].l<<endl;
    }
}
void heapsort(struct st a[])
{
    buildmaxheap(a);
    for(long i=heapsize;i>=2;i--)
    {
        swap(a[i],a[1]);
        heapsize1--;
        maxheapify(a,1);
    }


}
void buildmaxheap(struct st a[])
{
    heapsize1=heapsize;
   for(long i=heapsize/2;i>=1;i--)
   {
       maxheapify(a,i);
   }
}
void maxheapify(struct st a[],long index)
{
    long l1=left(index);
    long r1=right(index);
    long largest;
    if(l1<=heapsize1&&a[l1].l>=a[index].l)
    {
        if(a[l1].l==a[index].l)
        {
            if(a[l1].serial<a[index].serial)
                largest=l1;
        }
         else
                largest=l1;

    }

    else
        largest=index;
    if(r1<=heapsize1&&a[r1].l>=a[largest].l)
    {
        if(a[r1].l==a[largest].l)
        {
            if(a[r1].serial<a[largest].serial)
                largest=r1;
        }
         else
                largest=r1;

    }
    if(largest!=index)
    {
        swap(a[largest],a[index]);
        maxheapify(a,largest); //maintaining property
    }
}
long left(long a)
{
    return 2*a;
}
long right(long a)
{
    return 2*a+1;
}

Hello,
I'm trying to solve this problem a couple of days. But always get wrong answer 4. I don't know what is the problem may be and this makes me feel badly. Could somebody help me or show the 4th test for me, please?
I can send my code if it's needed.

Please, ban user (id 219673) to make a posts on the forum. Also delete all his posts on the forum if it possible.

Edited by author 20.05.2018 17:29

Had WA 16 because i checked if the plates can fit with > instead of >= (the upper part of the plates can touch.)

Also, if the height of the box is smaller than the plates, and the plates margin fall out of the box, don't forget that their full margins can't touch each other!
Example test:
4 8 1
1 3
1 3
2

Answer: NO

import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int a,n=0;
        a = in.nextInt();
        a = (int) (Math.pow(1,a)+Math.pow(2,a)+Math.pow(3,a)+Math.pow(4,a));
        int b[] = new int[11000];
        while(a>0){
            if(a%10==0)n++;
            else break;
            a = a/10;
        }
        System.out.print(n);
    }
}

I got ac on this problem using heuristic. Please, add anti-heuristic tests.

Probably dp is possible
Looks like to dp here one should invent something non-trivial because of relatively large n.

Edited by author 04.08.2017 10:43