RAD's blog

Codeforces Round #170
By RAD, 12 years ago, In English

Hi everyone!

Codeforces Round #170 begins soon, and I'll be the problem setter. I hope many people will be happy to solve all the problems.

UPD: The scoring is dynamic. The problems are sorted by increasing of estimated difficulty.

And the standard part: thanks to Gerald for his help with the problems, Seyaua and sdya for testing the contest, Delinur for translations, MikeMirzayanov for building the Codeforces platform.

Good luck!

UPD: Tutorial

  • Vote: I like it
  • +173
  • Vote: I do not like it

Comments Comments (88)
| Write comment?
»
12 years ago, # |
  Vote: I like it -32 Vote: I do not like it

i wish you good luck and have fun ;) =d>

→ Reply
»
12 years ago, # |
  Vote: I like it -38 Vote: I do not like it

It's also 11.30 here. I'm doing my internship, hope I will not get fired for sleeping at work -.-

→ Reply
»
12 years ago, # |
  Vote: I like it +21 Vote: I do not like it

I hope it will be a good contest! I just have a question, why do Seyaua and sdya have different name, but their image are same??? (i know their family name are same! maybe they are brother!)

→ Reply
»
12 years ago, # |
  Vote: I like it -49 Vote: I do not like it

yes we are twins...

→ Reply
»
12 years ago, # |
  Vote: I like it -32 Vote: I do not like it

How can I get positive votes in blogs? Please, help me!!!

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Always if you say 'LIKE ME' people will Dislike, because everyone want to harm))

    → Reply
»
12 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Score distribution is still unavailable :(

→ Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

4 problems with Score 3k :v Nice contest!

→ Reply
»
12 years ago, # |
  Vote: I like it +3 Vote: I do not like it

what is wrong with testcase 4 of 2C ???

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +16 Vote: I do not like it

    Perhaps a scenario in which nobody speaks any language?

    → Reply
  • »
    »
    12 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it 
    5 2
0
0
0
0
0

    The result is 5 :)

    → Reply
  • »
    »
    12 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    [sorry ! I just wrote it when no answer was available].

    all the vertices have degree 0 so everyone should learn a language !!

    → Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    maybe like this one

    2 1
0
0

    this should be 2 not one

    → Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    All of the employees know nothing.

    → Reply
»
12 years ago, # |
  Vote: I like it +3 Vote: I do not like it

last 15mins I have problems with connection to codeforces.

is this only with me or with all?

→ Reply
»
12 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Very FAST system testing @ Div 2!

→ Reply
»
12 years ago, # |
  Vote: I like it -47 Vote: I do not like it

I've challenged this solution twice during contest time but it returned correct answer

Submission: 3209935

But it failed on similar test case! admins please clarify?

Here is one of my test case: 100 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +35 Vote: I do not like it

    HEY you scrolled your browser only to give him negative votes! :P

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      HAHA it's more interesting that ppl didn't get lazy votedowning XDXD

      → Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

now I read problem B can someone explayn why length of answer<=2???

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    Because not all combinations of 1 or 2 letters can appear at the same time.

    → Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Actually It's <=3

    → Reply
  • »
    »
    12 years ago, # ^ |
    ← Rev. 2   Vote: I like it +1 Vote: I do not like it

    in 30 names with length 20 maximum number of consecutive pair elements is 30*19 and number of strings with length 2 is 26^2 30*19<26^2 so length 2 Is enough :)

    → Reply
»
12 years ago, # |
  Vote: I like it +2 Vote: I do not like it

not good contest! :|

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +58 Vote: I do not like it

    Hard problems but very interesting!

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it -11 Vote: I do not like it

      but in this contest the speed of coding was too important to be helpful for coders!

      → Reply
      • »
        »
        »
        »
        12 years ago, # ^ |
          Vote: I like it +9 Vote: I do not like it

        for me, I enjoyed solving div1 B.

        anyway I think speed of coding is important part of a good programmer.

        → Reply
