Topcoder SRM 715 - Codeforces

→ Обратите внимание

До соревнования
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
09:56:44
Зарегистрироваться »

*есть доп. регистрация

→ Трансляции

Leetcode BiWeekly Contest 144 — Solution Discussion

Shayan

До начала 11:26:44

Codeforces CodeTON Round 9 (Div 1 + Div 2) — Solution Discussion

Shayan

До начала 12:56:44

Всё →

→ Лидеры (рейтинг)

№	Пользователь	Рейтинг
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

Страны | Города | Организации

Всё →

→ Лидеры (вклад)

№	Пользователь	Вклад
1	cry	167
2	Um_nik	163
3	maomao90	162
4	atcoder_official	161
5	adamant	159
6	-is-this-fft-	158
7	awoo	156
8	TheScrasse	154
9	Dominater069	153
9	nor	153

Всё →

→ Найти пользователя

→ Прямой эфир

Детальнее →

Блог пользователя cgy4ever

Topcoder SRM 715

Автор cgy4ever, история, 8 лет назад, По-английски

Topcoder SRM 715

Time: 9:00 pm EDT Tuesday, May 30, 2017

Calendar: https://www.topcoder.com/community/events/

cgy4ever
8 лет назад
29

Комментарии (26)

Показать архивные | Написать комментарий?

Swistakk

8 лет назад, # |

Holy Mike and Mother of TopCoder! Schedule announced up to end of May!

→ Ответить

cgy4ever

8 лет назад, # ^ |

+10

We will announce TCO schedule (online and regionals) very soon — it will be up to September. :P

→ Ответить

poikniok

8 лет назад, # ^ |

+15

