Форум Всеукраїнської інтернет-олімпіади NetOI


На форумі обговорюються лише питання, пов'язані з олімпіадою

Ви не зайшли.

Сторінок: 1

 

#1 2020-02-24 18:15:47

Жюри_Пасихов
Адміністратор
Зареєстрований: 2009-11-08
Повідомлень: 439

Коментарі до розв'язків задач фінального туру

Задача Dcentralization
Предполагалась в качестве "a+b"

Нетрудно видеть, что из всех ребер графа (очевидного) нужны лишь ребра, которые выходят из привлекательного города. После этого все города разбиваются на компоненты связности, внутри каждой из которых бюджет можно считать “общим”, т.к. он свободно переходит из города в город. Теперь нужно лишь посчитать для каждой компоненты связности суммарный бюджет и нацело поделить на количество отмеченных городов в этой компоненте. После этого остается лишь взять минимум из полученных сумм. 
Возможен упрощенный вариант, когда города идут в линию, а ребра есть лишь между соседами. Тогда, помимо похожего по смыслу решения (фактически, жадного) существует альтернативное, использующее бинарный поиск по ответу + жадный алгоритм, однако оно всё еще сложнее и в придумке, и в реализации
   

Код:

#include<iostream>
#include<vector>
#include<cassert>
using namespace std;

struct Solution {
    int n, m;
    vector<char> marked;
    vector<vector<int> > e;
    vector<int> money;
    vector<char> used;
    

    Solution(int n, int m) 
    :   n(n),
        m(m),
        e(n),
        marked(n, 0),
        money(n),
        used(n, 0)
        {}
    
    void mark(int i){
        marked[i] = 1;
    }
    void add_edge(int i, int j){
        if(marked[i] || marked[j])
            e[i].push_back(j),
            e[j].push_back(i);
    }
    void dfs(int v, int & cnt, long long & sum){
        if(used[v])
            return;
        sum += money[v];
        if(marked[v])
            cnt++;

        used[v] = true;
        for(int i = 0; i < e[v].size(); i++)
            dfs(e[v][i], cnt, sum);
    }

    long long get_solution(){
        long long res = 1e18;
        for(int i = 0; i < n; i++){
            int cnt = 0;
            long long sum = 0;
            dfs(i, cnt, sum);
            if(cnt != 0)
                res = min(sum/cnt, res);
        }
        return res;
    }

};


int main(){
    int n, k, m;
    cin >> n >> k >> m;
    assert(1 <= n && n <= 10000);
    assert(1 <= k && k <= n);
    assert(0 <= m && m <= min(100000, n*(n-1)/2));
    Solution S(n, m);

    int prev_marked = 0;
    for(int i = 0; i < k; i++){
        int marked;
        cin >> marked;
        assert(1 <= marked && marked <= n && prev_marked < marked);
        S.mark(marked - 1);
        prev_marked = marked;
    }
    for(int i = 0; i < n; i++){
        cin >> S.money[i];
        assert(S.money[i] <= 1000000);
    }
    for(int i = 0; i < m; i++){
        int x, y;
        cin >> x >> y;
        S.add_edge(x - 1, y - 1);
    }

    cout << S.get_solution() << std::endl;
}

Поза форумом

 

#2 2020-03-01 10:45:05

Жюри_Пасихов
Адміністратор
Зареєстрований: 2009-11-08
Повідомлень: 439

Re: Коментарі до розв'язків задач фінального туру

Коментар до розв'язку задачі  HardWay   доступний за посиланням:

https://new.netoi.org.ua/admin/modules/ … ешение.pdf

Поза форумом

 

#3 2020-11-12 19:41:10

FordPerfect
Новий користувач
Зареєстрований: 2014-11-15
Повідомлень: 30

Re: Коментарі до розв'язків задач фінального туру

Как автор задач Forum, Spiral и Status, запощу здесь решения.
Вначале примечание. Авторы задач и жюри олимпиады - это две разные (хотя и пересекающиеся) категории. И коммуникация между ними может быть довольно ограниченной.

Задача Status.
Начну с этой задачи, как наиболее удачно вписавшейся в тур.
Что слегка вселяет надежду на то, что задача близка к READY PERFECTLY.
Решение:

Код:

#include <cstdio>

int ceil_div(int x,int y)
{
    int ret=x/y;
    return ret+(ret*y<x);
}

