Plan ahead for the next school year. Schedule your class today!

 
1
Hi! Render with bbCode.
2
3
This is for [url=https://codeforces.com/blog/entry/116940#:~:text=1852D]an editorial[/url].
4
5
You can change `topRow` and `k` in the code below.
6
This Asymptote code will programmatically draw a solution (if it exists)!
7
Scroll down a lot to change the `topRow` of the "Graph only" drawing.
8
9
Enjoy reading the abomination of code below. ~[url=https://artofproblemsolving.com/community/user/516122]emerald_block[/url]
10
11
Graph with DP:
12
[asy]
13
string topRow = "BAAABBAAB";
14
int k = 17;
15
16
string[] chars = array(topRow);
17
int sz = chars.length;
18
void drw(path p, bool b, int x, pair r) {
19
    draw(p,EndArrow(angle=22.5,size=4),p=b?red:black,Margin(2));
20
    label("\scriptsize"+string(x),r,p=b?red:black);
21
}
22
struct State {
23
    int l,r,v;
24
    void operator init(int l, int r, int v) {
25
        this.l = l;
26
        this.r = r;
27
        this.v = v;
28
    }
29
};
30
State operator+(State s, int x) {
31
    return State(s.l+x,s.r+x,s.v==-1?-1:s.v+x);
32
}
33
State operator#(State s, State other) {
34
    return State(
35
        s.l<other.l?s.l:other.l,
36
        s.r>other.r?s.r:other.r,
37
        s.v!=-1&&(s.v<other.l||other.r<s.v)?s.v
38
        :other.v!=-1&&(other.v<s.l||s.r<other.v)?other.v
39
        :(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
40
        :-1
41
    );
42
}
43
bool operator==(State s, int x) {
44
    return x>=s.l&&x<=s.r&&x!=s.v;
45
}
46
47
string sngltn(int o) {
48
    return "\{"+string(o)+"\}";
49
}
50
string intrvl(int l, int r) {
51
    return "["+string(l)+","+string(r)+"]";
52
}
53
string operator+(string s, State state) {
54
    string res = s+intrvl(state.l,state.r);
55
    if (state.v!=-1) res = res+"\setminus"+sngltn(state.v);
56
    return res;
57
/*
58
    if (state.v==-1) return s+intrvl(state.l,state.r);
59
    if (state.v==state.l+1) {
60
        if (state.v==state.r-1) {
61
            return s+sngltn(state.l)+"\cup"+sngltn(state.r);
62
        }
63
        return s+sngltn(state.l)+"\cup"+intrvl(state.v+1,state.r);
64
    }
65
    return s+intrvl(state.l,state.v-1)+"\cup"+sngltn(state.r);
66
*/
67
}
68
69
usepackage("mathtools");
70
unitsize(1cm);
71
72
for (int i = 0; i < sz; ++i) {
73
    if (chars[i] == "A" || chars[i] == "B") continue;
74
    label(
75
        "The DP implementation depends on there only being $A$s and $B$s!",
76
    (2,1),brown);
77
}
78
if (sz == 0) {
79
    label(
80
        "Just for you, okay?",
81
    (2,1));
82
}
83
84
draw((2,0)--(-1,0));
85
for (int i = 0; i < sz; ++i) {
86
    draw((0,-i)--(0,-i-1)--(-1,-i-1)--(-1,-i));
87
    label("$"+chars[i]+"$",(-1/2,-i-1/2));
88
}
89
90
State[] dpA;
91
State[] dpB;
92
for (int i = 0; i < sz; ++i) {
93
    draw((2,-i)--(2,-i-1)--(0,-i-1));
94
    if (i == 0) {
95
        dpA.push(chars[i]!="A"?State(1,1,-1):State(0,0,-1));
96
        dpB.push(chars[i]!="B"?State(1,1,-1):State(0,0,-1));
97
    } else {
98
        State pDpA = dpA[i-1];
99
        State pDpB = dpB[i-1];
100
        dpA.push(pDpA#(pDpB+1)+(chars[i]!="A"?1:0)+(chars[i]!=chars[i-1]?1:0));
101
        dpB.push(pDpB#(pDpA+1)+(chars[i]!="B"?1:0)+(chars[i]!=chars[i-1]?1:0));
102
    }
103
    label("$\mathrm{dp}_A["+string(i+1)+"]="+dpA[i]+"$",(2,-i-1/4),E);
104
    label("$\mathrm{dp}_{\mathrlap{B}\phantom{A}}["+string(i+1)+"]="+dpB[i]+"$",(2,-i-3/4),E);
105
}
106
107
int acc = k;
108
string prev;
109
pair L = (1,1/2);
110
pair R = (1,-sz-1/2);
111
dot(R,red);
112
for (int i = sz-1; i >= 0; --i) {
113
    string choice;
114
    if (i == sz-1) {
115
        if (dpB[i]==acc) choice = "B";
116
        else if (dpA[i]==acc) choice = "A";
117
        else choice = "";
118
    } else if (prev == "") {
119
        choice = "";
120
    } else {
121
        acc -= (prev!=chars[i+1]?1:0)+(chars[i+1]!=chars[i]?1:0);
122
        if (dpB[i]==acc-(prev!="B"?1:0)) choice = "B";
123
        else choice = "A";
124
        acc -= (prev!=choice?1:0);
125
    }
126
    pair A = (1/2,-i-1/2);
127
    pair B = (1+1/2,-i-1/2);
128
    label("$A$",A,choice=="A"?red:black);
129
    label("$B$",B,choice=="B"?red:black);
130
    if (i != sz-1) {
131
        string pc = chars[i+1];
132
        int val = (pc!=chars[i]?1:0);
133
        drw(A--A+S,prev=="A"&&choice=="A",val+("A"!=pc?1:0),(3/8,-i-5/6));
134
        drw(B--A+S,prev=="A"&&choice=="B",val+1+("A"!=pc?1:0),(2-5/8,-i-5/6));
135
        drw(A--B+S,prev=="B"&&choice=="A",val+1+("B"!=pc?1:0),(5/8,-i-5/6));
136
        drw(B--B+S,prev=="B"&&choice=="B",val+("B"!=pc?1:0),(2-3/8,-i-5/6));
137
    } else {
138
        drw(A--R,choice=="A",0,(1/2,-i-5/6));
139
        drw(B--R,choice=="B",0,(2-1/2,-i-5/6));
140
    }
141
    if (i == 0) {
142
        drw(L--A,choice=="A",("A"!=chars[i]?1:0),(5/8,1-5/6));
143
        drw(L--B,choice=="B",("B"!=chars[i]?1:0),(2-5/8,1-5/6));
144
    }
145
    prev = choice;
146
}
147
if (sz == 0) {
148
    drw(L--R,k==0,0,(7/8,1-5/6));
149
    prev = k==0?"hi":"";
150
}
151
dot(L,prev!=""?red:black);
152
[/asy]
153
[verbatim=%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%][/verbatim]
154
Graph only:
155
[asy]
156
string topRow = "BAAABBAAB";
157
158
string[] chars = array(topRow);
159
int sz = chars.length;
160
void drw(path p, int x, pair r) {
161
    draw(p,EndArrow(angle=22.5,size=4),Margin(2));
162
    label("\scriptsize"+string(x),r);
163
}
164
165
unitsize(1cm);
166
167
if (sz == 0) {
168
    label(
169
        "Just for you, okay?",
170
    (0,1+1/2));
171
}
172
173
draw((0,-2)--(0,1));
174
for (int i = 0; i < sz; ++i) {
175
    draw((i,0)--(i+1,0)--(i+1,1)--(i,1));
176
    label("$"+chars[i]+"$",(i+1/2,1/2));
177
}
178
179
pair L = (-1/2,-1);
180
pair R = (sz+1/2,-1);
181
dot(L);
182
for (int i = 0; i < sz; ++i) {
183
    draw((i,-2)--(i+1,-2)--(i+1,0));
184
    pair A = (i+1/2,-1/2);
185
    pair B = (i+1/2,-1-1/2);
186
    label("$A$",A);
187
    label("$B$",B);
188
    if (i != sz-1) {
189
        string pc = chars[i+1];
190
        int val = (pc!=chars[i]?1:0);
191
        drw(A--A+E,val+("A"!=pc?1:0),(i+5/6,-3/8));
192
        drw(B--A+E,val+1+("A"!=pc?1:0),(i+5/6,-2+5/8));
193
        drw(A--B+E,val+1+("B"!=pc?1:0),(i+5/6,-5/8));
194
        drw(B--B+E,val+("B"!=pc?1:0),(i+5/6,-2+3/8));
195
    } else {
196
        drw(A--R,0,(i+5/6,-1/2));
197
        drw(B--R,0,(i+5/6,-2+1/2));
198
    }
199
    if (i == 0) {
200
        drw(L--A,("A"!=chars[i]?1:0),(-1+5/6,-5/8));
201
        drw(L--B,("B"!=chars[i]?1:0),(-1+5/6,-2+5/8));
202
    }
203
}
204
if (sz == 0) {
205
    drw(L--R,0,(-1+5/6,-7/8));
206
}
207
dot(R);
208
[/asy]
209

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.

6 7