gen's blog

Codeforces Round #238
By gen, 11 years ago, In English

Hello everyone!

Codeforces round #238 will start today at 19:30 in Moscow time. The round will be held in both divisions.

The round was prepared by me and cfk. This is the 4th round for me and the 2nd for Krisjanis. I think the problems this time are rather unusual and maybe even surprising. We have no doubt that everyone will find a problem that suits their taste! But you have to find it. (:

As always, thanks to Mikhail Mirzayanov (MikeMirzayanov) for Codeforces and Polygon systems, and Maria Belova (Delinur) for translating the statements. Big thanks to Gerald Agapov (Gerald) for helping in preparation of the contest. Me and Gerald had a chance to talk about the problems onsite during the Petrozavodsk winter camp, which I think was very productive.

We wish you a very exciting round!

UPD1: Score distribution:

DivI: 500 1000 2000 2000 2500

DivII: 500 1000 1500 2000 3000

The scoring for the problems is relative, so that the cost of each problem would be a multiple of 500 and closer to the objective estimate. Don't be afraid, the problems are not really that hard. (:

UPD2: Congratulations to the winners!

DivI:

  1. al13n
  2. Shef
  3. scott_wu
  4. sillycross
  5. Komaki

DivII:

  1. NelsonMondialu
  2. L_Ecry
  3. aaaaAaaaaAaaaaAaaaaA
  4. xorfire
  5. Hec

UPD3: Excellent round statistics from DmitriyH.

UPD4: The contest tutorial is published here.

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

Comments Comments (95)
| Write comment?
»
11 years ago, # |
  Vote: I like it +27 Vote: I do not like it

"Problems will be unusual and surprising". Hmmm... Sounds interesting. Good luck to everybody...!!!

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

First Contest in Iran's New year and unusuall problems!! Great!!

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

Every contest anybody has new year and should write about it. It's sooo interesting for us!

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

    No, hardly every contest. Count contests per year and think: could there really be so many existing calendars?

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

On this round I wish all high ranking.

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

    what about other rounds you still wish same thing

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

      Not to mention his "wish" is impossible because everyone can't get high ranking. Unless almost nobody solves anything.

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

        or all solve problems with same final score with probability
        0.0000000000000000000000000000000000000000000001

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

      Please don't in those little details

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

wish all participants a very happy Match ^_^

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

This round will be even unusual and surprising for me, if my solution of Problem-C gets AC and fails system test of Problem-A :)

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

    Since you know that, so it won't be surprising ;)

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

Hi all, wanted to ask a simple query. How to find name of blogs in a tabled manner, In the right panel titled "Recent Actions", If I click on detailed, I can see comments of people over different blogs, But I dont want that. I want to see more number of blogs similar to ones shown in that panel itself. Eg. I would like to see around 30 entry per page for Recent actions, Is the any such option available somewhere on codeforces?

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

My first D1 round. So exited :O #mlc

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

E is 3000 seems that opening it during contest time is useless :D

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

Loving the pretty pictures.

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

Thanks for the contest I really really enjoyed C in DIV2 ;-) It's amazing problem !!!

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

    I was going into BIT ideas, Then I thought that why is GF(2) given, find solution was really cute =D

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

    Div1-A/Div2-C, aka "how to solve a problem while ignoring over half of the input". Pretty nice :P

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

Awesome problems. I really enjoyed solving C and D. Thanks for the contest.

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

Haha, I spent most of time on problem C and didn't solve it. :( Good contest though.

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

Very nice problemset, I found my problem! It was Div1 C :)

→ Reply
»
11 years ago, # |
← Rev. 3   Vote: I like it +3 Vote: I do not like it