long long solve(int HH,int HA,int HD,int HS,int MH,int MA,int MD,int MS)
{
    // If hero shows up to the duel dead, upgrade HP,
    // until he's alive. This is the only scenario where
    // we do so.
    if(HH<=0) return (1-HH)+solve(1,HA,HD,HS,MH,MA,MD,MS);
    // If the monster shows up to the duel dead, good on us.
    if(MH<=0) return 0;
    int A=HA-MD;
    int D=MA-HD;
    // If we cannot damage the monster, upgrade until we can.
    // We need to reduce its HP to 0 to win, so this is required.
    if(A<=0) return (1-A)+solve(HH,MD+1,HD,HS,MH,MA,MD,MS);
    // If the monster cannot damage us, we are good.
    if(D<=0) return 0;
    // Are we faster, than the monster?
    // Slower and equal have the same meaning for our purposes,
    // as hero needs to stay alive after defeating the monster.
    int t=(HS>MS);
    long long S=D+1;
    // If we are not faster than the monster, consider upgrading until we are.
    if(!t) S=(1-HS+MS)+solve(HH,HA,HD,MS+1,MH,MA,MD,MS);
    // If hero can win outright, we are good.
    if(ceil_div(MH,A)<ceil_div(HH,D)+t) return 0;
    int L=0,H=D;
    // Now, L points is not sufficient for victory, H points is.
    // As can_win(points) is clearly monotonic, we just
    // find the answer with a binary search.
    while(L+1<H)
    {
        int M=(L+H)/2;
        bool v=false;
        for(int i=0;i<=M;)
        {
            int a=A+i,d=D-M+i;
            int j=ceil_div(MH,a),k=ceil_div(HH,d);
            if(j<k+t) {v=true;break;}
            // We do not need to look at all possible values of Atk (or, for
            // that matter, Def), as there are only about 2*sqrt(HP)
            // reasonable values for it: as that is the number of
            // distinct values the number of turns ceil(HP/Atk) can take,
            // and for each number of turns only the lowest Atk that produces it
            // is any good.
            // It is straightforward to show that if m<sqrt(n), than the smallest number
            // such that ceil(n/k)=m is ceil(n/m).
            if(j<a)
            {
                if(j<=1) break;
                i=ceil_div(MH,j-1)-A;
            }
            else ++i;
        }
        if(v) H=M; else L=M;
    }
    return S<H?S:H;
}

long long solve_bruteforce(int HH,int HA,int HD,int HS,int MH,int MA,int MD,int MS)
{
    if(HH<=0) return (1-HH)+solve(1,HA,HD,HS,MH,MA,MD,MS);
    if(MH<=0) return 0;
    int A=HA-MD;
    int D=MA-HD;
    if(A<=0) return (1-A)+solve(HH,MD+1,HD,HS,MH,MA,MD,MS);
    if(D<=0) return 0;
    int t=(HS>MS);
    long long S=D+1;
    if(!t) S=(1-HS+MS)+solve(HH,HA,HD,MS+1,MH,MA,MD,MS);
    if(ceil_div(MH,A)<ceil_div(HH,D)+t) return 0;
    int L=0,H=D;
    for(int i=0;i<H;++i)
        for(int j=0;j<=i;++j)
            if(ceil_div(MH,A+j)<ceil_div(HH,D-i+j)+t) {H=i;break;}
    return S<H?S:H;
}

int main()
{
    int HH,HA,HD,HS,MH,MA,MD,MS;
    std::scanf("%d%d%d%d%d%d%d%d",&HH,&HA,&HD,&HS,&MH,&MA,&MD,&MS);
    std::printf("%lld",solve(HH,HA,HD,HS,MH,MA,MD,MS));
    return 0;
}

//     Some tests:
// 10 7 4 10 29 10 2 5
// 10 10 10 10 10 10 10 10
// 1 1 1 1 10 10 10 10
// 1 1 1 10 10 10 10 1
// 1 1 1 1 1 1 1 1
// 1 1 1 2 1 1 1 1
// 1 1 2 1 1 1 1 1
// 1 1 2 1 1 1 1 1
// 1 2 1 1 1 1 1 1
// 10 10 10 10 10 11 11 10
// 10 10 10 10 10 11 10 10
// 10 10 10 10 10 11 10 10
// 10 10 10 11 10 10 11 10
// 10 10 10 10 9999 9999 9999 9999
// 1 1 1 1 999999 999999 999999 999999
//     Counter-examples to "don't upgrade both Atk and Def."
// 85 39 49 38 73 98 28 76
// 911 965 248 872 916 364 942 473
// 3366 7691 1805 6043 6240 8286 6327 5605
// 24424 25384 12635 23727 24509 14704 24979 16634
//     Counter-examples to "don't upgrade both Atk and Def
//     for more than 1 turn's worth of improvement each."
// 22 33 17 19 21 28 28 23
// 50 25 26 60 85 45 11 34
// 21 16 21 21 25 29 15 20
// 155 134 134 148 135 147 130 191
// 318 409 513 635 337 893 385 835
// 7139 5356 6851 2911 7647 9547 5258 9923
//     Random tests
// 10 17 64 90 97 27 56 45
// 88 99 75 96 36 48 90 68
// 12 18 10 16 16 18 16 15
// 100 176 641 902 971 270 563 458
// 888 995 753 969 367 483 909 687
// 3366 7691 1805 6043 6240 8286 6327 5605
// 8889 9955 7535 9699 3673 4834 9095 6876
// 91141 96541 24824 87221 91619 36463 94265 47319
// 88900 99561 75361 96998 36740 48346 90957 68772
//     Max. test
// 1 1 1 1 999999999 999999999 999999999 999999999

