Kniaz's blog

Codeforces Round #378 (Div. 2)
By Kniaz, history, 8 years ago, translation, In English

Hello!

Next Codeforces round #378 for participants from the second division will take place on October 31, 2016 at 17:05 MSK(Moscow time). Traditionally, participants from the first division are able to participate out of the contest.

This round will be unusual:participants will be given six problems and two and a half hours to solve these problems. Pay attention to the unusual time of the beginning of a round!

I want to thank Nikolay Kalinin (KAN) for help with preparation of this round, Tatiana Semenova (Tatiana_S) for translation of statements and Mike Mirzayanov (MikeMirzayanov) for great Codeforces and Polygon systems and also for the help in preparation of a contest and the ideas for several tasks.

It is my first round and I hope you will appreciate it.

The scoring is 500-1000-2000-2000-2750-3000.

Congrats to the winners!

Div. 2

  1. Abdelfatah_Elsisi

  2. knp

  3. ahihi_do_ngok

  4. Thaddeus

  5. miagkov

  6. mayuntao

  7. __0v0__

  8. den2204

  9. CorrelationDecay

  10. goodthingstaketime_._

Div. 1

  1. uwi

  2. dreamoon_love_AA

  3. netman

  4. MrDindows

  5. arsijo

Editorial

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

Comments Comments (231)
| Write comment?
»
8 years ago, # |
  Vote: I like it +40 Vote: I do not like it

So, Delinur is back as a translator at Codeforces :D

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

    OK, yesterday in the announcement it was mentioned that Delinur translated the problems, today it is written that Tatiana_S did the translation, I want my up-votes back, it's not my mistake :(

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

I hope your first round will be a great round.

Good luck

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

Unusual rounds.. unusual rounds everywhere

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

I'm sure It'll be a very beautiful round <3 _ <3

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

I hope you make next contests on sundays, since most people can't participate on mondays.

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

    I wonder if anyone is going to get raided by treat or trick while competing.

    Anyways, Sunday round should be much more better, and I am pretty sure that many people are going to hang out on Hallo... Wait...

    Forever alone

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

    I agree, Sunday is the safest option.

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

I was hoping for special Halloween round, but it seems in vain

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

I like six-problem rounds, my top 3 best rounds are all six-problem rounds :D

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

A bad time for the Chinese...QAQQQ However, happy Halloween!

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

Can't play 'trick or treat' on the Halloween EVE.. So sad! :(

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

i hope it will be a beautiful round

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

I hope problem difficulties are gradual.

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

I am interested about your handle. Can somebody pronounce it to me? I have not seen this type of names earlier.

Finally, Happy Halloween contest to all! Hope to see some scary hard easy problems :D

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

Damn!!

where is the CF rounds for div1 only

about 40 days since last div1 round

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

    Canada cup was for DIV.1 and DIV.2.

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

      Which part of "div1 only" you didn't understand :\

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

Finally a regular codeforces round after two weeks. Thanks Kniaz for preparing this round. Hopefully everything will be fine :D

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

but i dont think it unusual .. because the current three contests are similarly : six problems with two and a half hours .. but i hope i can do better than my previous contests..

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

Good Luck!

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

Thanks for this contest!

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

Does Codeforces plan to change its format (or it has already changed it)? All recent contests have 6 problems and 2.5 hours.

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

    I think it is just a coincidence that recently the problemsetters have sets of 6 problems :)

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

      Possible, but with this one it's 5 Div2 rounds in a row (counting Technocup too) with 6 problems.

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

        Technocup 2017 — Elimination Round 2 after three weeks is just two hours length...

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

Thank this unusual time i can go to sleep early

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

Score distribution ?

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