Nice contest, the pretty complicated at first Div1 A turned out to be awsome. What was the main idea behind D? I used a stack and LCA, but got WA. I imagined that the stack part was wrong, but couldn't find any counterexample after looking for it 10 minutes. Do you have one? (I would like to add that the stack used line intesections, not just simple comparisons)

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

    Stack works when you can't see a hill again after removing it, which doesn't work in this case.

    The LCA is correct (that's pretty easy to see). To find the next hill a climber goes to from hill i, you add the points from right to left, remember the top convex hull (well, it's actually a concave curve, but it uses the same idea as convex hull algorithm) of these points, update it when adding points and always pick the leftmost point in the hull so far (after the just added point, from which the climbers go to the next point of the hull). This can be done using vector cross product — as long as the leftmost 2 points of the hull (if they exist) are placed in such a way that the leftmost one is below the line from the just being added point to the one to its right, you remove the leftmost point of the hull — because it won't be in the top convex curve ever again. It works the same way as the standard convex hull algorithm.

    Another contest where D appears simpler than C. At least to those who are used to more algorithmic problems — like me :D. Too bad I missed the start of the contest (thanks to the modern world's stupid shopping obsession), I think I could've done well.

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

      Thanks a lot for the pointers, In order to understand why my stack is not right, do you have a small handly counterexemple? thanks.

      Edit: I tried to build a counterexample like this:

             |   
       |
       |
       |
  |    |
| |  | | 
1 2  3 4
(In reversed order, from right to left)

      On an exemple like this, my stack alg runs as follows:

      Push 1
make_edge(1,2) (i will not write these from now on)
Push 2
try to pop the stack -> verify whether or not line segment 1 3 passes through hill 2 -> no -> no pop
Push 3
try to pop the stack -> 2 4 is above 3, so we pop the stack
try to pop the stack -> 4 1 is above 2, so we pop the stack
(make edge 1,4)
Push 4

      And now we have our tree, on which we apply a LCA algorithm.

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

        Depends on the exact approach. Just be satisfied with the general guideline that stack is useful if you're sure that you can't use a discarded element again. In this case, it fails because heights of hills can vary greatly — you can discard and use again any hill many times.

        If you want a good counterexample, you can always look for it yourself — try the case that gives WA; if it's too large, try generating your own and comparing against AC solutions, etc etc.

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

          I edited my approach ^, I also corrected a few small mistakes and got ACC. Please note that my stack pop criterion is geometry heavy, something like

          if(((1ll*stack[poz].x-stack[poz-1].x)*(1ll*v[i].h-stack[poz-1].h))<((1ll*stack[poz].h &mdash; 1ll*stack[poz-1].h)*(1ll*v[i].x-1ll*stack[poz-1].x)))

          No need to try to understand the formulas, all I did was to check if a segment intersects another.

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

            It could quite possibly be the same thing I was talking about. (Convex hull can as well be implemented with stack.) I just expect an algorithm that's called just "stack" to have storing the hills on a stack to be the most complex idea in it :D

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

My best performance in cf ever(Div2 5th place wink). Thanks a lot for the mathy contest :D

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

    And I am probably going to fall at my lowest rating in the last 2 years or so. Last two contests have been miserable for me. Making a lot of silly mistakes, I dont know what has happened. :( T_T . But both of these contest had very exciting problems.

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

Nice contest! Interesting and solvable problem :)

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

Объясните, пожалуйста, популярно, почему каждый флип меняет парность ответа?

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

    раскрой скобки в выражении

    там получится что ответом является сумма произведений диагональных элементов

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

      аааа, тьфууу.. вот дурак.. Заметил, что каждый два раза, но протупил выбрасывть их.. спасибо

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

      А если точнее, то просто сумма диагональных элементов. А каждый флип просто инкрементит ответ.

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

I got TLE in Div1 A on pretest 7. I had used cin cout with ios::sync_with_stdio(false). Until now I used to think that this method is faster than scanf printf. But when I changed this to scanf printf , the code was accepted. What is the reason for this?

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

    cin/cout does usually works longer than printf/scanf...

    use read/write instead!

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

    Each operation on cin flushes cout by default. Use cin.tie(NULL); to prevent this.

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

      Are #define endl '\n' and ios :: sync_with_stdio(false) enough?

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

        Together with cin.tie(NULL); this is probably about all you can do to speed up iostreams.

        Also with std::strings it helps to .reserve() the maximum number of characters before inputting a string, and to reuse the same string object if possible:

        string s; s.reserve(100005);

for (int i = 0; i < n; i++)
{
    cin >> s;

    // do something
}
        → Reply
        • »
          »
          »
          »
          »
          11 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Not just with strings. If you have a vector<> which you construct by adding elements (my implementation of interval trees, for instance), .reserve() can cut down on time and memory nicely.

          Note a line in my template: #define dibs reserve :D

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

Very nice problem :) it's really surprising !

-.- but I late to realize that

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

А можно еще попросить, объяснить, почему мое решение на А упало? не понимаю :(

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

Thanks to authors for illustrations! Very helpful!

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

Great Round ! too bad my C couldn't make it through the system tests :D, I realized after that it had a very simpler solution than i thought

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

Illustrations were so helpful.

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

when will the ratings be updated?

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

    Rating updated just now. +26 :p

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

Why the Codeforces Judge Doesnot Give Runtime Error in Situation When Size of array is Smaller than that Required... Rather It gives WRONG ANSWER. In some Judges like spoj WE get RUNTIME ERROR. Got WA on test7 PROBLEM C DIV 2 due to shorter array size,I concentrated on other Bugs rather than Array size which i missed ... so Discouraging

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

    global array overflow will not lead to runtime error(if only a little), but local one does. overflowed parts may not be initialized correctly.

    UPD overflowed 2-dimensional array will get wrong answer. See the implementation of 2d arrays: the i+1-th row is placed right after the i-th row. So if you write overflow data in i-th row the result is the data in i+1-th row is modified.

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

    When you do something wrong in C++, you don't get a runtime error. You get undefined behavior, and today you saw one of the many ways how it can behave.

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

When the editorial posted then?

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

    The editorial will be posted tomorrow, we are working on it!

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

please can any one tell me why the judgement verdict "SKIPPED" is shown ........??

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

    Maybe you have copied the solution or commented about the solution outside

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

Thx for contest, I am very happy for my participation, in final I got +163 ratig points) thx a lot

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

Can someone please help me by pointing out why 6118389 solution fails but 6118249 passes ? (Only difference is the part commented out in the AC solution)

