witua's blog

Codeforces Round #157
By witua, 12 years ago, translation, In English

Hi all,

Next Codeforces Round, which is with number 157, will take place tomorrow. I'm an author of it, it is my 7th round at CF. Thanks alot to Gerald for helping in preparings.

Scores distribution in both divisions is 500-1000-1500-2000-2500.

Good Luck!

Top-7 Div1:

  1. ftiasch
  2. rng_58
  3. shangjingbo
  4. gawry
  5. sandytea
  6. Petr
  7. peter50216

Top-4 Div2:

  1. guliashvili
  2. pavel.savchenkov
  3. HighFlow
  4. mohammadrdeh

Thanks!

Editorial (currently only for Div2).

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

Comments Comments (90)
| Write comment?
»
12 years ago, # |
  Vote: I like it +13 Vote: I do not like it
  • Will the round use dynamic rating system?
  • What are scores for the problems?
  • Will there be problems about lucky numbers?
  • 157 = 74 + 47 + 7 + 7 + 7 + 7 + 4 + 4
  • GL & HF!
→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +64 Vote: I do not like it

    Since GCD(4,7)=1, every round number can be considered lucky ;)

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

      If you are to find positive values, only any greater then ab-a-b.

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

157 div 1 = 7*7*7 — 4*4*4*4 — 7*7 — 4*4 — 7 — 7 — 4 — 4 = 7^(7-4) — 4^4 — 7^(sqrt(4)) — 4^(sqrt(4)) — 7*sqrt(4) — 4*sqrt(4); 157 div 1 = 77 + 44 + 44 — 4 — 4; 157 div 2 = 44 + 44 — 7 — 7 + 4;

It can be concluded that the round for first division will be more difficult than for the second division.

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

Why this article is not on the main page?

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

"Round will not use dynamic system" Shouldn't it be more explict to write "Round will use standard distribution"?

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

    it's because the score distribution may won't be standard(for example : 1000 1000 1500 2000 2500 is not dynamic nor standard)

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