Идея вроде довольно понятна из комментариев в коде (хотя они и на английском).
Примечание: в исходной формулировке условия допускалось HP=0, и равные Spd трактовались как одновременное действие.

Поза форумом

 

#4 2020-11-12 19:43:19

FordPerfect
Новий користувач
Зареєстрований: 2014-11-15
Повідомлень: 30

Re: Коментарі до розв'язків задач фінального туру

Задача Spiral.
Задачу, к некоторому моему удивлению, взяли на real-time тур, хотя она для него, на мой взгляд, несколько громоздкая.
Идея. Разбиваем плоскость на 4 участка (прямыми x=y и x=-y), на которых фомула имеет регулярный вид, и считаем пересечение прямоугольника с этими участками.
Исходное решение выглядело так:

Код:

#include <cstdio>

class Num
{
public:
    static const int M=1000000007;

    Num(int src)
    {
        value=src%M;
        if(value<0) value+=M;
    }

    friend inline Num operator+(Num l,Num r)
    {
        return Num(l.value+r.value);
    }
    friend inline Num operator-(Num l,Num r)
    {
        return Num(l.value-r.value);
    }
    friend inline Num operator*(Num l,Num r)
    {
        long long ret=(long long)l.value*(long long)r.value;
        ret%=M;
        return Num(int(ret));
    }

    static inline Num pow(Num a,int p)
    {
        if(p==0) return 1;
        if(a.value==0) return 0; // Only properly works for positive powers.
        p%=M-1;
        if(p<0) p+=M-1;
        Num ret=1;
        while(p)
        {
            if(p&1) ret=ret*a;
            a=a*a;
            p>>=1;
        }
        return ret;
    }
    static inline Num inv(Num src)
    {
        return Num::pow(src,-1);
    }

    friend inline Num operator/(Num l,Num r)
    {
        return l*Num::inv(r);
    }

    // Iffy syntax, with high enough precedence.
    inline Num operator[](int p) const
    {
        return Num::pow(*this,p);
    }

    inline Num &operator+=(Num r) {*this=*this+r;return *this;}
    inline Num &operator-=(Num r) {*this=*this-r;return *this;}
    inline Num &operator*=(Num r) {*this=*this*r;return *this;}
    inline Num &operator/=(Num r) {*this=*this/r;return *this;}

    inline int get_value() const {return value;}
private:
    int value;
};

// Gets value of a spiral at point (x,y):
//     +y
//      ^
//      |
//   4  3  2
//---5--0--1---> +x
//   6  7  8  9
//      |
Num get_point(int x,int y)
{
    int a=x+y;
    int b=x-y;
    // Note: the clauses can be freely reordered: if
    // a point satisfies several clauses, all produce
    // the same result.
    if(a> 0&&b>=0) return Num(x)*(4*Num(x)-3)+y;
    if(a<=0&&b<=0) return Num(x)*(4*Num(x)-1)-y;
    if(a>=0&&b<=0) return Num(y)*(4*Num(y)-1)-x;
    if(a<=0&&b>=0) return Num(y)*(4*Num(y)-3)+x;
    return 0;
}

Num solve_bruteforce(int x0,int y0,int x1,int y1)
{
    Num ret=0;
    for(int x=x0;x<=x1;++x)
        for(int y=y0;y<=y1;++y)
            ret+=get_point(x,y);
    return ret;
}

