Блог пользователя Kniaz

Автор Kniaz, история, 8 лет назад, По-русски

Доброго времени суток!

31 октября 2016 года в 17:05 MSK (время московское) состоится очередной раунд Codeforces #378 для участников из второго дивизиона. Традиционно, участники из первого дивизиона приглашаются поучаствовать в соревновании вне конкурса.

Этот раунд будет необычным: будет предложено 6 задач и 2,5 часа на их решение. Обратите внимание на необычное время начала раунда!

Хотелось бы сказать большое спасибо Николаю Калинину (KAN) за помощь в подготовке задач, Татьяне Семёновой (Tatiana_S) за перевод условий на английский и Михаилу Мирзаянову (MikeMirzayanov) за замечательные системы Codeforces и Polygon, а также за помощь в подготовке контеста и идеи нескольких задач.

Это мой первый раунд, надеюсь, раунд оценят по достоинству.

Разбалловка: 500-1000-2000-2000-2750-3000.

Поздравляем победителей!

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

Разбор

  • Проголосовать: нравится
  • +251
  • Проголосовать: не нравится

»
8 лет назад, # |
  Проголосовать: нравится +27 Проголосовать: не нравится

Давайте уже 17:05 не называть необычным временем)

»
8 лет назад, # |
  Проголосовать: нравится +40 Проголосовать: не нравится

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

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +174 Проголосовать: не нравится

    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 :(

»
8 лет назад, # |
  Проголосовать: нравится -15 Проголосовать: не нравится

I hope your first round will be a great round.

Good luck

»
8 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

Unusual rounds.. unusual rounds everywhere

»
8 лет назад, # |
  Проголосовать: нравится -56 Проголосовать: не нравится

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

»
8 лет назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

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

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится -28 Проголосовать: не нравится

    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

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    I agree, Sunday is the safest option.

»
8 лет назад, # |
Rev. 2   Проголосовать: нравится +29 Проголосовать: не нравится

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

»
8 лет назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

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

»
8 лет назад, # |
  Проголосовать: нравится +26 Проголосовать: не нравится

KAN — третий координатор раундов Codeforces?

»
8 лет назад, # |
  Проголосовать: нравится -14 Проголосовать: не нравится

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

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
8 лет назад, # |
  Проголосовать: нравится -6 Проголосовать: не нравится

i hope it will be a beautiful round

»
8 лет назад, # |
  Проголосовать: нравится -23 Проголосовать: не нравится

I hope problem difficulties are gradual.

»
8 лет назад, # |
Rev. 2   Проголосовать: нравится +13 Проголосовать: не нравится

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

»
8 лет назад, # |
  Проголосовать: нравится -83 Проголосовать: не нравится

Damn!!

where is the CF rounds for div1 only

about 40 days since last div1 round

»
8 лет назад, # |
  Проголосовать: нравится +14 Проголосовать: не нравится

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

»
8 лет назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

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..

»
8 лет назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

Good Luck!

»
8 лет назад, # |
Rev. 2   Проголосовать: нравится -21 Проголосовать: не нравится

Thanks for this contest!

»
8 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

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

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

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

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится +6 Проголосовать: не нравится

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

      • »
        »
        »
        »
        8 лет назад, # ^ |
          Проголосовать: нравится +5 Проголосовать: не нравится

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

»
8 лет назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

Thank this unusual time i can go to sleep early

»
8 лет назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

Score distribution ?

»
8 лет назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

where is this guy "is it rated" :P

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

»
8 лет назад, # |
  Проголосовать: нравится +79 Проголосовать: не нравится

Чтоб автора пожизненно просили восстановить ответ в каждой задаче.

»
8 лет назад, # |
  Проголосовать: нравится +72 Проголосовать: не нравится
»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How to solve C?

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    I use greedy and prefix sums!

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится +12 Проголосовать: не нравится

      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.

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +7 Проголосовать: не нравится

    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.

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Здравствуйте, пытался сделать свой первый взлом! Когда отправил программу-взломщик, получил такой вердикт:Validator 'val.exe' returns exit code 3 [FAIL Expected EOLN (stdin)]; Что это значит? Заранее спасибо!

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

how to calculate max vol for k=1 in D

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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....

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    8 лет назад, # ^ |
    Rev. 3   Проголосовать: нравится +4 Проголосовать: не нравится

    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.

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    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

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

how to calculate max volume for k=1 in D

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится -10 Проголосовать: не нравится

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

»
8 лет назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

How to solve problem E? Any small hints?

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    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.

  • »
    »
    8 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    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

»
8 лет назад, # |
Rev. 2   Проголосовать: нравится +2 Проголосовать: не нравится

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

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

»
8 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +19 Проголосовать: не нравится

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

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится +5 Проголосовать: не нравится

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

»
8 лет назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

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

»
8 лет назад, # |
  Проголосовать: нравится -6 Проголосовать: не нравится

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

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

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

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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.

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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?

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    yup,i agree with u.

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +4 Проголосовать: не нравится

    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.

»
8 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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

»
8 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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

»
8 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

Может скрывать ВК и e-mail участников пока контест идет? Мне в личку написал левый человек с просьбой скинуть код по А (не знаю на что он надеялся)

»
8 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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.

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Finished C just 2 minutes after contest ended ;_;

I badly needed rating rise

»
8 лет назад, # |
  Проголосовать: нравится +243 Проголосовать: не нравится

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

»
8 лет назад, # |
  Проголосовать: нравится +18 Проголосовать: не нравится

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

»
8 лет назад, # |
  Проголосовать: нравится +116 Проголосовать: не нравится

»
8 лет назад, # |
  Проголосовать: нравится +39 Проголосовать: не нравится

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

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How to solve C?

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How to solve C ?

  • »
    »
    8 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    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://mirror.codeforces.com/contest/733/submission/21933533

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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.

    • »
      »
      »
      8 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

      • »
        »
        »
        »
        8 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        plzz explain your code

        • »
          »
          »
          »
          »
          8 лет назад, # ^ |
          Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

          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..

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

»
8 лет назад, # |
Rev. 3   Проголосовать: нравится +19 Проголосовать: не нравится

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 !

»
8 лет назад, # |
Rev. 4   Проголосовать: нравится +9 Проголосовать: не нравится

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 :(

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    Yeah same, it's kinda nerve wracking.

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    test case 13 is killing everyone !!

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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)

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится +1 Проголосовать: не нравится

      I've seen a lot killed by test 11 too

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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.

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Unlucky 13

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
8 лет назад, # |
  Проголосовать: нравится +27 Проголосовать: не нравится

Codeforces users now : I think they wait something

»
8 лет назад, # |
  Проголосовать: нравится +23 Проголосовать: не нравится

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

»
8 лет назад, # |
  Проголосовать: нравится +35 Проголосовать: не нравится

should I be very optimistic ??

»
8 лет назад, # |
  Проголосовать: нравится +38 Проголосовать: не нравится

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.

  • »
    »
    8 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

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

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +15 Проголосовать: не нравится

    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

»
8 лет назад, # |
  Проголосовать: нравится +96 Проголосовать: не нравится

Some scary idea for Halloween costume:

»
8 лет назад, # |
  Проголосовать: нравится +27 Проголосовать: не нравится

Wake me up when systest ends.

»
8 лет назад, # |
Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

For problem C you can check this hack test:

4

1 2 3 4

3

1 2 3

Answer should be "NO"

»
8 лет назад, # |
  Проголосовать: нравится +29 Проголосовать: не нравится

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

»
8 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

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

»
8 лет назад, # |
Rev. 3   Проголосовать: нравится +19 Проголосовать: не нравится

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... =(

»
8 лет назад, # |
  Проголосовать: нравится +65 Проголосовать: не нравится

»
8 лет назад, # |
Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

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 .

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

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

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится

      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 )

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +6 Проголосовать: не нравится

    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.

»
8 лет назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

Такой себе контест, какой смысл делать претесты если все равно решаешь вслепую?!

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +4 Проголосовать: не нравится

    Как минимум для того, чтобы не прогонять ТЛ-и на систестах

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

how to solve c ??

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    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...

»
8 лет назад, # |
  Проголосовать: нравится -9 Проголосовать: не нравится

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

»
8 лет назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

Any idea why this fails for F? http://mirror.codeforces.com/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

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

»
8 лет назад, # |
  Проголосовать: нравится -8 Проголосовать: не нравится

WOW!!

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

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

For Problem C :

Why This Answer Considered as invalid for testcase 1?

YES 4 2 L 1 R 2 R 2 R

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

When will be editorial?

»
8 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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 ?

»
8 лет назад, # |
Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

Why rating change is so delayed ?

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

»
8 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

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

»
8 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

»
8 лет назад, # |
  Проголосовать: нравится +15 Проголосовать: не нравится

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!

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.
»
8 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

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.

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

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

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    You can use log values for comparison

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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.

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    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 }

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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;
      }
      
      • »
        »
        »
        »
        8 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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.

»
8 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Orz hahaha

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

any hints about problem E?

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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?

»
8 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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!!!

»
8 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

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!

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Ui bai kho qua chiu thoi.

Haha co cl y bai day toi lam 1 dam.

»
8 лет назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

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

»
8 лет назад, # |
Rev. 2   Проголосовать: нравится +11 Проголосовать: не нравится

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.

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Because the weight can be negative

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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.

»
8 лет назад, # |
Rev. 4   Проголосовать: нравится +10 Проголосовать: не нравится

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

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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 :(

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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"...

»
8 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

wait for my online judge

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

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

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

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.