Теперь раздел EDU доступен и на английском языке ×

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

Автор vovuh, история, 11 месяцев назад, По-русски,

<almost-copy-pasted-part>

Привет! В 13.08.2019 17:35 (Московское время) начнётся Codeforces Round #579 (Div. 3) — очередной Codeforces раунд для третьего дивизиона. В этом раунде будет 6 или 7 задач (или 8), которые подобраны по сложности так, чтобы составить интересное соревнование для участников с рейтингами до 1600. Однако все желающие, чей рейтинг 1600 и выше могут зарегистрироваться на раунд вне конкурса.

Раунд пройдет по правилам образовательных раундов. Таким образом, во время раунда задачи будут тестироваться на предварительных тестах, а после раунда будет 12-ти часовая фаза открытых взломов. Я постарался сделать приличные тесты — так же как и вы буду расстроен, если у многих попадают решения после окончания контеста.

Вам будет предложено 6 или 7 (или 8) задач и 2 часа на их решение.

Штраф за неверную попытку в этом раунде (и последующих Div. 3 раундах) будет равняться 10 минутам.

Напоминаем, что в таблицу официальных результатов попадут только достоверные участники третьего дивизиона. Как написано по ссылке — это вынужденная мера для борьбы с неспортивным поведением. Для квалификации в качестве достоверного участника третьего дивизиона надо:

  • принять участие не менее чем в двух рейтинговых раундах (и решить в каждом из них хотя бы одну задачу),
  • не иметь в рейтинге точку 1900 или выше.

Независимо от того являетесь вы достоверными участниками третьего дивизиона или нет, если ваш рейтинг менее 1600, то раунд для вас будет рейтинговым.

Спасибо MikeMirzayanov за платформы, помощь с идеями для задач и координацию моей работы. Спасибо моим очень хорошим друзьям Михаилу PikMike Пикляеву, Максиму Ne0n25 Мещерякову и Ивану BledDest Андросову за помощь в подготовке и тестирование раунда.

Удачи!

Также хочу сказать, что участники, намеренно отправляющие неверные решения и взламывающие их после окончания соревнования (пример), не будут показаны в таблице лидеров по взломам.

</almost-copy-pasted-part>

UPD: Разбор опубликован!

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

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

Auto comment: topic has been translated by Vovuh (original revision, translated revision, compare)

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

Автокомментарий: текст был обновлен пользователем Vovuh (предыдущая версия, новая версия, сравнить).

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

I hope it will be a good contest!

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

I hope this round will rebuild our shattered hope on easy rounds.

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

I love Div. 3 rounds. I eagerly wait for it.

»
11 месяцев назад, # |
Rev. 3   Проголосовать: нравится -14 Проголосовать: не нравится

Div3! Long time no see!

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

Best wishes to everyone!

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

Vovuh's rounds are always good!

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

Good luck everybody =)

»
11 месяцев назад, # |
Rev. 3   Проголосовать: нравится -34 Проголосовать: не нравится

After this contest my final exam will be started....But I will keep doing contest

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

Best ways to increase your contribution :)

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

Thanks MikeMirzayanov for adding Diagnostics Hint feature on RE.

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

    Sorry to disappoint you but the diagnostic hint is disabled in contests.

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

I hope it'll be a good contest;

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

Slide2.PNG

This is participants attending this contest at night 24:00.

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

Will the downtime of polygon affect us? Will there be testing in the contest?

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

I didn't do much with my youtube channel recently because I was busy with summer schools and stuff, and this is bad for publicity :)
So I guess I will do screencast with English commentary for this round and I'll try to go more in depth about solutions. That is, if Mike and team will fix Polygon. Hope to see you on the channel!

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

Is there any negative point for the unsuccessful hacking attempt during the 12 hours of hacking period?

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

    No. And no positive point for successful hacking attempt either.

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

Unfortunately there is an issue with CF-Predictor and it will not be available during coding phase of this contest. CF-Predictor is going to be back after 22:00 UTC today.

I'm very sorry for the inconvenience.

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

Me before Contest : second thing don't tell what you think I will be I'm the one at the sail I'm the master of my seeeeooh oooh
After Contest : Paaaaaain you made a you made a believer

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

i need to increse my rating !! hope this round helps:)

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

No stress Happy round

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

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

Long queue times anyone?

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

Long queue times anyone? Sorry posted previous comment in russian :C

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

Oh my god! Queueueueueueforces

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