// Calculates sum of 4*y^2+A*y+x over
// all points that satisfy:
//   L<=x<=R
//   y<=H
//   y>=D+x && y>=D-x
Num sum_sector(int D,int A,int L,int R,int H)
{
    if(D-R>H||D+L>H) return 0;
    Num ret=0;
    if(D-L>H) L=D-H;
    if(D+R>H) R=H-D;
    int B,E;
    B=L,E=(R<0?R:-1);
    if(B<=E)
    {
        Num b=B,e=E,a=A,h=H,d=D;
        //for(int x=B;x<=E;++x)
        //    for(int y=D-x;y<=H;++y)
        //        ret+=4*Num(y)*Num(y)+A*Num(y)+Num(x);
        // The above double sum simplifies to:
        ret+=-4*e*d[3]/3+4*(b-1)*d[3]/3+2*e[2]*d[2]-a*e*d[2]/2+4*e*d[2]+a*(b-1)*d[2]/2-4*(b-1)*d[2]
          -2*(b-1)[2]*d[2]-(4*e[3]*d+6*e[2]*d+2*e*d)/3+(a*e[2]*d+a*e*d)/2
          -(5*e[2]*d+5*e*d)/2-(a*(b-1)*d+a*(b-1)[2]*d)/2
          +(5*(b-1)*d+5*(b-1)[2]*d)/2+(2*(b-1)*d+4*(b-1)[3]*d+6*(b-1)[2]*d)/3
          +a*e*d/2-2*e*d/3-a*(b-1)*d/2+2*(b-1)*d/3+4*e*h[3]/3-4*(b-1)*h[3]/3
          +a*e*h[2]/2+2*e*h[2]-a*(b-1)*h[2]/2-2*(b-1)*h[2]+(e[2]*h+e*h)/2
          -((b-1)*h+(b-1)[2]*h)/2+a*e*h/2+2*e*h/3-a*(b-1)*h/2-2*(b-1)*h/3
          +(e[4]+2*e[3]+e[2])/3-(2*a*e[3]+3*a*e[2]+a*e)/12+(2*e[3]+3*e[2]+e)/2
          -(a*e[2]+a*e)/4+(5*e[2]+5*e)/6-(b+2*(b-1)[3]+3*(b-1)[2]-1)/2
          +(a*(b-1)+2*a*(b-1)[3]+3*a*(b-1)[2])/12+(a*(b-1)+a*(b-1)[2])/4
          -(5*(b-1)+5*(b-1)[2])/6-((b-1)[4]+2*(b-1)[3]+(b-1)[2])/3;
    }
    B=(L>0?L:0),E=R;
    if(B<=E)
    {
        Num b=B,e=E,a=A,h=H,d=D;
        //for(int x=B;x<=E;++x)
        //    for(int y=D+x;y<=H;++y)
        //        ret+=4*Num(y)*Num(y)+A*Num(y)+Num(x);
        // The above double sum simplifies to:
        ret+=-4*e*d[3]/3+4*(b-1)*d[3]/3-2*e[2]*d[2]-a*e*d[2]/2+a*(b-1)*d[2]/2+2*(b-1)[2]*d[2]
          -(4*e[3]*d+6*e[2]*d+2*e*d)/3-(a*e[2]*d+a*e*d)/2+(3*e[2]*d+3*e*d)/2
          +(a*(b-1)*d+a*(b-1)[2]*d)/2-(3*(b-1)*d+3*(b-1)[2]*d)/2
          +(2*(b-1)*d+4*(b-1)[3]*d+6*(b-1)[2]*d)/3+a*e*d/2-2*e*d/3-a*(b-1)*d/2
          +2*(b-1)*d/3+4*e*h[3]/3-4*(b-1)*h[3]/3+a*e*h[2]/2+2*e*h[2]-a*(b-1)*h[2]/2
          -2*(b-1)*h[2]+(e[2]*h+e*h)/2-((b-1)*h+(b-1)[2]*h)/2+a*e*h/2+2*e*h/3
          -a*(b-1)*h/2-2*(b-1)*h/3-(e[4]+2*e[3]+e[2])/3-(2*a*e[3]+3*a*e[2]+a*e)/12
          +(2*e[3]+3*e[2]+e)/6+(a*e[2]+a*e)/4+(e[2]+e)/6
          -(b+2*(b-1)[3]+3*(b-1)[2]-1)/6-(b+(b-1)[2]-1)/6
          +(a*(b-1)+2*a*(b-1)[3]+3*a*(b-1)[2])/12-(a*(b-1)+a*(b-1)[2])/4
          +((b-1)[4]+2*(b-1)[3]+(b-1)[2])/3;
    }
    return ret;
}

