Serega's blog

Codeforces Round #193 (Div. 2)
By Serega, 11 years ago, translation, In English

Hello everyone!

In several days (July 24, 19:30 MSK) will take place Codeforces Round #193 (Div. 2), which I have prepared. Those who has already reached the first division traditionally can participate in the round out of the competition.

I would like to thank Vitaliy Gridnev (gridnevvvit), Pavel Kunyavskiy (PavelKunyavskiy) and Dmitriy Ivanov (DmitriyIvanov) for testing of problemset, coordinator of Codeforces rounds Gerald Agapov (Gerald) for useful hints and Maria Belova (Delinur) for translation of statements into English.

Good luck and high rating to all!

UPD1. The score distribution in this round will be dynamic (see here). In our opinion problems are sorted according to their difficulty.

UPD2. Analysis of problems is publisched.

UPD3. Rating is updated. Congrutalations to the winners who solved 4 problems:

Williamacm

Windseeker

Tifuera

seen

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

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

I hope, the contest will be as good as round 192, I hope there is clear explanation and good picture like in the past :)

thanks :)

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

First , Thanks For Round Preparation. Second , Hope from you not to follow the rule of "The lower rate problem setter The higher problems difficulty" :).

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

    Just to remember my previous comment ,for me the problems was very hard to understand

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

      I guess the rule really applied for this contest. The problem statements were too much painful to understand. :/

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

Serega — Sereja

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

This is not about asking up-votes , because sincerely I could not care less about that, but I would like to ask the dear down voters, what is the logic of negatively rating my comment, and the one below positive ( nothing personal with the windoro, just an example ), when they almost say the same thing ?

PS:Now you have reason to down-vote.

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

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

    Even I understand you. Don't try to search the logic — it's Codeforces, upvotes and downvotes appears randomely.

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

      For instance, like now.

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

        Sometimes I am surprised to find that some comments that have good/helpful content being downvoted... so I just give them an upvote to balance it out >:)

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

Wish everyone & myself a good rating~

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

I think there will be short and not mathematical problems

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

So many contest on codeforces. Feeling really fantastic! (Y)

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

What is the dynamic score distribution ?

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

    Task score depends on number of people solving the task. More in detail: link

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

good luck to all...

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

Slow testing again...

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

the problems don't look like div2 to me

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

18 mins have passed and i am still waiting for my judgement. Its not easy moving on to the next problem knowing your queued solution might be wrong.

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

is the problems statements (in English version of codeforces) written in English?

I can't understand the problems at all!

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

    I give up the contest , one hour of contest passed and I still can't understand problems A C D E

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

    I guess meaning of A . Luckily,I get AC. But I spent an hour and a half on a guess！！！

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

If the test is so slow, I think this contest should be unrated.

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

Could someone tell me why my submit is in queue while other submits behind me is tested? THX~

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

First Codeforces was temporary unavailable, after that I submitted my solution, but it takes more than 20 minutes in queue and...

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

My first submission is 14 min after contest but it still in queue. In current standing I see Egor accepted C 30 min after contest. The system test work down, i think i should sleep and ignore this contest

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

http://mirror.codeforces.com/blog/entry/8063#comment-138056

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

Oh common what's happening. Why did some people get answer for their submissions on B 30-40 minutes into contest and I didn't have an answer for 30 minutes after I submitted 15 minutes into the contest. What is more I got a wrong answer and instead of searching for a mistake 20-30 minutes in contest I have to search for an error 50 minutes after beginning. This is way to big loss of points ....

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

The language of each problem statement is very accurate but yet very advanced. While I appreciate the comprehensive context , I still think it's a disadvantage for those who are less skilled in English.

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

    Yeah, "A student's life is fraught with complications. Some Berland University students know this only too well. Having studied for two years, they contracted strong antipathy towards the chairperson of some department. Indeed, the person in question wasn't the kindest of ladies to begin with: prone to reforming groups, banning automatic passes and other mean deeds. At last the students decided that she just can't get away with all this anymore..." It's just too hard to understand !!!

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

      It took 10mins to understand each questions

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