In Problem A the statement says that the grasshopper can jump on vowels of English alphabet, yet the image and the paragraph below the image feature letter Y among as a vowel. AFAIK, Y is not a vowel, but a consonant.

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

    I am not sure if this incorrect translation can be remedied at this point, but please consider any possible steps you may take in order to prevent quite a few people like myself being victims to errors in translation. (there are 4 people in my room who considered the phrase "English vowels" to only mean 'A', 'E', 'I', 'O', 'U')

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

      Did the pretests not cover Y being a vowel? Were you able to hack them?

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

        Yes. Pretests were not having Y. I hacked one such solution.

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

          Yeah, I hacked 3.

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

            I just realised you can continue hacking the same person's solution as long as they're uploading new submissions :(

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

          I was hacked because of 'Y'...

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

      It said "The following letters are vowels: 'A', 'E', 'I', 'O', 'U' and 'Y'." right below the picture in Problem A. In this https://simple.wikipedia.org/wiki/Vowel wikipedia page it says that vowels can be: "A, E, I, O, U, and sometimes Y".

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

    As it's explicitly written in the statement which characters are vowels as you said, there's no point of arguing about it, everyone should follow the statement in order to solve the problem. Also https://en.oxforddictionaries.com/explore/is-the-letter-y-a-vowel-or-a-consonant.

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

Educational rounds are really useful!

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

How to solve C?

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

    I use greedy and prefix sums!

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

      I divided A into contiguous blocks mapped to each index of B, such that sum of the block is equal to element at that index in B. Then picked the largest element in the block such that at least left or right of it has a smaller value and then made this monster eat all monsters to its left followed by all monsters to its right, or vice versa depending on which side has a smaller value than the largest element.

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

        ACCEPTED ?

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

          Actually, I didn't finish it in time during contest. I submitted in practice, and I was printing it wrong. Logic is correct though.

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

            Yes your logic is correct.I implemented the same logic during the contest.

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

    You should choose m segments such that i-th segments sum is equal to b[i].

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

    Consider first element of ending array. It must be formed by first elements of original array (else where does first monster go?). So it suffices to solve the problem in the case of ending state a single monster (then apply this to each range by precalculating partial sums). This can be done by identifying a monster of maximum size that is bigger than at least one of its neighbors (if none exists, then solution does not exist), and having it eat everything.

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

    Notice that you can only convert the initial array into arrays which contain elements which are contiguous sums of elements of the first array. Now, in order to generate the procedure, all you have to do is in every subsequence, find the largest element and go left and right to consume all the others (as it will only become larger, it will not create problems). You also have to take care of cases when the largest cannot go either left or right.

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

PLease tell me how to solve C and D!! I only solved A and B I tried to solve D in O(n^2) bruteforce but it got tle of course....

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

    D is enough to maintain hash of (pairs -> list of third dimension) for all 3 possible pairs (first sort the dimensions for each brick).

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

      Why hash, you need no hash, sort the array and check neighour bricks.

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

        Of course other solutions may exist. Hashing is simply the most natural one.

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

    D

    Imagine the shape described by the problem. It becomes obvious that the sphere is limited by the edge that has minimum length. You have block A that you are considering. To use A and B (another block) the value of some area must be the same (both in size of the area and shape). But there's something more: if you put A and B together, you are basically increasing the length of the edge that you didn't use to get the area. So this length that you are increasing needs to be the minimum length of block A and B, otherwise some length you used on the common intersection is already limiting the volume of the sphere and you already have the maximum volume you could get using this union. The max volume in this case will be limited by the minimum between the sum of the edges that A and B aren't using and the minimum edge of the intersecting area (because if the sum is greater than this, now this is the limiting factor of the volume of the sphere).

    Now, to get the answer from this you have a vector of (max_area, minimum side of area, side not used in area) and sort it. The blocks that you can glue together are next to each other, so you can easily consider all the unions.

    edit: now that I think about it, you just need the dimensions sorted and check if the 2 maximum sides match, but the thinking process is the same.

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

    For problem D: Basic observation is that if you have parallelepiped (lol I copyed it from statement :D) of size a * b * c, then the radius of the inner sphere is min(a, b, c) / 2. Also you can glue two parallelepipeds together only and only if they have two common edges of the same length. After that you should use a data structure like std::map<pair<int,int>, pair<int,int>>. In this DS you keep the maximum possible 3rd edge length for given a and b edge lengths, after filling this DS you can use a simple loop to get the answer. Complexity is

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

      This is what I did. Failed the system tests. Must have missed something. Did it work out for you?

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

        Failed test case 15.

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

        Did you check if any element in the pair which acts as key for the map is less than the glued dimension's measure?

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

      Pretty much exactly what I did, but got TLE on Test case 32 :(

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

how to calculate max volume for k=1 in D

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

    For a rectangular parallelepiped of dimensions a×b×c, the radius of the inscribed sphere is min(a, b, c) / 2.

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

How to solve problem E? Any small hints?

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

    The jumping root is regular, consider current step is right, so we jump right until reaching the first left step(now all the steps we have visited is left), then we jump left until reaching the first right(now all the steps we have visited is right), and so on until jump out, the answer has two parts, here consider the left part(distance we go at left side of current step), (curIndex — leftIndex1) + (curIndex — leftIndex2) + ...= totLeftNum*curIndex — (leftIndex1 + leftIndex2 + ...)

    To calculate the answer in O(nlog(n)), precalculate several arrays, lcntUp(number of up steps from left), lsumUp(the sum of every up index from left) and rcntDown, rSumDown. for every step there are 4 cases.

    Sorry for my poor English.

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

    Consider position i. Let char be 'U' there. The movement will be oscillatory. You will move to first 'D' above i, then to first 'U' below i, then to second 'D' above i, then to second 'U' below i and so on. I advise just running through an example on paper to see this. So, if you know the count of Us below and Ds above, you get to know whether you will exit from top or bottom. Then just calculate the total distance travelled. The case for when str[i] = 'D' is analogous. So each i can be dealt with in O(1). :)

    Code

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

Tried to hack this solution for Problem B with the following test case.

No initialization done whatsoever in the code. Still no hack :(

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

    The variables are global, so initialized to 0

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

Typed if (t&(1>>k)) instead of if (t&(1<<i)) in problem F, lost 3000 points...

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

    WOW , how could that pass the pretests ?
    it should completely change the answer

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

      He didn't pass the pretests. He meant that fixing the line helped him get AC verdict.

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

Solved D but Just fell short of 2 minutes from submitting C.Need to boost my speed.

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

only two minutes before the end of the round I realized that o(n^2) solution can pass the pretest for problem D
I could have hacked a lot of participants
BTW, problem C is sucks

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

    However my O(n^2) solution submitted and the result is TLE in pretest 7.

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

      Yeah, my O(n^2) solution also failed on pretest 7. Managed to get it to O(N*log N) but it took another 20 minutes to complete it.

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

To include Hacks like in problem A IMO should be controversial.

Well I don't know but hacks do change the contest for me so in my selfish opinion hacks should test algorithmic incorrectness . Any other views?

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

    yup,i agree with u.

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

    I agree. It is more of a problem of one's familiarity with English language.

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

      Why would you say that? The statement isn't clear or what? It clearly says which letters are considered to be vowels.

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

      so you have read "and" as "not" ?

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

    I think that on the one hand, the current hacking system is not fair. According to who is in your room, you may hack between 0 and n >> 1 solutions. Getting 0 hacking point or 1000 hacking points may be the result of your luck, more than of your hacking skills.

    On the other hand, I'm not sure letting everyone hack anyone would be a great idea. Indeed, we may see one day someone winning the contest with one problem solved and 70 hacks.

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

What is test 68 on D? I wish I hadn't missed it!

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

I failed system test on D(test case 14).Any boundary case?

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

Is there a problem with Codeforces servers? I was repeatedly getting 504 gateway timeout error while trying to submit my solutions during the contest. I was submitting my solutions by uploading the code file. Did not try submitting the code directly though.

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

Finished C just 2 minutes after contest ended ;_;

I badly needed rating rise

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

Revenge is a dish best served in the same contest. :)

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

It would be very interesting if Div. 1 could have joined this contest officially.

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

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

waiting for the result of your submission for problem C is harder than waiting for GOT season 7

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

How to solve C ?

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

    I use DP to solve it. DP[i][j] = if i ~ j's number can merge then DP[i][j] = sum( i ~ j ) else -1 if( DP[i][k] != DP[k+1][j] ) DP[i][j] = merge(DP[i][k], DP[k+1][j])

    time complexity is O(N^3)... little tight

    UPD) Source : http://codeforces.me/contest/733/submission/21933533

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

      There's a O(N) solution:

      To get the first wanted weight you need to make some combination using the initial values from the first to some where the sum of all the weights in this interval is the value wanted.

      You do the same for the other wanted weights. If in this process the sum is different than the one you want when it ends (when your interval reaches the end or when the sum is greater or equal to the one wanted), there's no answer. If this process ends and there's not enough groups there's no answer as well.

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

      pl0892029 your solution looks very interesting....can you explain your print function ?

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

        plzz explain your code

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

          Hmm... I can't explain well, but try it.

          Let's begin. testcase is here.

          5