Num solve(int x0,int y0,int x1,int y1)
{
    Num ret=0;
    if(x1<x0||y1<y0) return 0;
    // We split all points into 4 sectors as follows:
// BBBBBBB
// CBBBBBA
// CCBBBAA
// CCC*AAA
// CCDDDAA
// CDDDDDA
// DDDDDDD
    // And take sums over individual sectors.
    // Note: we cover (0,0) potentially twice (B and D), but since its
    // value is 0, the sum is the same.
    ret+=sum_sector(1,-3, y0, y1, x1)-sum_sector(1,-3, y0, y1,x0-1); // [A]
    ret+=sum_sector(0,-1,-x1,-x0, y1)-sum_sector(0,-1,-x1,-x0,y0-1); // [b]
    ret+=sum_sector(1, 1,-y1,-y0,-x0)-sum_sector(1, 1,-y1,-y0,-x1-1);// [C]
    ret+=sum_sector(0, 3, x0, x1,-y0)-sum_sector(0, 3, x0, x1,-y1-1);// [D]
    return ret;
}

int main()
{
    int x0,y0,x1,y1;
    std::scanf("%d%d%d%d",&x0,&y0,&x1,&y1);
    std::printf("%d",(solve(x0,y0,x1,y1)+Num(x1-x0+1)*Num(y1-y0+1)).get_value());
    return 0;
}

Формула ( sum_sector() ) была получена в Maxima, и на туре такое выводить руками несколько нереалистично.
Но на туре можно реализовать примерно такое:

Код:

// Faulhaber formulas.
// See https://en.wikipedia.org/wiki/Faulhaber%27s_formula .

Num P0(Num n) {return n+1;}
Num P1(Num n) {return n*(n+1)/2;}
Num P2(Num n) {return n*(2*n+1)*(n+1)/6;}
Num P3(Num n) {return n*n*(n+1)*(n+1)/4;}

Num sum0(Num l,Num r) {return P0(r)-P0(l-1);}
Num sum1(Num l,Num r) {return P1(r)-P1(l-1);}
Num sum2(Num l,Num r) {return P2(r)-P2(l-1);}
Num sum3(Num l,Num r) {return P3(r)-P3(l-1);}

// Alternative, shorter version, with less explicit formula.
// Also, about 5 times faster.
Num sum_sector(int D,int A,int L,int R,int H)
{
    if(D-R>H||D+L>H) return 0;
    Num ret=0;
    if(D-L>H) L=D-H;
    if(D+R>H) R=H-D;
    int B,E;
    B=L,E=(R<0?R:-1);
    if(B<=E)
    {
        Num b=B,e=E,a=A,h=H,d=D;
        //for(int x=B;x<=E;++x)
        //    for(int y=D-x;y<=H;++y)
        //        ret+=4*Num(y)*Num(y)+A*Num(y)+Num(x);
        // The inner sum simplifies to:
        // (8*x^3-3*(a+8*d-6)*x^2+(a*(6*d-3)+24*d^2-30*d+6*h+10)*x-(d-h-1)*(d*(3*a+8*h-4)+h*(3*a+8*h+4)+8*d^2))/6
        // Note: for d=0 and d=1 (our values) formulas are shorter:
        //     d=0: (8*x^3-3*(-6+a)*x^2+(10-3a+6*h)*x-((-1-h)*h*(4+3*a+8*h)))/6
        //     d=1: (8*x^3-3*(2+a)*x^2+(4+3*a+6*h)*x+h*(4+3*a+8*h+h*(4+3*a+8*h)))/6
        // We then proceed to sum individual terms in x via functions above:
        ret+=(
            8*sum3(b,e)
            -3*(a+8*d-6)*sum2(b,e)
            +(a*(6*d-3)+24*d*d-30*d+6*h+10)*sum1(b,e)
            -(d-h-1)*(d*(3*a+8*h-4)+h*(3*a+8*h+4)+8*d*d)*sum0(b,e))/6;
    }
    B=(L>0?L:0),E=R;
    if(B<=E)
    {
        Num b=B,e=E,a=A,h=H,d=D;
        //for(int x=B;x<=E;++x)
        //    for(int y=D+x;y<=H;++y)
        //        ret+=4*Num(y)*Num(y)+A*Num(y)+Num(x);
        // The inner sum simplifies to:
        // (-8*x^3-3*(a+8*d-2)*x^2+(a*(3-6*d)-24*d^2+18*d+6*h+2)*x-(d-h-1)*(d*(3*a+8*h-4)+h*(3*a+8*h+4)+8*d^2))/6
        // Note: for d=0 and d=1 (our values) formulas are shorter:
        //     d=0: (-8*x^3-3*(-2+a)*x^2+(2+3*a+6*h)*x-((-1-h)*h*(4+3*a+8*h)))/6
        //     d=1: (-8*x^3-3*(6+a)*x^2+(-4-3*a+6*h)*x+h*(4+3*a+8*h+h*(4+3*a+8*h)))/6
        // We then proceed to sum individual terms in x via functions above:
        ret+=(
            -8*sum3(b,e)
            -3*(a+8*d-2)*sum2(b,e)
            +(a*(3-6*d)-24*d*d+18*d+6*h+2)*sum1(b,e)
            -(d-h-1)*(d*(3*a+8*h-4)+h*(3*a+8*h+4)+8*d*d)*sum0(b,e))/6;
    }
    return ret;
}

