Hi! Render with bbCode.

​

This is for [url=https://codeforces.com/blog/entry/116940#:~:text=1852D]an editorial[/url].

​

You can change `topRow` and `k` in the code below.

This Asymptote code will programmatically draw a solution (if it exists)!

Scroll down a lot to change the `topRow` of the "Graph only" drawing.

​

Enjoy reading the abomination of code below. ~[url=https://artofproblemsolving.com/community/user/516122]emerald_block[/url]

​

Graph with DP:

[asy]

string topRow = "BAAABBAAB";

int k = 17;

​

string[] chars = array(topRow);

int sz = chars.length;

void drw(path p, bool b, int x, pair r) {

    draw(p,EndArrow(angle=22.5,size=4),p=b?red:black,Margin(2));

    label("\scriptsize"+string(x),r,p=b?red:black);

}

struct State {

    int l,r,v;

    void operator init(int l, int r, int v) {

        this.l = l;

        this.r = r;

        this.v = v;

    }

};

State operator+(State s, int x) {

    return State(s.l+x,s.r+x,s.v==-1?-1:s.v+x);

}

State operator#(State s, State other) {

    return State(

        s.l<other.l?s.l:other.l,

        s.r>other.r?s.r:other.r,

        s.v!=-1&&(s.v<other.l||other.r<s.v)?s.v

        :other.v!=-1&&(other.v<s.l||s.r<other.v)?other.v

        :(s.r<other.r?s.r:other.r)+1<(s.l>other.l?s.l:other.l)?(s.r<other.r?s.r:other.r)+1

        :-1

    );

}

bool operator==(State s, int x) {

    return x>=s.l&&x<=s.r&&x!=s.v;

}

​

string sngltn(int o) {

    return "\{"+string(o)+"\}";

}

string intrvl(int l, int r) {

    return "["+string(l)+","+string(r)+"]";

}

string operator+(string s, State state) {

    string res = s+intrvl(state.l,state.r);

    if (state.v!=-1) res = res+"\setminus"+sngltn(state.v);

    return res;

/*

    if (state.v==-1) return s+intrvl(state.l,state.r);

    if (state.v==state.l+1) {

        if (state.v==state.r-1) {

            return s+sngltn(state.l)+"\cup"+sngltn(state.r);

        }

        return s+sngltn(state.l)+"\cup"+intrvl(state.v+1,state.r);

    }

    return s+intrvl(state.l,state.v-1)+"\cup"+sngltn(state.r);

*/

}

​

usepackage("mathtools");

unitsize(1cm);

​

for (int i = 0; i < sz; ++i) {

    if (chars[i] == "A" || chars[i] == "B") continue;

    label(

        "The DP implementation depends on there only being $A$s and $B$s!",

    (2,1),brown);

}

if (sz == 0) {

    label(

        "Just for you, okay?",

    (2,1));

}

​

draw((2,0)--(-1,0));

for (int i = 0; i < sz; ++i) {

    draw((0,-i)--(0,-i-1)--(-1,-i-1)--(-1,-i));

    label("$"+chars[i]+"$",(-1/2,-i-1/2));

}

​

State[] dpA;

State[] dpB;

for (int i = 0; i < sz; ++i) {

    draw((2,-i)--(2,-i-1)--(0,-i-1));

    if (i == 0) {

        dpA.push(chars[i]!="A"?State(1,1,-1):State(0,0,-1));

        dpB.push(chars[i]!="B"?State(1,1,-1):State(0,0,-1));

    } else {

        State pDpA = dpA[i-1];

        State pDpB = dpB[i-1];

        dpA.push(pDpA#(pDpB+1)+(chars[i]!="A"?1:0)+(chars[i]!=chars[i-1]?1:0));

        dpB.push(pDpB#(pDpA+1)+(chars[i]!="B"?1:0)+(chars[i]!=chars[i-1]?1:0));

    }

    label("$\mathrm{dp}_A["+string(i+1)+"]="+dpA[i]+"$",(2,-i-1/4),E);

    label("$\mathrm{dp}_{\mathrlap{B}\phantom{A}}["+string(i+1)+"]="+dpB[i]+"$",(2,-i-3/4),E);

}

​

int acc = k;

string prev;

pair L = (1,1/2);

pair R = (1,-sz-1/2);

dot(R,red);

for (int i = sz-1; i >= 0; --i) {

    string choice;

    if (i == sz-1) {

        if (dpB[i]==acc) choice = "B";

        else if (dpA[i]==acc) choice = "A";

        else choice = "";

    } else if (prev == "") {

        choice = "";

    } else {

        acc -= (prev!=chars[i+1]?1:0)+(chars[i+1]!=chars[i]?1:0);

        if (dpB[i]==acc-(prev!="B"?1:0)) choice = "B";

        else choice = "A";

        acc -= (prev!=choice?1:0);

    }

    pair A = (1/2,-i-1/2);

    pair B = (1+1/2,-i-1/2);

    label("$A$",A,choice=="A"?red:black);

    label("$B$",B,choice=="B"?red:black);

    if (i != sz-1) {

        string pc = chars[i+1];

        int val = (pc!=chars[i]?1:0);

        drw(A--A+S,prev=="A"&&choice=="A",val+("A"!=pc?1:0),(3/8,-i-5/6));

        drw(B--A+S,prev=="A"&&choice=="B",val+1+("A"!=pc?1:0),(2-5/8,-i-5/6));

        drw(A--B+S,prev=="B"&&choice=="A",val+1+("B"!=pc?1:0),(5/8,-i-5/6));

        drw(B--B+S,prev=="B"&&choice=="B",val+("B"!=pc?1:0),(2-3/8,-i-5/6));

    } else {

        drw(A--R,choice=="A",0,(1/2,-i-5/6));

        drw(B--R,choice=="B",0,(2-1/2,-i-5/6));

    }

    if (i == 0) {

        drw(L--A,choice=="A",("A"!=chars[i]?1:0),(5/8,1-5/6));

        drw(L--B,choice=="B",("B"!=chars[i]?1:0),(2-5/8,1-5/6));

    }

    prev = choice;

}

if (sz == 0) {

    drw(L--R,k==0,0,(7/8,1-5/6));

    prev = k==0?"hi":"";

}

dot(L,prev!=""?red:black);

[/asy]

[verbatim=%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%][/verbatim]

Graph only:

[asy]

string topRow = "BAAABBAAB";

​

string[] chars = array(topRow);

int sz = chars.length;

void drw(path p, int x, pair r) {

    draw(p,EndArrow(angle=22.5,size=4),Margin(2));

    label("\scriptsize"+string(x),r);

}

​

unitsize(1cm);

​

if (sz == 0) {

    label(

        "Just for you, okay?",

    (0,1+1/2));

}

​

draw((0,-2)--(0,1));

for (int i = 0; i < sz; ++i) {

    draw((i,0)--(i+1,0)--(i+1,1)--(i,1));

    label("$"+chars[i]+"$",(i+1/2,1/2));

}

​

pair L = (-1/2,-1);

pair R = (sz+1/2,-1);

dot(L);

for (int i = 0; i < sz; ++i) {

    draw((i,-2)--(i+1,-2)--(i+1,0));

    pair A = (i+1/2,-1/2);

    pair B = (i+1/2,-1-1/2);

    label("$A$",A);

    label("$B$",B);

    if (i != sz-1) {

        string pc = chars[i+1];

        int val = (pc!=chars[i]?1:0);

        drw(A--A+E,val+("A"!=pc?1:0),(i+5/6,-3/8));

        drw(B--A+E,val+1+("A"!=pc?1:0),(i+5/6,-2+5/8));

        drw(A--B+E,val+1+("B"!=pc?1:0),(i+5/6,-5/8));

        drw(B--B+E,val+("B"!=pc?1:0),(i+5/6,-2+3/8));

    } else {

        drw(A--R,0,(i+5/6,-1/2));

        drw(B--R,0,(i+5/6,-2+1/2));

    }

    if (i == 0) {

        drw(L--A,("A"!=chars[i]?1:0),(-1+5/6,-5/8));

        drw(L--B,("B"!=chars[i]?1:0),(-1+5/6,-2+5/8));

    }

}

if (sz == 0) {

    drw(L--R,0,(-1+5/6,-7/8));

}

dot(R);

[/asy]

​