»
12 years ago, # |
  Vote: I like it +21 Vote: I do not like it

The contest was very hard but the system testing was too fast!

→ Reply
»
12 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Lost 2nd position because of 10 (instead of 1000000). :( It is REALLY disappointing. I was too nervous I think. T_T

→ Reply
»
12 years ago, # |
← Rev. 2   Vote: I like it +54 Vote: I do not like it

That was really fast system testing!

Short editorial for problems I know how to solve (sorry for possible errors):

DIV1-A. Connect persons with common language, then output is max(0, #connected components — 1) + #persons without any language knowledge

DIV1-B. [extracted from rng_58 source code] For case m = 3, n >= 5 there's no solution. m = 3, n = 3/4 one can construct big triangle and a point near one of the points of the triangle. For other cases (m > 3) one can construct (as rng_58 did I think) "function X^2" for one convex polygon (points (i, i * i + LARGE_DELTA)), and "function -X^2" for the rest of the points (poiints (i, -i * i — LARGE_DELTA).

DIV1-C. It can be considered as nim game. For every row/column with coordinates [1 .. maxCoordinate — 1] count the number of "free" unit segments ("free" = not covered by any move played). Let that number be countRow_r for row r, or countCol_c for column c. Then nim sum would be NIM_SUM = (XOR_SUM countRow_r) XOR (XOR_SUM countCol_c). So by the theory of nim game first player wins if NIM_SUM != 0, otherwise second wins. Then we have to find a move which makes NIM_SUM equal to zero, and by the theory of nim games that move exists.

DIV1-E. Construct graph with two nodes u_in, u_out per one node u originally given in the input. Attach the "source" to u_in with capacity 2 and cost 0, attach u_out to the "target" with capacity 1 and cost 0. Then attach u_in to v_out with capacity 1 and cost DISTANCE(u, v) when v can be a child of u (ie. v.y < u.y). Then run min-cost-max-flow and if the flow is n — 1 you can construct the graph and output it minimum cost, otherwise no solution exists.

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    "number of free segments >= NIM_SUM. It can be proved that such row/column exists."

    Not necessarily. You only have to find one such that ("Y" xor NIM_SUM) <= "Y". The other condition would work for some cases but it's not guaranteed to always hold, unlike this one.

    http://en.wikipedia.org/wiki/Nim

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      Thanks, that was my error. I corrected it.

      → Reply
  • »
    »
    12 years ago, # ^ |
    ← Rev. 7   Vote: I like it +27 Vote: I do not like it

    supplement .. .

    DIV1-D is a knapsack problem, actually is a dependency 0-1 knapsack problem, But the dependence is very weak. So we prefer to use a grouping 0-1 knapsack problem model to solve this. The expect score is trivial, so let us focus on the penalty. You can found the penalty system in the problem is a little bit different against the reality, that is once we start solving on those large point, we'll never back to solve a small point. This declare is obviosly true.

    Then, for two large point u, v, let us denoted by (t, f) for time and fail probability.

    • tu fv (1-fu) + (tu+tv) (1-fv)
    • tv fu (1-fv) + (tu+tv) (1-fu)

    Simplificate on the formula, Then we could found a large point u is in front of v, iff

    • tu fu (1-fv) < tv fv (1-fu) .

    Once the principal contradiction is grasped, all problems will be readily solved.

    1. Sort the problem by the above function.
    2. Running a 0-1 knapsack problem.
    3. Choose the answer.
    const int N = 1009, M = 2009, P = 1000000;

pair<LL, DB> dp[M];
int n, t;

struct rec{
    LL t1, t2, s1, s2, pf;
    LL ps()const{return P - pf;}
    bool operator < (const rec& r) const{
        return t2*pf*r.ps() < r.t2*r.pf*ps();
    }
    void input(){
        RD(s1, s2, t1, t2), pf = RF() * P + 0.5, s1 *= P;
    }
    void update(){
        DWN(i, t, 0){
            if (i + t1 <= t) checkMax(dp[i+t1], MP(dp[i].fi+s1, dp[i].se));
            if (i + t1 + t2 <= t) checkMax(dp[i+t1+t2], MP(dp[i].fi+s1+s2*ps(), (dp[i].se+t2)*pf/P));
        }
    }
} A[N];

int main(){

#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
#endif

    RD(n, t); REP(i, n) A[i].input();
    sort(A, A+n); REP(i, n) A[i].update();

    LL a = 0; DB b = 0; REP_1(i, t){
        if (dp[i].fi > a || dp[i].fi == a && i-dp[i].se < b){
            a = dp[i].fi, b = i-dp[i].se;
        }
    }
    printf("%.9lf %.9lf\n", (DB) a/P, b);
}

    As we want to minimize the penalty, it'll be a wise idea that we use the second dimension of the dp array, record the maximum expected save of the penalty.

    → Reply
»
12 years ago, # |
← Rev. 7   Vote: I like it -56 Vote: I do not like it

My solution is correct!!!!!! :@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ this failed on system test: http://codeforces.me/contest/278/submission/3214079 and then just added this lines for debug and when i submitted Accepted :/ http://codeforces.me/contest/278/submission/3219530

difference is only :

void add(string &s,int toindex,int strindex) {
    if(s.length() <= strindex)
        return;
    if(root[toindex].c[s[strindex]] == 0) {
         root[toindex].c[s[strindex]] = ++cindex;
         add(s,cindex,++strindex);
    }else {
        add(s,root[toindex].c[s[strindex]],++strindex);
    }
}

void add(string &s,int toindex,int strindex) {
    if(s.length() <= strindex)
        return;
    int ind = root[toindex].c[s[strindex]];
    if(ind == 0) {
         root[toindex].c[s[strindex]] = ++cindex;
         add(s,cindex,++strindex);
    }else {
        add(s,ind,++strindex);
    }
}

why it has different answer?

Seyaua

Gerald

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +17 Vote: I do not like it

    You have undefiined behavior in line add(s,root[toindex].c[s[strindex]],++strindex); arguments can be calculated in any order. For example it can be

    1. calc strindex for last argument
    2. add 1 to strindex
    3. calc root[toindex].c[s[strindex]] with new strindex.

    Probably this one happened. It can depend on compiler and OS.

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      Also the same compiler on the same OS can reorder the parameters if it finds that to its advantage.

      → Reply
    • »
      »
      »
      12 years ago, # ^ |
      ← Rev. 2   Vote: I like it -34 Vote: I do not like it

      typedef struct node{ int c[255]; node() { for(int i = 0; i < 255; i++) c[i] = 0; } } node;

      nooo i initialize all the nodes, none of them mustn't be undefined..... strindex is always less then s.size(); every s[i] is less then 255, c[255];

      and it means that if(root[toindex].c[s[strindex]] == 0) is false

      and

      int ind = root[toindex].c[s[strindex]];

      if(ind == 0) that's true :/

      → Reply
      • »
        »
        »
        »
        12 years ago, # ^ |
          Vote: I like it +13 Vote: I do not like it

        add(s,root[toindex].c[s[strindex]],++strindex); may be done as ++strindex,add(s,root[toindex].c[s[strindex]],strindex); and may be done as add(s,root[toindex].c[s[strindex]],strindex),++strindex,;

        One of them is correct, and one not.

        → Reply
        • »
          »
          »
          »
          »
          12 years ago, # ^ |
            Vote: I like it -85 Vote: I do not like it

          fucking compilers :@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@

          → Reply
»
12 years ago, # |
  Vote: I like it +6 Vote: I do not like it

The problem Standard was A , B , C , E , E :D

→ Reply
»
12 years ago, # |
  Vote: I like it +35 Vote: I do not like it

Screencast

→ Reply
»
12 years ago, # |
  Vote: I like it +23 Vote: I do not like it

In div-1 1st prob:pretest 4 could have been avoided to increase successful hacking attempts.

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Agree with you!!! the more hacks contest have, the more enjoyable it is!

    → Reply
»
12 years ago, # |
  Vote: I like it -29 Vote: I do not like it

Контест будет рейтинговым ?

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    А почему бы ему не быть рейтинговым?

    → Reply
»
12 years ago, # |
  Vote: I like it +36 Vote: I do not like it

When will the rating update ? If there any problem, please update this blog.

→ Reply
»
12 years ago, # |
  Vote: I like it +1 Vote: I do not like it

In problem Games, I get WA on test 17. In the test one of the cuts is "2 4 2 3", while the jury's answer is 2 0 2 5. How could it be right?

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    What's the problem?

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      If the part 2 3 2 4 was already cut, how can we cut 2 0 2 5? Won't we repeat the edge 2 3 2 4?

      → Reply
      • »
        »
        »
        »
        12 years ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        As long as you touch some uncut parts, it's fine. (I asked this question during contest time)

        → Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Please note that the paper doesn't move during the cuts and you can cut along previus cuts but you have to cut at least one more unit line.

    → Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    I did the same mistake :( I believe this problem should have better definition of cutting even with a figure showing different situations.

    → Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Could someone comment on possible strategies for div1-b checker ?

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it -9 Vote: I do not like it

    Fit m vertices evenly on a circle with radius R1. Fit the other n — m ones evenly on a circle with radius R2 < R1. This can always be done, except when m = 3 and n > 4, I don't know the reason for this yet though.

    → Reply
  • »
    »
    12 years ago, # ^ |
    ← Rev. 2   Vote: I like it +10 Vote: I do not like it

    You can also create a distribution like this:

    http://s16.postimage.org/83zarzh2d/design.png

    This will guarantee that you cannot form a polygon whith more than 4 vertices selected from both the first and the second set of points. So, if you have M>3 or if M=3 and N<=4 then the given strategy will provide a good solution.

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks for the solution, but I was asking about how the checker would have evaluated the answers. I would like to know what logic did checker apply on the output points so as to verify that maximum convexity is m. (a naive approach of selecting m+1 points and checking will be too time consuming and I am not able to think of a better checker)

      → Reply
      • »
        »
        »
        »
        12 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        My guess about the checker is to run Convex Hull algorithm(O(nlgn)) on your points and see if the output is m or not.

        → Reply
      • »
        »
        »
        »
        12 years ago, # ^ |
          Vote: I like it +8 Vote: I do not like it

        I am sorry I misunderstood your question. My guess for how the checker works for this problem is that it sorts the output points clockwise or anti-clockwise, and then it used a dynamic programming algorithm to find the maximum convexity of the points. If the maximum convexity is equal to M, and there are no 3 points situated on a straight line (which could be verified in N^3 complexity, given that N is no bigger than 200) then the solution is considered correct.

        As for the Convex Hull algorithm, I do not believe this algorithm would have found the maximum convexity of a set of points (consider a hexagon inside a square, the convex hull algorithm would say that the maximum convexity is 4, which is not correct) .

        → Reply
    • »
      »
      »
      12 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      You also need to make sure you don't have 3 points at the same line, like here: http://s24.postimage.org/oynvny78l/design2.png I wrote same solution but made this bug during the contest. I took a random distance out of my head between those two simmetric figures, but, as usual, if it is possible to make a bug I will make it:)

      → Reply
      • »
        »
        »
        »
        12 years ago, # ^ |
        ← Rev. 4   Vote: I like it -8 Vote: I do not like it

        My guess about the checker is to run Convex Hull algorithm(O(nlgn)) on your points and see if the output is m or not.

        [Edit: sorry I meant to reply to pareshverma91]

        → Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +23 Vote: I do not like it

    First of all, check that no three points lie on the same straight line.
    Then iterate over all points, and assume that the i-th point is the leftmost point of largest convex polygon. Sort all the points to the right of i by the angle relative to the i-th point.
    Calculate the following DP: z[t][j] = the maximal size of polygon, where the first point is i, the last point is j, and the next to last is t (j is always greater than t by the relative angle). We can connect points i and j to finish the polygon of z[t][j] points. Or we can find the next point k to continue building the polygon. k must be greater than j by relative angle, and triple (t, j, k) must have positive orientation. This solution is O(n4) in total, but actually it's C(n, 4). And you can improve the DP to make it O(n3). Code: http://pastebin.com/Ubf25Qq8

    → Reply
»
12 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Fast System test is awesome, hopping rating update be as fast as it .... every contest.

→ Reply
»
12 years ago, # |
  Vote: I like it +10 Vote: I do not like it

In problem div1-C, the sentence "that is the knife has to touch the part of the paper that is not cut before." is ambiguous. One could understand, as in my case, that the knife can only touch the part of the paper that is not cut before. My submitted solution in contest time was written according to this interpretation. Please, try to be clearer the next time.

→ Reply
  • »
    »
    12 years ago, # ^ |
    ← Rev. 2   Vote: I like it +9 Vote: I do not like it

    I find it clear. In your interpretation, it'd be "cannot touch the part that was cut before" — exactly to remove the possibility of this ambiguity. But if you're not sure, you can still ask an official question — they're answered pretty fast.

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      I also asked the same question during the contest. Maybe it should have been better to make a public clarification since lots of people asked about it.

      → Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    The same here ; /. In fact it's our fault, but that's not a good thing when many contestans got the description wrong :d.

    → Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    I made the same mistake too :(

    I think for this kind of ambiguous, one of the best solution is to have it in samples to resolve it.

    Samples are not used for testing, but are used for better understand the statement and resolve the ambiguous.

    The current samples are already very good that resolved the ambiguous of "it is not guaranteed that the cuts were obtained during any correct game".

    Hope it can be better next time.

    → Reply
»
12 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Why my solution in problem C div2 getting "Ошибка исполнения на тесте 10"?I think everything is OK...but i can't understand why it is giving TLE...PLS help...Here is my code:3214342

→ Reply
  • »
    »
    12 years ago, # ^ |
    ← Rev. 2   Vote: I like it +1 Vote: I do not like it

    You don't get TLE (Time Limit Exceeded), but Runtime Error. Download the test, run in your environment, debug.

    Edit: Aha, you can't download the test. But repeat the last full line 30 times and you should get runtime error locally. I did with your prog.

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      thx for help...but my prog giving true result in my computer...but in codeforces it's giving runtime error...but i don't know why?...

      → Reply
      • »
        »
        »
        »
        12 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        This is the problematic line:

        int n,i,j,k,l,f,d,c,ans,cnt,s,t[MN],m;

        Don't declare all the letters in advance. You used global variable L, where you should have a local L. Probably your compiler optimized the code incorrectly, not expecting that the value of L could change inside the loop. Actually it is changed inside recurent calls to dfs. Incorrect optimization surprisingly gave expected behavior in your environment. I bet you don't use gcc, do you? What's your compiler?

        → Reply
        • »
          »
          »
          »
          »
          12 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          thx a lot for helping...i accepted it...problem was "l" i think...i took it from global and it got accepted...

          → Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Will the editorial be public?

→ Reply
»
12 years ago, # |
  Vote: I like it -8 Vote: I do not like it

in problem div 1 C "You are given an n × m piece of paper" "(0 ≤ xbi, xei ≤ n, 0 ≤ ybi, yei ≤ m)" how can be both correct? if 0<=xbi<=n and 0<=ybi<=m than we are given n+1 x m+1 piece of paper no?

→ Reply
»
12 years ago, # |
  Vote: I like it +13 Vote: I do not like it

Also made a screencast: link

→ Reply
»
12 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Hi,

Is it please possible to have as many rounds in the weekends as possible? For ex, the next div2 round is on monday and i don't see why it was not scheduled on sunday. For people from western europe the 7:30pm from russia is really bad during work days.

Thanks a lot!

→ Reply