the level of these problems is very high compared to average Div-2 problems....wonder why??

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

    This has been the case with recent div2 only contests.

    Also, including all kind of tests in pretest has also become a routine. Most contests don't have many hacks.

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

Apparently it is not guaranteed that being an excellent coder leads you to develop a reliable and fault-tolerant web application. Right, CodeForces?

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

As Killever said: "First , Thanks For Round Preparation. Second , Hope from you not to follow the rule of "The lower rate problem setter The higher problems difficulty" :)." 2 days ago, and has a lot of negative feedbacks! But he was right!

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

for B problem, is it available to solve it other than use segment tree ?

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

    You don't need a segment tree, there are no updates at all, so you can precompute everything you need. In my solution i compute F[i], which is what the answer would be for just one segment, using only the numbers from 1 to i. And then let's say that the begginning of the second interval is at Z. Then the current answer is Sum(Z,Z+K-1)+F[Z-1], you can simply check all possible begginings of B (from K+1 to N) and pick the one that has the largest answer. You can calculate Sum(a,b) constantly after linear precompute :) Hope i helped

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

      thx for the answer, i will see your code and take my time :)

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

I am not expecting the system testing to start soon. Rather I'd go to sleep.

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

Could someone give me hints about problem D? My idea is the following : We take a sile V, suppose there is direct passage to P siles from V. If P>=K, then we can pick subsets from those K vertices and the sile V will be their adjacent sile, since its mentioned that there is only one adjacent sile to a subset of K vertices, and obviously V is one. Every sile from those will be chosen in exactly C(K-1,P-1) subsets, and therefor an edge connecting V and some sile Z, will be used exactly C(K-1,P-1). Knowing that we can sum all the edges outgoing from one sile and then multiply it by C(K-1,P-1) , and doing that for every sile we get the total sum, now we have to divide it by the total amount of subsets of K vertices we can pick, which is C(K,N). However since P is different for each sile, i couldn't find a way to avoid using large numbers and therefor couldn't get my solution to work. Is that the proper idea or am i too far :P?

[C(A,B) = Binomial Coefficient]

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

    I think it's correct, but use C(K - 1, P - 1) instead. I submitted the same thing with binoms in long double, hope it will be enough.

    UPD: it is enough.

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

      Yea, sorry, it's C(K-1,P-1), edited. However why does it work? I am surprised it works since binomial coefficients are usually really large... It will be interesting to see a proof why it won't overflow

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

        I think if both the nominator and denominator are very large, precision errors appear only after the decimal point separator in the resulting number. But if they are small, then precision errors should be negligible in nominator and denominator.

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

          The reason why the binomial coefficients do not grow large is that for this special graph, K can only be 1, 2, or N-1.

          • K can be 1 when N is even. (matching)
          • K can be 2 when N is odd. (many triangles share a same point)
          • K can be N-1 no matter N is even or odd. (clique)

          This property makes the binomial coefficients very limited in range.

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

            Thanks, that's a very nice observation! I feel a little bit stupid now — my solution does not use any properties of the graph — it is just a brutal bignum computation but somehow it actually works, and it would (in a way) work on any graph.

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

            Why?? How do you prove it?

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

              I mainly got it from observation and then verified it with the test data. Indeed the K=2 construction is already quite tight in constraints. K=1 and N-1 are trivial. However I tried but could not come up with a proof for the other cases. Hope that there would be an editorial for that.

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

      It's really depressing when I know it's enough.... I got the formula, did some preprocessing to check overflowing, and after knew it will overflow (I checked C(2000,1500)), I closed the problem. Poor me, LOL.

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

oh . how much i miss round 192 :D

→ Reply
»
11 years ago, # |
← Rev. 3   Vote: I like it +3 Vote: I do not like it 
00:16:47  Skipped [pretests] → 4148842
01:00:50  Accepted [final tests] → 4152076