The system is not allowing me to submit even a single solution. It is always showing "You have submitted exactly the same code before". please help!!

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

    It means that the the solution has been submitted. You don't have to submit again.

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

Thanks for the round. It sucks. Can u fix your servers pls, the submission was in queue for about 7 minutes. Make it unrated or increase the time. Thanks

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

    Please be patient, they said they are fixing it, besides it's happening with all of us.

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

    You have not even submitted anything. Another fake account ?

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

    To solve problems or for learning from this platform, we don't need to pay anything. It's totally opensource. This community help us with many things. Imagine the number of submissions per moment. It's pretty obvious that there will be problems sometime. Just be patient.

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

contest should be unrated i submited my solution 12 mins ago

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

Queueforces Div3

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

I am back on code forces after a year, and it still hangs a lot :P

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

I use gmail for codeforces. How can i enter in codeforces2?

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

MY CUR PING : 600000 ms and it keeps on increasing :/

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

MY CUR PING : 600000 ms and it keeps on increasing :/

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

pls make it unrated!!!

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

Contest extended by 20 minutes, but the situation that has already happened cannot be reversed. It's not good for successful contest. :(

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

make this round unrated

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

Wondering what happens if you hack a solution, and it gets compilation error.

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

Me waiting for the verdicts.

»
11 месяцев назад, # |
Rev. 4   Проголосовать: нравится -13 Проголосовать: не нравится

deleted

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

Is there a solution in python that runs in time for D2? If not, then why support it at all! frustrated ^^ The problem was very nice to think about, thank you — I am curious what I did wrong...

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

What is TC 37 in F1 ?

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

What is the test case #37 problem F1?

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

Sorry for slow website and judge queue. I think it was the first major queue during the last months. Actually, I do not understand the reason for now: is it because of too heavy tests + easy problems or there is another reason. I'll investigate it. I'm doubly upset because I was thinking about ideas for these problems for several days (it seems that all ideas belong to me). I hope you enjoyed the problems!

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

    Even though it queued a bit in between, it turned out to be a good contest. At least for me, I enjoyed it.

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

    Really enjoyed the problems, Thanks a lot

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

    Hello... I login into codeforces using the gmail account ; but it was not there on the alternate version of the website ( The light version ) ...

    Is there someway of login on that light version for people who login there accounts using gmail...? Please suggest ; thanks in advance...!

    Edit : Got it...! Thanks...!

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

    Are you feeding the hamster properly?

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

Upd: now I got what is the problem with C. Can you tell me what is wrong with other ones?

Can someone please tell me why I got WA on all of my submissions in this contest? (except A)

https://codeforces.com/contest/1203/submission/58755675

https://codeforces.com/contest/1203/submission/58763681

https://codeforces.com/contest/1203/submission/58744361

https://codeforces.com/contest/1203/submission/58770060

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

What is testcase 33 in D2?

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

Failed to solve a QUEUE question in interview this morning, and now CF is showing me QUEUEEEEEEEEE. God's pun game is strong :(

Could have made WA to AC if it wasn't QUEUEEEE, this is frustrating..

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

I think the order should have been C-A-E-B-D-F, but I suppose it doesn't really matter in Div 3 contests.

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

how to solve F2? I spent 2 hours thinking :( . Is there some standard algorithm?

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

    First do the ones with positive reward, then most possible ones with negative reward by knapsack.

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

in queue:)

»
11 месяцев назад, # |
Rev. 3   Проголосовать: нравится -6 Проголосовать: не нравится

R.I.P QUEUEFORCES

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

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

36 hours hacking phase?

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

F2 is similar to Problem I in NWERC2017.

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

why is the open hacking phase of 36 hrs??

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

this contest — queue = PERFECT!!

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

Why the duration of open hack is 36 hours, not 12?

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

