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]
Hey, it looks like you're using a mobile phone or small device! TeXeR works best on a larger screen, so please visit this page from a desktop or tablet.
Enter your LaTeX code in the editor panel on the left.When you are ready to compile your document, click one of the options at the top.
Image: Renders as a PNG image. Suitable for short equations. Hint: Use Ctrl-Enter to recompile an image after making changes.
bbCode: Render with bbCode. This is similar to writing posts in the AoPS community or on your AoPS blog. You can use this to test your message before posting to the forum or your blog. bbCode rendering auto-updates if you stop typing for a short period of time.
MathJax: Render the document with MathJax, a client side LaTeX compiler. MathJax rendering auto-updates if you stop typing for a short period of time. MathJax does not support Asymptote.
PDF: Render document as a PDF file. You must have a PDF viewer to view the compiled document.