Yes but only 2 rounds a month, how I miss the old days when there were 4 rounds every month :(

→ Ответить

cgy4ever

7 лет назад, # |

+19

Starts in 1 day.

→ Ответить

rhezo

7 лет назад, # ^ |

+10

Another reminder because participation in rounds at this time is very less.

→ Ответить

MedoN11

7 лет назад, # |

+31

What was the point of making div1-250 incredibly easier than usual?

→ Ответить

poikniok

7 лет назад, # ^ |

To test people's speedcoding / give randoms a chance to beat reds :)

→ Ответить

Lewin

7 лет назад, # |

← Rev. 2 →

+37

I was the writer for this round. Here is the code and some short explanations.

div2

ImageCompression

MaximumRangeDiv2

InPrePost

Notice that the pre and post traversals tell us what the root is. We can then look into the in order traversal to know what the size of the left and right subtrees are and recurse. The idea for this is relatively simple, but the implementation can get very complicated if you are not careful.

code

import java.util.HashSet;

public class InPrePost {
    public final int PRE = 0, IN = 1, POST = 2;
    public int[][] child;
    public int[][] a;
    public String isPossible(String[] s, int[] a1, int[] a2, int[] a3) {
        child = new int[3][2];
        for (int i = 0; i < 6; i++) {
            child[i/2][i%2] = getIdx(s[i]);
        }
        a = new int[][] {a1, a2, a3};
        int n = a1.length;
        return pok(new int[]{0,0,0}, new int[]{n-1,n-1,n-1}, new int[]{0,1,2}) ? "Possible" : "Impossible";
    }
    public int getIdx(String s) {
        switch(s) {
            case "pre": return PRE;
            case "in": return IN;
            case "post": return POST;
            default: throw new RuntimeException();
        }
    }

    public int[] getId(int[] x) {
        int[] w = new int[3];
        for (int i = 0; i < 3; i++) w[x[i]] = i;
        return w;
    }

    public boolean pok(int[] s, int[] e, int[] cmode) {
        int clen = e[0] - s[0] + 1;
        if (clen == 0) return true;
        if (clen == 1) {
            if (a[0][s[0]] == a[1][s[1]] && a[1][s[1]] == a[2][s[2]]) {
                return true;
            } else {
                return false;
            }
        }
        int[] w = getId(cmode);
        int root = a[w[PRE]][s[w[PRE]]];
        if (a[w[POST]][e[w[POST]]] != root) {
            return false;
        }
        for (int i = s[w[IN]]; i <= e[w[IN]]; i++) {
            if (a[w[IN]][i] == root) {
                int szleft = i - s[w[IN]];
                int szright = e[w[IN]] - i;
                int[] ls = new int[3], le = new int[3], rs = new int[3], re = new int[3], lmode = new int[3], rmode = new int[3];
                for (int j = 0; j < 3; j++) {
                    ls[j] = s[j]; re[j] = e[j];
                    if (cmode[j] == PRE) ls[j]++; if (cmode[j] == POST) re[j]--;
                    lmode[j] = child[cmode[j]][0]; rmode[j] = child[cmode[j]][1];
                    le[j] = ls[j] + szleft - 1; rs[j] = re[j] - szright + 1;
                }
                return pok(ls, le, lmode) && pok(rs, re, rmode);
            }
        }
        return false;
    }
}

div1

MaximumRange

ClassicTowers

Consider how to compute the minimum number of moves given a configuration. We can iterate through biggest disk to smallest disk. Initially, we'll fix the target rod as the rod containing the largest disk. So now, we have some a target rod, and the current disk we are considering. If the current disk is already at the target rod, we do nothing. Otherwise, WLOG, suppose our target is A, and our current disk is on B. Then, we want to recursively solve the problem when the target is C with one fewer disk, then add 2^(current disk number) (this can be derivied by knowing how towers of hanoi work).

We can use this solution to constuct a dp with state (s₁, s₂, s₃, want), meaning we need s_i disks on the i-th rod, and we want to move them all the the rod want. We can then look at the binary representation of k to determine when we need to switch our target or stay at the current target.

code

public class ClassicTowers {
    public String findTowers(long k, int[] count) {
        int ndisks = count[0]+count[1]+count[2];
        if (k >= 1L << (ndisks - 1)) return "";
        boolean[][][][] dp = new boolean[3][ndisks+1][ndisks+1][ndisks+1];
        dp[0][0][0][0] = true;
        dp[1][0][0][0] = true;
        dp[2][0][0][0] = true;
        int[][][][] sw = new int[3][ndisks+1][ndisks+1][ndisks+1];
        for (int d = ndisks-1; d >= 0; d--) {
            if (((k>>d)&1) == 1) {
                // must switch
                for (int w = 0; w < 3; w++) {
                    for (int h1 = 0; h1 < ndisks; h1++) {
                        for (int h2 = 0; h2 < ndisks; h2++) {
                            for (int h3 = 0; h3 < ndisks; h3++) {
                                for (int nxt = 0; nxt < 3; nxt++) {
                                    if (nxt == w) continue;
                                    if (h1+h2+h3 == ndisks-d-1 && dp[w][h1][h2][h3]) {
                                        int nh1 = h1, nh2 = h2, nh3 = h3;
                                        if (3-nxt-w == 0) nh1++;
                                        if (3-nxt-w == 1) nh2++;
                                        if (3-nxt-w == 2) nh3++;
                                        dp[nxt][nh1][nh2][nh3] = true;
                                        sw[nxt][nh1][nh2][nh3] = w;
                                    }
                                }
                            }
                        }
                    }
                }
            } else {
                // must stay
                for (int w = 0; w < 3; w++) {
                    for (int h1 = 0; h1 < ndisks; h1++) {
                        for (int h2 = 0; h2 < ndisks; h2++) {
                            for (int h3 = 0; h3 < ndisks; h3++) {
                                if (h1+h2+h3 == ndisks-d-1 && dp[w][h1][h2][h3]) {
                                    int nh1 = h1, nh2 = h2, nh3 = h3;
                                    if (w == 0) nh1++;
                                    if (w == 1) nh2++;
                                    if (w == 2) nh3++;
                                    dp[w][nh1][nh2][nh3] = true;
                                    sw[w][nh1][nh2][nh3] = w;
                                }
                            }
                        }
                    }
                }
            }
        }

        for (int i = 0; i < 3; i++) {
            if (dp[i][count[0]][count[1]][count[2]]) {
                String ret = "";
                int cp = i;
                for (int j = 0; j < ndisks; j++) {
                    int d = sw[cp][count[0]][count[1]][count[2]];
                    int which = cp == d ? cp : (3 - d - cp);
                    ret += (char)('A' + which);
                    count[which]--;
                    cp = d;
                }
                return ret;
            }
        }

        return "";
    }
}

PreInPost

We can solve this by dp. We'll let dp[L][R] tell us whether or not it is possible to match the numbers in a1[L..R] with the corresponding numbers in a2. Of course, if the numbers in a2 are not adjacent it is impossible.

If t1 or t2 is in "in", this is easy, we can find the root and know the size of the left/right childs and recurse. If they are "post" and "pre", we'll need to try all roots. Overall, this means in the worst case, each dp state may take O(n) time to check.

Overall, the idea for this problem is not too complicated, but implementation can get very complicated if you are not careful.

code

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;

public class PreInPost {
    public final int PRE = 0, IN = 1, POST = 2;
    public int getIdx(String s) {
        switch(s) {
            case "pre": return PRE;
            case "in": return IN;
            case "post": return POST;
            default: throw new RuntimeException();
        }
    }
    public int[][] child;
    public int[][] a;
    public int x1,x2,x3;

    public int[] findMissing(String[] s, int[] a1, int[] a2, String e1, String e2) {
        int[] x;
        x = new int[]{2,1,3,5,4}; if (check(s,a1,a2,x,e1,e2).equals("")) return x;
        child = new int[3][2];
        for (int i = 0; i < 6; i++) {
            child[i/2][i%2] = getIdx(s[i]);
        }
        int n = a1.length;
        x1 = getIdx(e1); x2 = getIdx(e2); x3 = 3-x1-x2;
        a = new int[3][]; a[x1] = a1; a[x2] = a2;
        mp = new HashMap<>();

        ArrayList<Integer> z = get(new int[]{0,0,0}, new int[]{n-1,n-1,n-1}, new int[]{0,1,2});
        if (z.size() > 0) {
            int[] ret = new int[z.size()];
            for (int i = 0; i < z.size(); i++) ret[i] = z.get(i);
            return ret;
        } else {
            return new int[]{};
        }
    }

    public HashMap<Long, ArrayList<Integer>> mp;
    public int[] getId(int[] x) {
        int[] w = new int[3];
        for (int i = 0; i < 3; i++) w[x[i]] = i;
        return w;
    }
    public long hash(int... x) {
        long ret = 0;
        for (int b : x) {
            ret *= 400;
            ret += b;
        }
        return ret;
    }
    public ArrayList<Integer> get(int[] s, int[] e, int[] cmode) {
        long key = hash(s[x1],s[x2],e[x1],e[x2],cmode[x1],cmode[x2]);
        ArrayList<Integer> ret = mp.get(key);
        if (ret != null) return ret;
        mp.put(key, ret = new ArrayList<>());
        int clen = e[0] - s[0] + 1;
        if (clen == 0) return ret;
        if (clen == 1) {
            if (a[x1][s[x1]] == a[x2][s[x2]]) ret.add(a[x1][s[x1]]);
            return ret;
        }
        int[] w = getId(cmode);

        int rootpr = x3 == w[PRE] ? -1 : a[w[PRE]][s[w[PRE]]];
        int rootpo = x3 == w[POST] ? -1 : a[w[POST]][e[w[POST]]];
        if (rootpr != -1 && rootpo != -1 && rootpr != rootpo) return ret;
        int root = rootpr == -1 ? rootpo : rootpr;

        for (int szleft = 0; szleft <= clen-1; szleft++) {
            int szright = clen-1-szleft;
            if (x3 == w[IN] || a[w[IN]][s[w[IN]]+szleft] == root) {
                ListPair p = tryRoot(szleft, szright, s, e, cmode);
                if (p.ok()) {
                    if (x3 == w[PRE]) ret.add(root);
                    ret.addAll(p.left);
                    if (x3 == w[IN]) ret.add(root);
                    ret.addAll(p.right);
                    if (x3 == w[POST]) ret.add(root);
                    break;
                }
            }
        }
        return ret;
    }

    static class ListPair {
        public ArrayList<Integer> left, right;
        public ListPair(ArrayList<Integer> left, ArrayList<Integer> right) {
            this.left = left;
            this.right = right;
        }

        public boolean ok() {
            return left != null && right != null;
        }
    }
    public ListPair tryRoot(int szleft, int szright, int[] s, int[] e, int[] cmode) {
        int[] ls = new int[3], le = new int[3], rs = new int[3], re = new int[3], lmode = new int[3], rmode = new int[3];
        for (int j = 0; j < 3; j++) {
            ls[j] = s[j]; re[j] = e[j];
            if (cmode[j] == PRE) ls[j]++; if (cmode[j] == POST) re[j]--;
            le[j] = ls[j] + szleft - 1; rs[j] = re[j] - szright + 1;
            lmode[j] = child[cmode[j]][0]; rmode[j] = child[cmode[j]][1];
        }
        ArrayList<Integer> left = get(ls, le, lmode);
        ArrayList<Integer> right = get(rs, re, rmode);
        return new ListPair(left.size() == szleft ? left : null,
                right.size() == szright ? right : null);
    }
}

→ Ответить

mmaxio

7 лет назад, # ^ |

+11

You were also the writer for the last 2 contests(w/o this SRM) I participated in :O

→ Ответить

Um_nik

7 лет назад, # |

+20

How to solve hard? I thought that if the solution is not unique (if it exists) then it will be kinda hard to check it. So I wrote some bruteforce with breaks hoping that bad branches will be very short. And it passes.

→ Ответить

Lewin

7 лет назад, # ^ |

← Rev. 2 →

You can see div2 hard on how to check (in essence, you know the root from pre and post, and the in order traversal tells you how to split into left and right subtrees).

I'm not sure if it's possible to break a solution like yours.

→ Ответить

Um_nik

7 лет назад, # ^ |

I'm stupid, yeah. I use all that ideas in my bruteforce :)

→ Ответить

Swistakk

7 лет назад, # ^ |

Haha also thought about some kind of backtracking hoping it will crash shortly :P. But too late in the contest :<.

Actually checking if solution is good is pretty easy. I tried to solve problem recursively and in every execution I was given two orders and two types, but that didn't suffice to make good transitions. But if you are given three orders and three types then you always know what is the root (because you are given both preorder and postorder and can take first/last one in those), what belongs to left subtree and what belong to right (because you know where is root in inorder), so you can proceed recursively and recover whole tree in unique way.

→ Ответить

tubo28

7 лет назад, # |

← Rev. 2 →

+57

Div1Easy : competitive typing
Div1Med : no clue
We in range 1400-1500 need an intermediate.

→ Ответить

rng_58

7 лет назад, # ^ |

+37

I had the following problem when I was an admin:

D1 Easy shouldn't be too hard. Otherwise many people will get zero.

E ≤ 1500

D1 Hard shouldn't be too hard. Otherwise targets will get bored.

H ≥ 3000

The difference between Easy and Medium should be small. Otherwise intermediate people will get bored.

M - E ≤ 700

For the same reason, the difference between Medium and Hard should be small.

H - M ≤ 700

→ Ответить

tubo28

7 лет назад, # ^ |

Infeasible (´；ω；｀)

→ Ответить

cgy4ever

7 лет назад, # ^ |

What is E, H, M? The rating that have 50% chance to solve?

Btw, do you remember why we wanted to set about 1% solve rate for Div1-Hard? (Even bmerry told me that Div1-Hard is unsolvable in recent years, so I'm thinking about lower the difficulty.)

→ Ответить

rng_58

7 лет назад, # ^ |

Please don't take the values very seriously, I just wanted to say that it's very hard to find a problemset that suits everyone.

If my memory is correct, CF changed the cutoff between D1 and D2 a few years ago. I think if TC do the same (without changing the difficulties of problems) the situation becomes better. For blue coders D2 Hards look very suitable (they are somewhere between d1 easies and d1 mediums).

I don't remember about 1% rate, but that can be outdated given that recently only around 300 people participate in D1 and still lots of very strong people participate. Now I think anywhere between 1 person and 5% is suitable.

→ Ответить

Vicennial

7 лет назад, # ^ |

Btw why cant topcoder have more problems in a round? Even 1 extra problem would help decrease the massive jumps in difficulty.

→ Ответить

tubo28

7 лет назад, # ^ |

You think the system and the applet are designed enough extensible and tough so that it's possible?

→ Ответить

Vicennial

7 лет назад, # ^ |

+25

Maybe not. But IMO, topcoder is losing popularity and they have to do something about it before its too late.

→ Ответить

tubo28

7 лет назад, # ^ |

I relay think so too :,(

→ Ответить

dalex

7 лет назад, # ^ |

I have 1800 and it's the same for me. Solve easy in 10 min and go AFK — that's my typical round. I stopped competing at Topcoder because of that.

→ Ответить

E869120

7 лет назад, # ^ |

I agree. I have 1799 in Topcoder, but last time (SRM 714), I solved easy in 4 min but I can't solve medium.

What I feel strongly recently is "Div1-Med difficulty is increasing".
The SRM 715-710 Med solved are 20, 45, 22, 2, 107, 6. (Average numbers of competitor is about 270)
But SRM 515-510 Med solved are 57, 39, 159, 67, 173, 32. (Average numbers of competitor is about 600)

So, I think people who rating is 1500-2200 can solve easy rapidly, but can't solve medium especially Div1-Med's solved is 1-digit.

Recently, I'm practicing in Div1-Med. If I could gain performance to 2000+,... but I couldn't solve Div1Med and I would be sad in contest that Div1-Med's solved is 1-digit.

→ Ответить