Why does the timer for open hacking (https://codeforces.com/contest/1203/standings) say that the open hacking phase lasts over 35 hours?

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

still 36 hours open hacking?

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

Contest was nice.

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

This contest should get unrated. I had to wait for a long time to see the whether the test cases passed or not. This wasted a lot of time of mine.

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

it seems Dsiv.3 always have a huge number of participations this round have a 13216 participations, which I think is one of the most participations in contests. maybe it should increase the number of Div.3?

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

    Increasing the number may cause the quality goes a little bad. Plus, there is once-a-week Educational rounds.

»
11 месяцев назад, # |
  Проголосовать: нравится +21 Проголосовать: не нравится
»
11 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How to use m2.codeforce?

I only use the auto?(one click?) login of Gmail.

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

Please help with the solution of F2

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

I'm getting WA on test case 18 in problem D2. Could someone help me to figure out what is going wrong. This is my submission 58778018. Thanks in advance.

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

    Replace else in last for with if (i < n - 1), because there is a case, where removing substring is between $$$pre[0]$$$ and $$$suff[1]$$$.

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

how to solve f1 ??

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

Does the hacking in hacking phase gives points?

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

Why does my submission TLE, it is O(n*n), it should work totally fine in 2s as n is 100, my submission is submission

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

How to sort the input in optimal order in F2 ?

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

In question C I got TLE in this submission 58730683 and pretest passed in this 58757237 can anyone explain why ??????

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

    Maybe it's because of the time it takes your gcd function to go from one step to the other

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

      I also got TLE in test 5 during the constest. I used faster input methods and got AC. As you can see your solution ran in 850 ms, which is just a bit below TLE.

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

    In the second loop, i*i can reach 10^12 which won't fit into int, I changed int to long long and resubmitted your solution and got it accepted.

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

I think the problems are really great, if it not were for the technical issues it might be an excellent contest.

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

Best ways to get downvotes in a div.3 post:

Lv.1 wish a good contest!

Lv.2 No broken div.3 again!

Lv.5 WTF, this is a div.2 or even div 1.5!

Lv.10 See this is good examples of div 3...........

Lv.100 This comment is hidden because of too negative feedback, click here to view it

Lv.999 Please give me upvotes.

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

The common divisor of 2 integers $$$a, b$$$ is the divisor of $$$gcd(a,b)$$$. I tried to prove in the way.
Every integer $$$x$$$ can be rewrite under the form of multiple of prime factors:

$$$x = p_1^{m_1} . p_2^{m_2} ... p_k^{m_k}$$$

$. &

$$$ y = p_1^{n_1} . p_2^{n_2} ... p_l^{n_l} $$$

We construct $$$gcd(a, b)$$$ by choosing all common prime factors p with the lowest exponent each factor.

And, we construct a arbitrary common divisor by choosing some common prime factors with the exponent each factor always less or equal to the lowest (i choosed in gcd).
Following this manner, the common divisor of $$$a, b$$$ is always divisor of $$$gcd(a, b)$$$.

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

I think this Codeforces round is a bit easy, but it's still very good, too. A good writer with a good round.

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

thank to the extend 20 minutes, I can solve the D2 in the last minute. however, waiting for 3 problems' judge is not a good feeling. hope nobody hack me so that i can be an expert this time.

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

How to solve D2 Remove the Substring (hard version)(https://codeforces.com/contest/1203/problem/D2) ?

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

    There are 2 cases: 1)Answer — prefix or suffix of string s 2)Consider 2 subsequences: leftmost and rightmost.Assume that we take first i letters from leftmost subs. and the rest we take from rightmost.So you have to check all values such as : rightmost[i + 1] — leftmost[i], and maximize it.

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

    I like a neat and self-explaining solution (58718869) of D2 by icecuber, by the way. (The idea seems to be the same as index_ proposed.)

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

is this contest rated??

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

Can F1/F2 be solved by some Greedy approach? Many solved it by Dynamic Programming. I tried Greedy during the contest but it failed.

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

    if bi is bigger than 0 then use greedy, add them all if ai is smaller than r. and for left bi which is smaller than 0 use dynamic programming

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

Добрый день!

я получил сообщение, о том, что мой код на С задачу идентичен решению другого пользователя. Я хотел бы сказать, что это не случайность. Я действительно скопировал его код, о чём сейчас сожалею. Прошу прощения за нарушение правил и обещаю, что такого больше не повториться

Спасибо

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

Can someone explain the idea behind problem D?

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

    find the rightmost place and the leftmost place in s for each letter in t, then (leftmost[i] — rightmost[i + 1]) for every letter in t, get the max one, that is the answer

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

I have got this message from System

Attention!

Your solution 58745781 for the problem 1203D1 significantly coincides with solutions Sukarna_Paul/58745781, ManBug/58766521, CODE_IS_LIFE/58770117. Such a coincidence is a clear rules violation. Note that unintentional leakage is also a violation. For example, do not use ideone.com with the default settings (public access to your code). If you have conclusive evidence that a coincidence has occurred due to the use of a common source published before the competition, write a comment to post about the round with all the details. More information can be found at http://codeforces.com/blog/entry/8790. Such violation of the rules may be the reason for blocking your account or other penalties. In case of repeated violations, your account may be blocked.