3 3 1 2 2
3
3 3 5

          I intend DP's value is it.

          DP[1][1] = 3
DP[2][2] = 3
DP[3][5] = 5

          focusly, DP[3][5] is derived it's sub-DP value.

          DP[3][5] = DP[3][4] + DP[5][5]

          why not DP[3][3] + DP[4][5], because V[4] and V[5] is same value 2.

          In this context, let's calculate DP[3][4]'s value.

          DP[3][4] = DP[3][3] + DP[4][4]

          so generally dynamic formula is

          if (DP[i][k] != DP[k+1][j])
then DP[i][j] = (DP[i][k] + DP[k+1][j])

          print function is similar binary tree's postorder traversal.

          while calculate DP, we save it's k value. my variable name is PATH.

          and call print. print is trace it using PATH.

          I think it's solution is Unintuitive. other's solution is more helpful. :) ... Haha..

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

In D, for the second sample case, I printed

2

5 1

and got WA. Why? The statement mentions I can print in any order.

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

    It might be an issue with spacing, for example writing "2 \n" instead of "2\n"

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

      I do that all the time. This is the first time I got WA.

      Then I changed 5 1 to 1 5 and got pretests passed. Took me 10-15 minutes, because I thought it's some other serious bug, and test case 2 is different from the second sample case.

      It costed me C.

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

    simple rule can help you in all your life :
    you're always wrong and the statement is always right

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

      I agree with you.

      But life's a little difficult when the checker doesn't agree with the statement.

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

    http://codeforces.me/contest/733/submission/21938356 looks like you didn't print 5 1 huh

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

      Which is funny, because it prints 5 1 when I tested it.
      You can test it on ideone or your local compiler. You'll see 5 1

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