Same code, 46 minutes in queue :(

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

Yeah, after this round! I never rate a round tutorial before I participate in the round. To muslims: I was fast, and azaan was in the contest time, I just participate in this round for 40 minutes. Excuse me, but it was the worst contest I ever participate in Codeforces.

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

    in my country, the contest time is about 4-5 hours after azaan :)

    just dont participate if you have other important things to do, and if you still insisted, you shouldn't say the worst time

    remember, there is different place, different time, and different religion for others

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

      I'm not talking about the time! I'm talking about the problems!

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

        oh, sry, i misunderstood that.

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

          he said:" I was fast, and azaan was in the contest time, I just participate in this round for 40 minutes"

          You did not misunderstood.

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

How lucky am I! I passed E at the last second!

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

long in-queue is still the most annoying problem. this problem affects the ranks directly.

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

Forgot to mark one flag in solution to problem E, and hence I was outputting the correct string, but not lexicographically smallest, but just the one with the maximal number of '1's. Failed on test #169 (last test case). It seems that my luck was a little bit less strong than test cases this time.

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

To be honest,I don't think the problems description is pellucid...

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

How to do C?

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

Can someone clarify me this sentence in problem D :

"The insurgents studied the polygon plan and noticed its unusual structure. As it turned out, for any k-element set of silos S there is exactly one silo that is directly connected by a passage with each silo from S (we'll call this silo adjacent with S)."

How is it possible to this test case be valid :

5 2

-1 -1 14 3

19 -1 1

-1 6

0

Silos set S = {1, 2} (number 1 and 2 silo) have 0 adjacent silo, right? Silo 1 is connected with 4 and 5, and silo 2 is connected with 3...

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

Editorial was out 30 minutes ago, but no one announced it!

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

It's just my opinion, but I think CodeForces should balance the difficulty between Div 1 and 2 more. With solving 3 problems, you can place on top 20 in Div 2, and will be promoted to Div 1. In Div 1, with solving 1 problem, you can't stay longer and will be kicked to Div 2. I got this many times, do well in Div 2 but not good enough in Div 1.

My example for "easier" difficulty is TopCoder. In Div 1, you will be sent to Div 2 only if you can't solve any problem. Maybe the difference comes because the problem's count is differ (3 on TopCoder and 5 on CodeForces). Or maybe the competition here is intended to be more strict?

Just my opinion, it's not a bad thing actually.

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

I can understand that English isn't necessarily the first language of everyone (it isn't mine either). But the problem statements today were simply too hard to understand.

The description of Problem A seemed unclear (e.g "if j ≥ 4 and the players who had turns number j - 1, j - 2, j - 3, made during their turns the same moves as player bi on the current turn, then he had drunk a glass of juice" — who is the 'he' referring to? The current player, or the players in the last three turns? Why is the whole description of the game in past tense?). The first paragraph of Problem C looks like it is fresh out of Google Translate (not that it mattered for solving the problem, but still).

I hate to be a grammar Nazi, but this really makes a difference in programming contests.

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

    I agree. This problem took me a minimum of 10 minutes to understand, I honestly lost track. I initially thought it was 30 but then checked my submission time. For my first contest on here, this was really disconcerting.

    Things that threw me:

    • Trying to figure out who "he" was
    • Understanding that Vasya was always player 0
    • Figuring out the what difference between an elbow and a nod actually was
    • Having to assume "optimally well" meant drinking the most juice (most drinking games in my country, the aim is to NOT have to drink...)
    • Interpreting the question to understand Vasya may or may not have played optimally well, and you were to disregard his moves from the record.

    Mind you, English IS my native tongue, which might actually have proved to be a disadvantage here.

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

    Actually the Russian statements were hard to understand too.

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

Horrible problem statement !!!

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

even though i submitted A a bit earlier than everybody else and hence wasn't in queue for very long time, i was still greatly affected by it....when i submitted A i was 7th in standings and i remained in the top 20 till about 30 minutes into contest, so i thought B must be very difficult as very few people had done it till then, and i tried to hack instead of attempt B....after 50 minutes into contest i had moved to 400th in standings, i was like WTF!!!