The code that has been commented out should have no effect on the final solution, since (X +- (2*Y))%2 is same as X%2 .

EDIT : Will not work in if 2*Y > X.

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

    I had a similar solution which failed on case 50. Weirdly, converting everything to long long got AC.

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

      Still WA. there shouldnt be a problem for long long in any case. The maximum value would be 1000*1000

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

If the result of the judging is Compilation Error, Denial of judgement (or similar) or if the solution didn't pass the first pretest, then this solution won't be considered in calculating results. I take this rule from here
Now I ask If this is the only solution I submit it wrong and get wrong answer in the first pretest so it won't be considered in calculating so it doesn't considered as a try so system has to deal with me as out of contest at this moment like the case of you didn't submit anything. Now,
why my rate change ?

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

    I think this rule only means that there are no penalties for a compilation error or failed on pretest 1 ...

    However, I think it is quite fair to get your rating changed, cause u actually tried to solve a problem during the contest ...

    → Reply
»
11 years ago, # |
← Rev. 3   Vote: I like it +49 Vote: I do not like it

Thanks for the round!

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

    Maybe it makes sense to integrate your statistics into codeforces instead of creating a blog?

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

first contest and become purple. happy~ >.<

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

Is there a quicker method for console input in java, other than BufferedReader or scanner?seems that using either of them cannot pass problem c in div2?

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

    Just now I translated my code into c++, and I used "scanf" for console input.It passed.

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

    I used BufferedReader in java (Scanner will not do with 1000000 lines) and it worked perfect.

    By the way I see no solution with BufferedReader among your 3 submissions.

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

      It is here. http://mirror.codeforces.com/contest/405/submission/6114625 Did I make some mistakes?

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

        No mistakes, but probably there really are some points to improve:

        • you really need not filling matrix at all — you need only to sum diagonal elements;
        • in matrix filling you also need not do "split" — this creates 1000 small strings 1000 times while you can simply check diagonal character with "charAt";
        • you was trying do output with System.out.print for each command — I fear this could be slow — try to collect the whole answer string in array or list and after the loop output it with a single "println".

        For 1000*1000 matrix your two pairs of nested loops will give 10^6 iterations each (and this is not necessary as I've told) so you probably spend significant time in vain and then there remained too few time for printing answer with "print".

        Check my solution (it is similar except details mentioned): 6111736 — it really takes less than 200ms... So I do not think you need to resort to C, though surely Java is slower :)

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

          Thank you very much for your suggestion!

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

    Many Java coders use a self-written FastScanner class or something similar. For implementation details please look at any of my submissions.

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

      OK, thank you!

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

      i'm not expert, but i dont see what's the difference between ur FastScanner and java.io.BufferedReader.
      can u please explain the difference? thanks.

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

        Oh, it seems that you don't know Java at all...

        Please read about BufferedReader. Then please read about Scanner. Then please understand that FastScanner is a recreation of Scanner's most useful features for competitive programming that works fast (contrary to Scanner). Then you won't ask such stupid questions.

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

I'm waiting for editorial .

thank you

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

The tutorial will be tomorrow they said. Wait for it, they said. -_- :DDD

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

    Read it, I say now. :)

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

    For those, who didn't find it — see the tutorial Here :DD Thanks gen for the excellent round! :)))

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

Thanks everybody for participating in this round! We would like to hear your thoughts: what did you like very much or not so much? What can we improve in our next round? (Apart from the late tutorial, sorry for that..)

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

    The Style and the format of problems were very interesting (especially prob. C and D in div. 2)! I liked the problem statements, they were very clear and easily understandable.

    Maybe the only thing that I didn't like so much, is that there was little opportunity of hacking someone's solution, maybe for some of us it's good, but I think that passing the pretests almost meant passing the System Testing.

    But, in general I hope seeing more this kind of rounds here at CF. It can serve as an ideal example for the upcoming contests. We are waiting for other, even more interesting and challenging problems!

    Thank you for the hard efforts ! :)

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

    I liked that the authors messed with my head in Div1 B/Div2 D by making an example where |X| did not equal |Y| (because one term was 0 and could be omitted), and then writing

    instead of

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

    Thanks for organizing the round. I tried to solve problems A-C in Div1. Problem C was excellent: a "natural" problem and a very clear problem statement. Problems A and B were also interesting, but they were somewhat difficult to understand due to the complex problem statements. In addition, it's not nice when cin and cout are too slow (and warning about this makes the problem statement even longer) — maybe it wouldn't have been necessary to use so large test cases.

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

      Cin and cout aren't too slow if you use the right tricks. (Okay, they are sometimes, but such problems are very rare.) It's not actually an author's obligation to warn about it, and in some problems it even seems unnecessary (200000 integers is hardly an extra large test case) — take it as gen's generousness of sorts :D

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

    I think div1 problems (A-D, I don't know how to solve E so far) are really awesome. Thank you for the contest.

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

      I found E simpler than C and D. Don't be afraid of it, it isn't hard at all.

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

        Yes, during the contest I try to solve E after a lot vain work on C and D. However it requires more patience which I am lack of. Finally I solve it in the practice.

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

239 ?

→ Reply