But I don't even know those guys with whom my code has been matched . Even I myself surprised how it matched . Its a coincidence for sure .

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

Problem F is a cleverly disguised "regular bracket sequence" problem. See 1745 on timus.

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

Editorial by me incase anyone still needs it:

A. Circle of Students

explanation
soln

B. Equal Rectangles

explanation
soln

C. Common Divisors

explanation
soln

D. Remove the Substring

explanation
soln

E. Boxers

explanation
soln

F. Complete the Projects

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

    How can we prove that projects should be considered in decreasing order of a+b?

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

      By exchange argument (Um_nik's video has pretty good explanation)

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

        You actually watched this... I don't understand why, but ok, looks like it worth doing :)

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

          I came up with knapsack idea but then could not figure out sorting order (I still don't get intuition behind it) and I wrote some really strange thing with bitmasks which worked somehow but I was sure there is simpler solution and there was no editorials so I checked the video. I did enjoy parts I have seen tho, if you're seeking for some feedback :)

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

            Intuitive intuition: Let's look on the process from the end, working backwards in time. We have to have at least $$$a_{i} + b_{i}$$$ rating, and now these projects are good (we are going back in time so our rating will increase), and it is obvious that we should do the projects in order of increasing necessary rating (which is $$$a_{i} + b_{i}$$$ now).

            Professional intuition: I'm sure that I should sort the projects according to some rule, so I will write inequalities for exchange argument and see what I get. You can see in screencast that at first I guessed wrong, and even with correct comparator I was unsure until I wrote the inequalities and everything worked out.

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

      Lets say you have at the moment rating r. And you have (a1, b1), (a2, b2)... (an, bn). Assume we already have ordered set of problems we take (No matter what this order is). Then for each taken project: ai >= r + b1 + b2 + ... + b(i — 1). So you can add to both parts bi and get (ai + bi) >= r + b1 + b2 + ... + bi. So for each i you need ai + bi just not less than some const. That gives us right to assume that if we have correct order then you can take problems in decreasing order of (ai + bi).

      P.S. There are some flaws I think, but common logic is the same.

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

        Your inequality is wrong: instead of ai >= r + ... , it should be ai <= r + ... Since we require the current rating to be >= the project requirement.

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

          Oh thanks. So final inequality is ai + bi <= const. And there is more logic to sort in decrease order.

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

      Let say we have 2 "negative" projects (a1, -b1), (a2,-b2) with b1, b2 > 0 and a1-b1<=a2-b2 and we can successfully complete project (a1, -b1) first follow by project (a2,-b2). Then we can always change the order and successfully do (a2, -b2) first follow by (a1, -b1): + complete (a1, -b1) equivalent to r>=a1 and r-b1>=0. Then do (a2,-b2) equivalent to r-b1>=a2 and r-b1-b2>=0. + complete (a2,-b2) first equivalent to r>=a2 and r-b2>=0. Then do (a1, -b1) equivalent to r-b2>=a1 and r-b1-b2>=0. All these conditions can be followed from above (where r-b2>=a1 because we have r-b1>=a2 and a1-b1<=a2-b2)

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

    (ooops... this was already mentioned in the official editorial)

    For C. Common Divisors (1203C - Common Divisors),
    prime factorization is not necessary to pass the tests.
    Alternatively, we can iterate from $$$1$$$ to $$$\sqrt{g}$$$ (order of $$$10^6$$$) and find each possible pair of divisors (58753671).

    P.S. Thanks for your tutorial!

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

Can anyone please help me to understand the problem E? I dont understand the problem for a while. It would be really helpfull. Thanks in advance. :)

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

    You mean you do not understand the problem statement?

    We are choosing a subset of the original ($$$a_1, a_2, ... a_n$$$) list of weights.
    We construct another list consisting of the chosen weights.
    We can modify some of the chosen weights:
    value $$$a_i$$$, if chosen, becomes $$$(a_i-1)$$$, $$$a_i$$$, or $$$(a_i+1)$$$ in our new list.
    Our task is to choose and modify weights in such a way that all values in our new list are unique.
    More than that, we should do that so that the size of our new list would be as large as possible.
    The answer to the problem is the size of a such list.

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

Can somebody tell me what is wrong with my submission?

https://codeforces.com/contest/1203/submission/59493558