Exiting moment for me ! Waiting eagerly to see the final verdict of my submission on D. Because, after a long time I am able to solve D !! If it got AC, it will be my 2nd time to be able to solve D in contest duration !!

Update: My solution for D is Accepted finally !! I am so much happy and excited that I can't express it !!!

Update2: After rating change done, I became Cyan(Specialist) from green(pupil) ! Exitement overflowed !

→ Reply
»
8 years ago, # |
← Rev. 4   Vote: I like it +9 Vote: I do not like it

This is my room: I'm not very optimistic on passing the system tests on problem C :((

EDIT: I became a victim of test 13 too :(

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

    Yeah same, it's kinda nerve wracking.

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

    test case 13 is killing everyone !!

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

      Am I the only one here who is dying to know what is test 13? (Didn't take part in the contest, but read it and assumed there it should be something really obscure)

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

      I've seen a lot killed by test 11 too

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

      Good from tester perspective to have tricky test cases just in the beginning so that if some solution fails it will fail immediately and don't waste time on server by passing 90 cases and then failing on 91st test case.

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

      Unlucky 13

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

[submission:http://codeforces.me/contest/733/submission/21935362] why did this fail ? :/

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

Codeforces users now : I think they wait something

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

WOW!! actually the first official participant in the contest is Abdelfatah_Elsisi the president of Egypt :V :V

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

should I be very optimistic ??

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

For those who failed problem C: I guess 13th test must be something like

7
1 2 2 2 1 2 179
2
5 5

i. e. some valid yes-case with extra monsters appended to a, so you also need to check whether sum of a equals sum of b (or do some other validity check). Pretests didn't cover it.

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

    In my room 3 participants failed on test 11, including me
    UPDATE: My C failed just because I forgot to reset a varialbe ...

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

    During the contest I was like "Oh, these guys don't check if the current index is still less than or equal to N, let's hack them" (3 successful hacks). And after getting WA #13, I saw that my code checks if the index is less than or equal to M, not N (in array B instead of A) :D

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

Some scary idea for Halloween costume:

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

Wake me up when systest ends.

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

For problem C you can check this hack test:

4

1 2 3 4

3

1 2 3

Answer should be "NO"

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

    LOL. Thank god I first checked if sum of array a and b are equal. I still can't say it will pass. :/

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

    My solution fails this. :( Thanks by the way. Now I don't need to wait for the system testing.

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

    After seeing this test case I got AC now. Just had to add one line that sum(A)== sum(B)

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

I am feeling that MikeMirzayanov turned the last 20% of automatic system test to manual system test :\

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

Submitted solution for problem C at 2:29:59..now just hoping it passes the system tests. :)

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

    Happy Halloween ? Test 13 Again :/

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

      Both C and D failed on test 13.Such a Halloween theme round for me. :D

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

That feel when in the phrase Help Zahar choose such a present so that Kostya can carve a sphere of the maximum possible volume and present it to Zahar. you took attention only to words maximum possible volume and present it and decided that goal is to maximaze volume of parallelepiped, not sphere... =(

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

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

    Bro! plz don't wait for the rating change :P

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

How does this solution pass for problem C? Shouldn't variable sum2 be of type long long as elements in B are ~ 5*10^8 and maximum 500 in number .

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

    Elements in B are 5*10^8. These elements are sums of elements in A that are 10^6.

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

      You didn't get me. number of elements in B are maximum 500 , maximum value of these can be 5*10^8 . maximum value variable sum2 can get is 25*10^9 =2.5 *10^10. which overflows integer range. ( Look at variable sum2 in the code )

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

    I think it passes because he checks for !=

    If sumof A != sumof B, then it doesn't really matter that one of them overflows, because if they are indeed equal, they won't overflow.

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

how to solve c ??

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

    Watch first number in array b, say it's 10. Iterate over array a elements until their sum is 10. If their sum is less or more then it's not possible. If it's 10 then you need to find an element in array a among those you checked that will eat all the other elements. It's one of the maximal elements, consider some tests on a paper to understand which one you have to pick. Once you are done with first number in array b, watch the second number and do the same stuff...

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

That feel when you solve C and D and get a wrong answer at problem B.

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

Any idea why this fails for F? http://codeforces.me/contest/733/submission/21947192 The value of minimum sum matches, but it says "wrong answer lyamzikov shortage" i also checked that it is printing n-1 edges...}

Edit: NVM, Got it! I forgot that there could be multiple edges b/w same pair of vertex in graph too

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

    I think "lyamzikov shortage" means that you use more coins than you're given while lowering drivers' dissatisfaction :)

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

WOW!!

Abdelfatah_Elsisi submit problem D at 17:30 and submit problem C after exact one minute :|

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

    It's called cheating.

    :)

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

    In fact,he might meet the following condition. In a contest,I wrote the code of problem C first but I failed to debug the code. Then I gave it up and wrote the code of problem D. After I sent the code of D,I continued to debug the code of C and sent the code of C after debugging in little time.

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

For Problem C On testcase 1 :

Why this is considered as invalid? Input :

6 1 2 2 2 1 2 2 5 5

My output : YES 4 2 L 1 R 2 R 2 R

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

    You don't have to print the "4".

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

      Ouch, i just realized that. Thanks for answering! It's a funny mistake though

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

When will be editorial?

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

Got C and D wrong by two very small and silly mistakes.... :(
Got them ACed just after the contest ended :P

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

Can I download the test cases for a problem, because my solution is failing on a test case which very large and is not displayed completely in the browser ?

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

Why rating change is so delayed ?

Update: I just commented and reloaded the page and saw that rating change is published... !

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

I heard that 2Pac didn't come back in 2014 because he was waiting for ratings to be updated.

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

In problem E, why am I getting RTE on CF, while its working fine on ideone?

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

what's the procedure of the check against repetitive code？ one of my friend Hu_huhuhuhuhuhu used other's code on problem D(despise him!),but after systest his score was still less than me. but i got -8 on this round(now my rating is less than him), he escaped from decreasing！ it seems if someone's rating will decrease in a round，copy other's code can avoid it. that's rediculous!

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

Something fishy going on with the judge/checker for D.

  1. The output is different when tested and submitted for same test case.
  2. Output differs on different runs of (almost) the same code! I had to make small change between two submissions.
→ Reply
»
8 years ago, # |
  Vote: I like it +4 Vote: I do not like it

For D, what can we do if we are asked to find out the maximum volume? As a * b * c may be as large as 10^27, how can we compare two volumes without BigInt?

p.s. I didn't work out D during the contest because I didn't read the problem carefully and thought it was finding greatest volume. Don't be like me.

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

    the answer can be simple as the min(a, b, c) / 2

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

    You can use log values for comparison

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

      Thanks, maybe, I've tried, but consider this: 999,999,999 ^ 3 and 1,000,000,000 * 999,999,999, 999,999,998. It seems that even using log will return the latter is bigger.

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

    Although this isn't what was required in this problem, but you can simply use double for comparing huge numbers like this. if((double) a1 * b1 * c1 < (double) a2 * b2 * c2) { // my code }

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

      Thanks for your attention.

      According to the following code, with given a1, b1, c1 and a2, b2, c2, it gives a1*b1*c1 == a2*b2*c2.

      #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
	ll a1 = 999999999LL;
	ll b1 = a1, c1 = a1; // all same
	ll a2 =1000000000LL;
	ll b2 = a2 - 1LL, // 999999999 
           c2 = a2 - 2LL;   // 999999998
	bool res = (double) a1 * b1 * c1 < (double) a2 * b2 * c2;
	cout<<res<<endl;
	return 0;
}
      → Reply
      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Notice that a1 * b1 * c1 == a2 * b2 * c2 won't cause you any problems even if they overflow because the overflowed values will probably be equaled if the real values of the multiplications are equaled. But to be on the safe side, use doubles.

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

Orz hahaha

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

any hints about problem E?

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

    Can you determine the which side will you fall off in O(1) with preprocessing? If you can, then can you use this observation tell how many "cycles" you have to go through before falling off?

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

Somebody please compare these two submissions and tell me wtf is going on!!!! One is failing on test case2, other at test case 36.

21957079 21957040

spoiler : they're EXACTLY the same!!!

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

For Problem D,

First of all, for a parallelepiped with sides say l,b and h ,the radius of sphere inscribed in it will be r = min(l,b,h)/2 . So here, to maximize the volume, we need to maximize the radius r. That is we need to maximize the minimum side of parallelepiped.

Now, two parallelepipeds should have atleast two sides identical in order to join them. Lets sort the sides for a parallelepiped in increasing order and do this for all parallelepipeds. After sorting, lets say the sides of a parallelepiped are l,b,h such that l<=b<=h . Now the observation is we need to match only the larger sides i.e. 'b' and 'h' of this parallelepiped with larger sides of other parallelepipeds so that the minimum side of the resulting parallelepiped can be maximum. Why? Because , lets assume we match 'l' and 'b' values of two parallelepipeds then for the resulting parallelepiped the minimum side will remain 'l' . The same thing happens when we match 'l' and 'h' values of two parallelepipeds. But when we match 'b' and 'h' then there is a chance that now the 'l' side of resulting parallelepiped will be greater than 'b' or 'h' as a result our minimum side will become 'b' now.

For help refer to my solution, 21956827

Hope this helps :)

And sorry for my bad English!

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

When will be the editorials published??? Nice problemset Hope they publish it ASAP

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

For problem F, after viewing some other's code. I think I understand it. First, we are actually finding a spanning tree of the graph and are decreasing weights of some of the edges of the tree to get the answer.

Suppose now we happen to know the spanning tree, we can simply invest all of our money into only one edge, whose C is the smallest among edges of the tree, to reduce total 'disatisfaction' as large as possible. Note that we may not be able to invest in any other edge by doing so.

But how can we find the spanning tree — we only know minimal spanning tree algorithm.

Well, let's turn our attention to another point. I mentioned that what you have to do is just to reduce the weight of only ONE edge. So what about enumerate through edges we are going to reduce! Actually, the final spanning tree may be very similar to the minimal spanning tree — intuitively, apart from the edges to reduce, other weights of edges of the spanning tree must be as small as possible. So, suppose we now have the minimal spanning tree T.

And now we want to plug an edge (u, v), which may or may not be in the tree, into T. The only block, if (u, v) is not in the T, is the only path from u to v in T. And if we remove one of the edge of the path from T and plug (u, v) into T, we'll got another spanning tree.

So, you may just remove the edge with the largest weight on path from u to v and plug E into it you will get the answer. But how to find the path from u, v and find the maximal weight along the path? You'll need LCA(Lowest Common Ancester) algorithm, which preprocess the minimal spanning tree.

Sorry for my poor English. But typing solution out really helps me organize my thought.

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

    I was wondering why we just need to reduce the weight of only ONE edge. As you mentioned "what you have to do is just to reduce the weight of only ONE edge".

    Thanks.

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

      Because the weight can be negative

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

      Suppose you want to reduce weight of m edges of a spanning tree, let's number them 1, 2...m, you wan to reduce each edge by ui times, and each edge costs you Ci for reducing once. Then, the result you get is tot - u1 - u2 - ... - um, where u1 * C1 + u2 * C2 + ... + um * Cm ≤ S. Suppose now you select an edge with minimal C, and you can at least reduce u1 + u2 + ... + um times, because: C ≤ Ci and u1 * C + u2 * C + ... + um * C ≤ u1 * C1 + u2 * C2 + ... + um * Cm ≤ S. So reducing only one edge is at least as good as reduce many edges.

      And intuitively, for a fixed spanning tree, you can find the edge with minimal C, then you can reduce the 'dissatisfaction' of the whole tree by S / C. If you select edges with bigger C, you may not be able to reduce the 'dissatisfaction' that much.

      As we don't know whether the edge we are working with is the edge with minimal C, we want the w of remaining edges to be as small as possible, that's why we are replacing edges in MST.

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

For the problem C733C - Epidemic in Monstropolis Although my code is Accepted, but if use this data will wrong answer

23

3 2 1 3 3 3 1 1 2 1 2 1 1 1 2 2 3 1 2 3 3 3 3

5

6 16 5 5 15

Because my answer is NO and the right answer should be "YES" So is the data have BUG? Hope a reply!Thank you!@Kniaz

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

    The answer my program gives is YES 1 R 1 R 4 R 4 L 3 L 2 R 2 R 2 R 2 R 6 L 5 L 4 L 5 L 7 L 6 L 5 R 5 R 5 R You can try it. And my code

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

    I ran this testcase and my AC solution gave NO. I freaked out until I realize the testcase lacks number K (number of elements in B). You scared me :(

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

      I am so sorry! Just now surely lack a "k", you can try again. For this data my accepted program gives "NO"　but I think should be "YES"...

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

wait for my online judge

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

Hi! Can you give me a test example where this does not work:

https://gist.github.com/Vitosh/01e3ce215de5ecb70b42cafc2dd2b8d0

Its from http://codeforces.me/contest/733/problem/B and I think it should be working. However it breaks on test 10 and I cannot see it. Thanks!

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

    You are missing out so many things:

    1. why the "&&(long_left>long_right)" conditions? Sometimes there are more right legs and you need to reduce them to achieve max beauty.

    2. maximising the delta of legs do not guarantee maximum beauty, think about it.

    → Reply