Это уже более-менее реализуемо, хотя и всё-равно тяжеловесно.
Причём, алгоритмически задача несложная - идея незатейлива, как топорище. Но реализация довольно объёмная и требует аккуратности.

Поза форумом

 

#5 2020-11-12 20:16:07

FordPerfect
Новий користувач
Зареєстрований: 2014-11-15
Повідомлень: 30

Re: Коментарі до розв'язків задач фінального туру

Задача Forum.
Эффект от задачи не особо удачный, мои извинения участникам.
Задача задумывалась как несколько провокационная, для "оптимизируйте до упора".

Решение.
Для маленьких K есть явная формула (https://latex.codecogs.com/png.latex?%5Cinline%203%20%5Ccdot%202%5EK%20-%202), чего, впрочем, авторский код не делает.
Для больших K ответ N.
Соответственно, интересны только K порядка log2(N).
Для них мы делаем практически ровно то, что сказано в условии задачи - обход дерева достижимых страниц, запоминая посещённые в битовом массиве (2*10^8 бит вполне помещается в память).
Сложность O(2^K) - того же порядка что и сам ответ. 2^K, а не 4^K потому, что легко показать что достаточно вначале сделать все "половинные" переходы, а только потом все +1/-1.

А есть второе решение, которое асимптотически ничем не лучше, но примерно в 6 раз быстрее.
Вместо самых нижних (глубоких) уровней мы делаем соответствующее количество полных проходов по массиву, обрабатывая страницы по 64 за раз с помощью битовых операций.
Половинные переходы - использование (де)кодирования Мортона. Его можно загуглить или (при некотором знакомстве с битхаками) вывести самому.
Участникам, скорее всего, неочевидно, что вообще имеет смысл заморачиваться.

Но, 6x - это константа за которую, по винницким правилам, вполне имеет смысл бороться.

А потом задачу (к моему удивлению) взяли на real-time тур. И эксперимент получился несколько жёстче, чем задумывалось.
Код:

Код:

#include <cstdio>
#include <cstring>
#include <ctime>
#include <cmath>

static const int MAXN=200000000;

typedef unsigned long long ui64;

ui64 T[2][MAXN/64+500];

int A;

void dfs1(int N,int K,int i,int d)
{
    if(A==N) return;
    ui64 x=(i>>6)+4,y=1ull<<(i&63);
    if(T[K&1][x]&y); else {++A;T[K&1][x]|=y;}
    if(d==K) return;
    if(d==0) dfs1(N,K,N-1,d+1);
    if(i>0) dfs1(N,K,i-1,d+1);
    if(i<N-1) dfs1(N,K,i+1,d+1);
    dfs1(N,K,i>>1,d+1);
    dfs1(N,K,(i+N)>>1,d+1);
}

// We will do no worse, if we do
// all halfway moves first, and +1, -1
// after that. Also sequence should
// only contain either +1 or -1 moves.
void dfs2(int N,int K,int i,int d)
{
    if(A==N) return;
    for(int j=i-(K-d);j<=i+(K-d);++j)
    {
        if(j<0||j>=N) continue;
        ui64 x=(j>>6)+4,y=1ull<<(j&63);
        if(T[K&1][x]&y); else {++A;T[K&1][x]|=y;}
    }
    if(d==K) return;
    if(d==0) dfs2(N,K,N-1,d+1);
    dfs2(N,K,i>>1,d+1);
    dfs2(N,K,(i+N)>>1,d+1);
}

void pass_individual(int N,int k)
{
    const ui64 *src=T[k&1]+4;
    ui64 *dst=T[!(k&1)]+4;
    #define GET_BIT(i) ((src[(i)>>6]>>((i)&63))&1)
    #define SET_BIT(i,b) (dst[(i)>>6]|=ui64(b)<<((i)&63)) // Conditionally set, not copy.
    for(int i=0;i<N;++i)
        if(GET_BIT(i))
        {
            if(i>0) SET_BIT(i-1,1);
            if(i<N-1) SET_BIT(i+1,1);
            SET_BIT(i>>1,1);
            SET_BIT((i+N)>>1,1);
        }
    if(k==0) SET_BIT(N-1,1);
    #undef GET_BIT
    #undef SET_BIT
}

void pass_bitwise(int N,int k)
{
    int n=(N+63)>>6;
    const ui64 *src=T[k&1]+4;
    ui64 *dst=T[!(k&1)]+4;
    // Turns 64-bit integer [b0,b1,...,b63]
    // into [(b0|b1),(b2|b3),...,(b62|b63),0,...,0].
    // Almost the same as inverse of Morton code:
    // https://stackoverflow.com/questions/4909263/how-to-efficiently-de-interleave-bits-inverse-morton
    // https://fgiesen.wordpress.com/2009/12/13/decoding-morton-codes/
    #define PACK_BITS(t) \
        (t)=((t)|((t)>> 1))&0x5555555555555555ull;\
        (t)=((t)|((t)>> 1))&0x3333333333333333ull;\
        (t)=((t)|((t)>> 2))&0x0F0F0F0F0F0F0F0Full;\
        (t)=((t)|((t)>> 4))&0x00FF00FF00FF00FFull;\
        (t)=((t)|((t)>> 8))&0x0000FFFF0000FFFFull;\
        (t)=((t)|((t)>>16))&0x00000000FFFFFFFFull;
    for(int i=0;i<n;++i)
    {
        // Process 64 pages at once.
        // Namely, find what pages the [i*64 .. i*64+63] affects.

        if(ui64 c=src[i])
        {
            // Copy (already reachable).
            dst[i]|=c;
            // Reach via r <- r-1 and r <- r+1 navigation.
            dst[i]|=(c>>1)|(c<<1);
            dst[i-1]|=c<<63;
            dst[i+1]|=c>>63;
            // Reach via r <- floor((0+r)/2) navigation.
            ui64 t=c;
            PACK_BITS(t);
            dst[i>>1]|=t<<(32*(i&1));
            // Reach via r <- ceil((r+(N-1))/2) navigation.
            // Bits b0,b1,...,b63 map either to (b0|b1),...,(b62|b63)
            // or b0,(b1|b2),...,(b61|b62),b63, depending on parity of N.
            t=(c>>(N&1));
            PACK_BITS(t);
            t=(t<<(N&1))|(c&1);
            int j=(64*i+N)>>1;
            int x=j>>6,y=j&63;
            dst[x]|=t<<y;
            dst[x+1]|=(t>>1)>>(63-y);
        }
    }
    #undef PACK_BITS
    // Reach via r <- N-1 navigation.
    if(k==0) dst[(N-1)>>6]|=1ull<<((N-1)&63);
    // Mask bits outside [0..N-1].
    dst[-1]=0;
    if(((N-1)&63)<63) dst[(N-1)>>6]&=(1ull<<(((N-1)&63)+1))-1;
    dst[((N-1)>>6)+1]=0;
}

int count_set_bits(int N,int K)
{
    int ret=0;
    for(int i=0;i<N/64+1;++i)
    {
        //ret+=__builtin_popcountll(T[K&1][i+4]);
        // Number of bits set in an integer, aka population count.
        // See: https://graphics.stanford.edu/~seander/bithacks.html
        ui64 b=T[K&1][i+4];
        b-=(b>>1)&0x5555555555555555ull;
        b=(b&0x3333333333333333ull)+((b>>2)&0x3333333333333333ull);
        b=(b+(b>> 4))&0x0F0F0F0F0F0F0F0Full;
        b=(b+(b>> 8))&0x00FF00FF00FF00FFull;
        b=(b+(b>>16))&0x0000FFFF0000FFFFull;
        b=(b+(b>>32))&0x00000000FFFFFFFFull;
        ret+=(int)b;
    }
    return ret;
}

int solve1x(int N,int K)
{
    A=0;
    dfs1(N,K,0,0);
    return A;
}

int solve1t(int N,int K)
{
    A=0;
    dfs2(N,K,0,0);
    return A;
}

int solve2i(int N,int K)
{
    T[0][4]=1;
    int ret=1;
    for(int k=0;k<K;++k)
    {
        pass_individual(N,k);
        ret=count_set_bits(N,k+1);
        // Early-out.
        if(ret==N) break;
    }
    return ret;
}

int solve2b(int N,int K)
{
    T[0][4]=1;
    int ret=1;
    for(int k=0;k<K;++k)
    {
        pass_bitwise(N,k);
        ret=count_set_bits(N,k+1);
        // Early-out.
        if(ret==N) break;
    }
    return ret;
}

int solve3(int N,int K)
{
    int M=0;
    int ret=1;
    // For small K>1 solve1t() is faster than solve2b().
    // Guess the threshold, and start pass()'es from there.
    // Constants are empirical.
    for(int i=0;i<=K&&2000*(1ull<<i)<N*(4ull*i+1);++i) M=i;
    ret=solve1t(N,M);
    if(M==K) return A;
    for(int k=M;k<K;++k)
    {
        pass_bitwise(N,k);
        ret=count_set_bits(N,k+1);
        // Early-out.
        if(ret==N) break;
    }
    return ret;
}

int main()
{
    int N,K;
    std::scanf("%d%d",&N,&K);
    std::printf("%d",solve3(N,K));
    return 0;
}

#if 0
Timings are in μs.
          N|          K|     Answer|  solve1x()|  solve1t()|  solve2i()|  solve2b()|   solve3()
-----------+-----------+-----------+-----------+-----------+-----------+-----------+-----------
       1000|          0|          1|         1 |         1 |         0 |         1 |         1
       1000|          1|          4|         1 |         1 |         1 |         1 |         0
       1000|          2|         10|         1 |         1 |         2 |         1 |         1
       1000|          3|         22|         2 |         2 |         4 |         1 |         1
       1000|          4|         46|         3 |         1 |         5 |         1 |         1
       1000|          5|         94|        23 |         2 |        19 |         1 |         1
       1000|          6|        190|        20 |         3 |         8 |         2 |         2
       1000|          7|        381|        75 |         5 |        11 |         2 |         2
       1000|          8|        724|       305 |        10 |        30 |         3 |         2
       1000|          9|       1000|      1312 |        19 |        26 |         2 |         2
       1000|         10|       1000|       844 |        10 |        26 |         2 |         2
    1000000|          1|          4|         1 |         1 |       971 |        53 |         1
    1000000|          2|         10|         1 |         1 |      2082 |        97 |         1
    1000000|          3|         22|         2 |         1 |      2994 |       164 |         1
    1000000|          4|         46|         3 |         2 |      4146 |       237 |         2
    1000000|          5|         94|         7 |         2 |      5285 |       265 |         2
    1000000|          6|        190|        21 |         3 |      7503 |       552 |         5
    1000000|          5|         94|        11 |         2 |      8231 |       259 |         3
    1000000|          8|        766|       717 |        16 |      8289 |       442 |        10
    1000000|          9|       1534|      1875 |        30 |      9247 |       501 |        17
    1000000|         10|       3070|      5408 |        35 |     10809 |       604 |        32
    1000000|         11|       6142|     27268 |        64 |     12155 |      1113 |       115
    1000000|         12|      12286|     94130 |       131 |     12484 |       705 |       125
    1000000|         13|      24574|    336740 |       284 |     13804 |       825 |       251
    1000000|         14|      49150|   1348465 |       504 |     14904 |       966 |       502
    1000000|         15|      98302|  too long |       989 |     17199 |      1233 |       715
    1000000|         16|     196603|  too long |      1993 |     19113 |      1517 |      1209
    1000000|         17|     391785|  too long |      4874 |     30730 |      1875 |      1503
    1000000|         18|     737441|  too long |      8759 |     30131 |      1916 |      1522
    1000000|         19|    1000000|  too long |     15906 |     37149 |      2100 |      1643
    1000000|         20|    1000000|  too long |      5608 |     36492 |      3737 |      2858
   50000000|          0|          1|         1 |         1 |         1 |         1 |         1
   50000000|          1|          4|         1 |         1 |     52442 |      3220 |         1
   50000000|          2|         10|         1 |         1 |    105245 |      5898 |         1
   50000000|          4|         46|         4 |         2 |    215578 |     15269 |         2
   50000000|          6|        190|        24 |         4 |    319038 |     19049 |         5
   50000000|          8|        766|       352 |        12 |    431799 |     24012 |        14
   50000000|         10|       3070|      5278 |        58 |    533763 |     29579 |        45
   50000000|         12|      12286|     82912 |       258 |    622777 |     34729 |       170
   50000000|         14|      49150|   1285825 |       798 |    731918 |     42456 |       825
   50000000|         16|     196606|  too long |      3487 |    867185 |     48619 |      3098
   50000000|         18|     786430|  too long |     13608 |    981536 |     57137 |     13025
   50000000|         20|    3145726|  too long |     49122 |   1105846 |     76962 |     52590
   50000000|         24|   44008624|  too long |    758976 |  too long |    119740 |    135709
   50000000|         28|   50000000|  too long |    977684 |  too long |    126388 |    140385
#endif

Поза форумом

 

 

Сторінок: 1

Нижній колонтитул

Powered by Likt
© Copyright 2002–2009 Likt