Codeforces, please do something to fix the lengthy queue problem! ur coders, for god's sake!!

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

    Exactly... It really happens... Specially for the coders like us(Specialist, pupil & newbie). We have to keep an eye in the standing too. But when this situation occurs, it is really difficult to realize the difficulty of the problems. :(

    Again, if I submit a problem but if it stays in queue for the long times, then it's hard to give concentration to another problem. And if I get "wrong answer" verdict after a long queue, it effects standing too. If I get this verdict few minutes ago, I can re-think my solution few minutes ago. Thus I could submit the problem again few minutes ago saving time penalty.

    I think(like many others commented in this blog), contest should be unrated when "long time queue problem" happens. It will be fair, I think.

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

      Hmm, I totally agree with you except the last paragraph of your comment. There are usually some technical problems in CF contests, like long queue or server down, but the circumstance is the same for all coders. So I think there is no reason to make the contest unrated because of "unfairness".

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

        Ok... Lets see two cases :

        Case 1: Usual contest. No problem of long time queue. Mr. A submitted a solution and the solution is ok. Mr. B submitted a solution but "wrong answer"(You know, it can be happened even for a Grandmaster too). He resubmitted it within one or two minutes. And this time it is ok.

        Case 2: The contest like last one. Mr. A & Mr. B both submitted a solution and there is no verdict. After 10 or 15 minutes the verdict is given. Solution for Mr. A is ok and solution for Mr. B is wrong.

        Now think, In last contest, someone got verdict even if he/she submit a solution later while the contestant had submitted a solution earlier didn't get any verdict. So there are many chances for some other contestants to enter between Mr. A & Mr. B in the standing.

        I've told "unfair" thinking this. And in my view this two cases can never be same. In case 2, if there is no "long queue" problem, Mr. B could get a chance to resubmit his solution within one or two minutes. But for "long queue" problem, he didn't get this chance. Moreover, some other contestants also entered between Mr. A & Mr. B.

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

The descriptions are so bad!!!

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

The problems are translated well , but all problems are too long ! Shortering some problems will be better .

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

My idea in problem D is: Take an arbitary silo u and check the total danger of all possible S which are adjacent to u.

Let deg[u] be the number of silos which has a passage to u. Consider an arbitary passage (u,v) which has danger c. Assume that (u,v) appears in S, then the total danger increases by c. So we must find out how many times (u,v) appears, which is equals to how many S which contains (u,v). We must choose (k-1) other silos from the set of the other (deg[u]-1) silos, so it would be C(deg[u]-1,k-1).

Every passage from u appears exactly C(deg[u]-1,k-1) times, so let s[u] be the sum of the danger of all passages from u. The total danger of all possible S adjacent to u is: s[u]*C(deg[u]-1,k-1).

Then, the answer of the problem is: (s[1]*C(deg[1]-1,k-1)+s[2]*C(deg[2]-1,k-1])+...) / C(n,k) (C(n,k) is the number of all S possible)

The problem here is: how to handle the C(n,k), which should be huge?

I use Extended in Pascal and /C(n,k) by every s[u]*C(deg[u]-1,k-1). It's easy to see that C(deg[u]-1,k-1)/C(n,k)=k/(n-k+1)*(deg[u]-1-0)/(n-0)*(deg[u]-1-1)/(n-1)*...

It's not very precise and I got WA on test 21:

Output

1999999999

Answer

2000000000

Anybody has an idea how to handle this? Coding big number would be too complicated.

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

Was a tough contest indeed as the problem statements were complicated to understand.Hopefully will get better problem statements from the next contest..

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

I'm trying this problem:

http://mirror.codeforces.com/contest/332/problem/B

CF shows WA for the 1st test case.

Test #1

5 2
3 6 1 1 6

Correct output

1 4

And my code gives correct output in my PC and in Ideone too.

http://ideone.com/cTqaKy

But it gives

2 4

in CF!!!

http://mirror.codeforces.com/contest/332/submission/4171816

Can anyone please tell me where is the problem? :O

→ Reply