It is the third "Ukrainian" round in a row! Waiting for a nice one)

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

    Ну и зачем ты кичишься "украинским" раундом? Ты националист? Признавайся, это [ты]?(http://www.youtube.com/watch?v=RrwLGOCiqGA)

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

      И этот недотролль на девятом месте по вкладу. Парадокс, одно слово...

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

What does "the score distribution will be announced later." mean? isn't it always like 500:1000:1500:2000":2500 ?

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

    Not always. The most common distribution is 500 1000 1500 2000 2500 but there are exceptions. That means that some problems will be harder or easier than normal.

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

what does "dynamic system" mean?

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

    Dynamic scoring system is the system in which you receive points only for a correct solution and the received points are inversely proportional to the time it took you to solve the problem.

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

Wow! Mr. witua's problemset is always great! ;)

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

when the score distribution will be announced.

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

Good luck to all^O^

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

More and more times we help little Elephant :D

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

Is this the first round after end of the world?

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

    I have a doubt . If I solve the first problem 10 minutes after the start of competition and second problem after further 15 minutes i.e. 25 minutes after the start of competition . Then while calculating the score for the second problem solved will the time considered bye 25 minutes or 15 minutes . If it is 25 minutes , then is it not better to solve difficult problems first because there the penalty is larger . The text says it is better to solve problems by order in difficulty ( ascending or descending ) . May be difficult problem will large time so will affect time of larger number of problems , hence ascending order of difficulty . But just clarify which time will be considered . Thanks .

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

      25 minutes after the start of competition

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

      You'll have the penalty for 25 minutes, since they can't know how much time you have used for each problem... The most people start with the easier problem but others prefer to start with problem E, up to you to choose your strategy.

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

      25 minutes.

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

Contest was interesting, but it has a problem: from the one side first 3 problems were really easy, but the next 2 were very hard (as for Div 2). But thanks in any case.

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

    Apparently not that easy actually; there are a lot of hacks happening. (I think problem C has many hacks.) The first three are easy but somewhat tricky.

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

      any challenge case for C?

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

        Nop, but some have forgotten the cases with only 1.

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

          I did.and u hacked me :( However good that you did,else it would have failed system tests and I wouldn't have got any points.

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

      Even so, they were too unbalanced. 1200 ppl having OK on pretests for A-C and 30 for D?

      I'm fine with problems whose difficulty is based mostly on tricky cases (or using an appropriate bruteforce to escape such cases), as long as they don't make up more than half of all problems, which was not the case in div. 2.

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

i think that the A,B,C questions were very easy

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

in div1 second problem had a hard implementation and no special algorithm which i didn't like.the whole contest had too much mathematics in it i guess. calculating expectations is HARD.

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

    You can brute force (10^5 is easy). Or otherwise just note that the sum of all numbers minus the sum of the main diagonal is exactly twice of the sum of a line, but this is also exactly what we're given. The rest is left as an exercise (read: implementation problem).

    ...misread comment. I need to pay more attention to "1" and "2".

    I don't mind a lot of mathematics in the contest; in fact I like it. (Okay I'm an IMO participant so that's biased.) But the point is that it helps you to learn more than usual implementation problems. You can use Google/Wikipedia while you're competing right?

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

      It's Div1 B, not Div2.

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

      are u sure u participated in div1????!!!!

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

        I'm sure I did B Div1 (D Div2) though.

        ...yeah, now I reviewed my solution, I agree that it's hard to implement and has no special algorithm. Sorry for the confusion. (I must not take contests at 1 AM.)

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

    No idea on how to calculate number of numbers with at least some number of lucky digits in a range... I suck.

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

Fast testing: Is it our christmas's gift?

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

That awkward moment when you can't decide, whether to try the next problem or to start hacking other's solutions.

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

WOW new feature in codeforces that when hacking, every code that you have seen it before will colored in green to make it easy to know what codes you have not seen it yet.

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

    It was already on the previous contest. And yes, it is awesome. But I'm disapointed that we can't reset the colors (like "mark as non read" for client mail).

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

I found someone submitted only his template code and got passed. Maybe Div1 Problem B is a previous used problem. Look at these submissions: 2812620 2812759

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

Just finished up my first contest at CodeForces . I attempted the first three problems in Division 2 and spent rest of time trying to figure out problem D , but to no avail . I have a question : Do the hacks have to made within the 2 hours of the contest itself . And can I hack within my room only or elsewhere also . Can I hack a solution of problem that I have personally solved or can I hack solution to any problem . I was thinking that hacking phase would be after 2 hours . I recently started participating topcoder.com SRM's and there hacking phase which is called challenge phase starts after the coding phase . They have 75 minutes coding for 3 problems , 5 minutes intermission and then 15-20 minutes of hacking phase . I guess I had to press the hacks tab during the contest to be able to hack . Still have not seen the interface of hacking . Tell me something about it .

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

    1- in 2 hours

    2- your room only

    3- only problems that you solved after locking it

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

    FAQ page is not meant only to make the menu bar bigger .You should go through the rules here

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

fast system test :)

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

Good round overall, but i couldn't submit any hacks on problem C div 2.

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

Thanks @kingofnumbers What is the process of locking the solution . I didn't lock any solution . I just submitted and watched the message that it has passed pretests . I have not suffered because of that because system testing of DIV 2 has ended and I can see myself in final standings with points of all 3 problems I did . Do I need to do something else also to lock my solution of just a submit means locking . Or is there some concept of lock once I click on the "Hacks" tab . ????

Meanwhile I too feel like many , that the first 3 problems were too easy and last 2 two too difficult . Some medium level problems were missing , I feel .

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

    You can lock your problems by going to the dashboard of the contest and clicking on the lock icon aside of the problem you have solved.

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

    don't be afraid, you will get points on problem that you solved even if you did not lock it, but you may lock it if you want to hack the others' solution , locking a problem means that you can't resubmit your solution again if you find a bug in your solution

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

red ^_^ thanks for the contest

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

    Congratulations! Waiting for Div 2 rating update, hopefully I will be first time in Div1. And just before new year, like a new year gift

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

    Congratulations!~

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

the contest was terrible. you sucked with your problem set.

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

How soon are the ratings likely to be updated . I want to know whether I will be eligible for next Div2 contest which is happening soon or will I be promoted to Div 1 . I have 376 rank in Div 2 today .

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

    Sorry, but you can be sure you'll remain in Div2

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

    I think to be eligible for Div1 for first-comers(rating 1500), you need to have a rank of 5+ or so.

    My experience: Rank 16-> Rating 1476->1663

    Anyway my rating is going to drop >_<

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

    You are in div2 for sure. the real question is will you be blue or green?.

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

    about 1550 I think ....

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

I cant believe it. My submission number 2812603 passes the test case 11 (458754) for which it gives the answer 667496909 on my computer.

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

Yeah! Finally div1

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

Now waiting for the tutorial

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

what happened!! my code still running!!! after updating new ranking !!!

http://www.codeforces.com/contest/259/standings/page/42

Problem A, Div-2.

00:07:28 Running on test 31 [final tests] → 2808294

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

    i lost 87 points... showing my rank 823.. what the is this??? @codeforces authority.

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

    AC now, after sending mail to admin, but rating not yet updated..... hope to recover the bug soon.... :)

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

Why these submissions got TLE? I don't have a clue.

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

    In the first submission you calculate strlen(A) in every iteration of main loop. There are exactly strlen(A) iterations of main loop, so you solution is O(strlen2(A)), it is about 1010 operations, so TL.

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

      Thanks. I had thought the compiler or CPU may cache this constant.

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

    About first submission — strlen function works in O(n) time

    About second submission — I don't know Java at all, but it seems that this code res+=line.charAt(i); works in O(n) time

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

    len.charAt(i) is O(1) but res = res + len.charAt(i) uses string concatenation which is O(n) because a new string object is being created

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

There's something wrong in test program on div2 A. Somebody prints "No" as the result(2817648), but the answer should be "NO". I tried to hack it, but failed.

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

    Maybe validator check the first later of output :D

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

why am I div 2 winner? noh4h_ss won the contest. no?

→ Reply