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

Привет, Codeforces!

В 25.05.2023 17:35 (Московское время) состоится Educational Codeforces Round 149 (Rated for Div. 2).

Продолжается серия образовательных раундов в рамках инициативы Harbour.Space University! Подробности о сотрудничестве Harbour.Space University и Codeforces можно прочитать в посте.

Этот раунд будет рейтинговым для участников с рейтингом менее 2100. Соревнование будет проводиться по немного расширенным правилам ICPC. Штраф за каждую неверную посылку до посылки, являющейся полным решением, равен 10 минутам. После окончания раунда будет период времени длительностью в 12 часов, в течение которого вы можете попробовать взломать абсолютно любое решение (в том числе свое). Причем исходный код будет предоставлен не только для чтения, но и для копирования.

Вам будет предложено 6 или 7 задач на 2 часа. Мы надеемся, что вам они покажутся интересными.

Задачи вместе со мной придумывали и готовили Адилбек adedalic Далабаев, Иван BledDest Андросов и Максим Neon Мещеряков. Также большое спасибо Михаилу MikeMirzayanov Мирзаянову за системы Polygon и Codeforces.

Удачи в раунде! Успешных решений!

Также от наших друзей и партнёров из Harbour.Space есть сообщение для вас:

Harbour.Space

Не упустите возможность: полные стипендии доступны в Harbour.Space Бангкок

Отличные новости, Codeforces! Harbour.Space Bangkok Campus предлагает 10 полных стипендий для изучения Computer Science или Data Science!

Присоединяйтесь к нам в Harbour.Space в самом сердце Бангкока, Таиланд, и откройте для себя целый мир возможностей. Мы с гордостью сообщаем, что недавно одержали победу на SWERC, одном из самых престижных соревнований по программированию.

В Harbour.Space у вас будет возможность учиться у таких известных экспертов, как MikeMirzayanov и Errichto. Эти исключительные люди привносят свои знания и понимание отрасли, создавая динамичный опыт обучения.

Став частью нашего динамичного и инклюзивного сообщества, вы будете сотрудничать с блестящими умами, способствуя развитию культуры роста и инноваций. Наши квалифицированные и талантливые студенты имеют возможность соревноваться в ICPC, демонстрируя свои навыки на мировой арене.

Присоединяйтесь к нашим выпускникам, которые работали в ведущих компаниях, таких как IBM, Google, Deloitte, Amazon и других, прокладывая путь к успеху.

Требования:

Обучение: 3 часа в день

За год обучения вы завершите 15 модулей (длительность каждого 3 недели). Ежедневная учебная нагрузка составляет 3 часа, плюс домашнее задание, которое нужно выполнить в свободное время.

Требования университета

  • CV
  • Аттестат об окончании старшей школы/диплом бакалавра
  • Знание английского языка
  • Занятие призового места любого соревнования по программированию — это плюс!

Не забудьте подать заявку до 30го июня, 2023, чтобы иметь шанс получить стипендию и снизить плату за подачу заявления.

Готовы начать свой путь к успеху? Подать заявку сейчас.

Мы с нетерпением ждем вас в нашем университете.

Всего наилучшего,

Команда Harbour.Space

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

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

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

I seriously want that Mike's T-shirt...

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

Please don't be another SpeedForces Edu Round, otherwise excited about this.

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

    Please don't be another HackForces Edu Round

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

    they literally just made speedforces

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

      not really, actuallly problem F seems pretty easy ( I didn't solve it, my solution fails at 23 test case ) .

      My implementation is little hard, SSRS_ has implemented is very easily with two priority queues.

      basically, we need to apply binary search on the final time, and maintain how many editorials we can write in the given time, if we split at index 'i' ( splitting that first person writes as many as editorials from index '1' to index 'i', and second person writes as many editorials from 'i+1' to 'n' within given time ) .

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

" Study in Bangok "

People go there for something else

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

its taking too much time to be in queue is it problem on my end or happening with yall

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

WHY ARE THERE NO TESTERS FOR ANY EDUCATIONAL ROUNDS?

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

this is pure stupidity from the organizers

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

https://mirror.codeforces.com/contest/1837/problems never gets updated! I waited 10 minutes and then finally got to know it's WA on test 1 after 10 minutes when solutions were rejudged. queue is also long, taking so much time for the verdict

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

Still in queue for B. Should i resubmit?

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

https://codeforces.com/contest/1837/submission/207170399 была на 10 минуте, перетестирование позже. Уберите её, пожалуйста!

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

Edu ROUND waste my time and emotions, ALWAYS.

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

stringforce

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

"problems and examples will be in announcements"forces

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

(()deforces

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

I dont think i will participate in edu rounds anymore. I asked if my submission is going to be judged after it was in queue for 10 minutes. While I got the answer it was judged and the answer was "No comments". There is no need to be arrogant and in my opinion that was. Also, this would not happen if they tested the round.

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

    "No comments" is very classic answer if they don't want to tell you anything, it wasn't arrogant (in my opinion).

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

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

This contest is really bad. What is this problem D? The solution is pretty dumb for a D. I think ABCD were really silly and this round is really bad. I liked problem E though.

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

    so u will be getting +delta then!?

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

      I won't but I'm not mad about that. It's just that the contest is unbalanced and problem D shouldn't be like that

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

Why time constraint was so small on F? my nlog^2n solution with segment tree could not pass, had to remake it into a priority_queue solution with same nlog^2n. (smaller constant with priority_queue)

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

    did you use only segment tree ? or was it persistent seg tree ?

    can you please enlighten how to do it with normal seg tree ? ( i used persistent seg tree ) which was huge implementation. :( .

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

      I used normal segment tree. First I created a vector of pairs where I put { a[ i ] , i } the I sorted that vector and assigned an index to each pair. I use that index to store them in segment tree. Then I binary search on the answer. I use two segment trees, for each answer I rebuild both segment trees in the following way: first segment tree is empty, and second segment tree is full with activated nodes. In each node of segment tree I store pairs, where first element is the sum of times of activated verticies and second one is the amount of them. While checking the answer I go from right to left, activiating each vertex of the current pair { a[ i ] , i } in second first segtree and deactivating in the second one. Now what I need to check is if I can get some prefix of both seg trees such their activated times are less then the answer I am checking and the amount of activated verticies is maximum possible. For that I create a recursive function for each segment tree, where I first check the root of tree and its value, if the time of activated verticies stored in the root is less or equal to answer(which I am checking) time then I simply return its activated verticies count, otherwise I check for its left and right children.

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

      207253723

      I used ord array to compress the indices.

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

      You can maintain prefix sums on a Segment tree.

      My solution
»
10 месяцев назад, # |
Rev. 2   Проголосовать: нравится -43 Проголосовать: не нравится

the worst contest

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

another really bad educational round

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

faqin unclear d. its problem. not maze or smthing

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

B completely ruined my round,TEST YOUR PROBLEMS.

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

For the problem D is there any chance that we need to use more than 2 color because i tried many sequence ans only i found only 2 color is enought to paint.

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

Worst contest I have ever seen!..

The sample test case was wrong and it delayed me a lot. Also, because of rejudges, there was a queue so I could not see my verdict for a while.

Also, I could not submit my code in the last 30 seconds maybe it was about my internet but giving the sample wrong was a big mistake :(

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

    I was also unable to submit my code in the last minute. I think we should try using m1.codeforces.com for the next contest

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

Mostly of cheaters them are indian shame on you all cheaters you spoils contest (disclaimer not targeting indians but dumb cheaters for india) all cheaters ban from codeforces this is not your fathers platform you cheat and spoil platform !

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

may anyone help me ,plz? i dont know why does it give me WA (problem B:) https://codeforces.com/contest/1837/submission/207236832

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

Lol i easily fast-solving C in 30 minutes and can solve D in the contest. First see 4k+ can solve D ;))

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

Last tasks DEF look like CDE to be honest.

It was 1st Div. 2 round that i almost have solved full. (but wa2 in F on last minutes)

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

Unrated would be better than this situation

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

Nice E, solved it 2 minutes after contest:)

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

The last 2 rounds made me realise that expert is not for me ;(.

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

i'm gonna cry because of the problem E....

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

Really bad Contest . Solutions can be easily guessed .

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

This is really the most unexperienced game, abcd is violent, e is too big, there is no room to learn, total useless。

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

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

Again, a shit educational round. Problem A,B,C,D can be done in 25-30 minutes and rating depends on whether or not you incorrectly submit B. Last educational round for me,you learn nothing and only have headache.

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

Worst Contest !!! Didn't liked the problems at all

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

Very Cool F except the TL

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

Very bad experience, all the time was wasted on understanding the meaning of the question, and I once doubted whether I was from Earth

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

    That's a very serious concern if you did indeed doubt your origins as you mention...

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

I don't know why I wasted time waiting in the queue. Could have solved other Problems earlier. LMAO

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

How to solve Problem D?

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

Educational Rounds = Lose Rating Rounds.

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

Solved A-E and passed pretest of F in 3899ms (which will be TLE in system test).

A: If x%k!=0, we just need to move by x, otherwise since k>=2 we need to move by x-1, and then move by 1.

B: Consider the longest maximal block of same symbol, let it's length be k. Then If we put 1 at every local minimum and k+1 at every local maximum, we always have enough numbers from 2 to k to fill other positions.

C: We can see that a consecutive block of same numbers (0 or 1) plays the same role as a single number, and more blocks takes more operations to sort the string. Therefore, we can fill '0' into a block of '?' between '0' and '0', fill '1' between '1' and '1', and fill '0' or '1' between '0' and '1'. For these blocks at the front or the back of the string, we can assume that there's an additional '0' at front and '1' at back of the string, which won't affect the answer.

D: For any beautiful sequence the number of occurences of '(' and ')' will be the same, so if they are not the same we can simply output -1. Otherwise, there must be a solution with k<=2. In fact, we can record the prefix-sum of the string (assume '('=1, ')'=-1) and change color whenever the sign of the prefix-sum changes, then brackets with non-negative prefix-sum will form a regular sequence, and other brackets will form a reversed regular sequence.

E: We can see that teams of number [2^(k-1)+1 , 2^k] will lose in the first round, teams of number [2^(k-2)+1 , 2^(k-1)] will lose in the second round, and so on. So in the first round, we check 2^(k-1) pairs of adjacent positions, and each pair must contain a team with number larger than 2^(k-1). If any of such a pair contains 2 numbers > 2^(k-1) or 2 numbers <= 2^(k-1), there's no solution. Otherwise we have 2^a*(b!) ways to arrange teams of number [2^(k-1)+1 , 2^k], where a=(how many pairs of positions are both undefined), b=(how many pairs of positions contains no teams with number > 2^(k-1) ). Then we can eliminate teams with larger number in every pairs, and solve the problem recursively.

F: I tried to solve it by segment tree and ternary search in O(n*(log(n))^2), but it takes too long times to pass the system test. Maybe there will be solution with smaller constant.

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

    Not sure if it is compatible with your solution, but in F replacing segment tree with a priority queue or a set gives AC in approx 3 seconds.

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

      Nope, my solution with std::set gives TL on 23 pretest though I changed cin/cout to scanf/printf and had no stupid memory allocation.

      207257375

      I wish in C++24 std::set is automatically substituted by priority_queue if my code does not contain iterators, BS and etc :)

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

        Probably requires minor constant optimizations. 207226137 passed in 3 seconds.

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

          Quote: "...but in F replacing segment tree with a priority queue or a set..." I mean std::set can't pass TL but std::priority_queue can.

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

    Can you explain bit more about "2^a where a=(how many pairs of positions are both undefined)" in your E's solution?

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

      If a pair of position is -1 -1, then we can put the team with larger number on the left or right of this pair, so each pair gives us 2 options. Otherwise, which number will be larger is determined in this pair.

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

        Dont the numbers in range [1,2^(k-1)].Doesn't they impose constraint on other number ? How can they be placed freely ?

        For suppose, if 1 is place in Xth pair then 2 cant be placed in (X+1)th pair, if they get placed they 2 will get eliminated in second round but they need to continue until finals ?

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

          If a team cannot be decided in kth turn, you bring it to the next turn with -1, You can only count those teams can be determined in kth turn within (2^k-1, 2^k] and leave those undetermined to the (k-1)th turn. The key observation here is when a team gonna lose is fixed at the beginning. So the whole process is like you assign a seed to a team only if that team will lose in that turn.

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

    use binary search on answer in F instead of ternary search, and then priority queue to find maximum numbers <= sum in prefix and suffix

    mine runs in 2.7s

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

    Sorry YocyCraft:( (Hacked)

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

    This guy saves me in every contest with short and on point explanation

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

Five minutes and I would have had my first D problem of division 2 solved in time https://codeforces.com/contest/1837/submission/207261995

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

10k ACs on C and 4k ACs on D, wow! Never seen anything this extreme before.

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

how to solve d

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

Nice contest. Incase you are stuck on Problem A, Problem B, Problem C, Problem D. You can use check the following video tutorial- video link

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

The Worst Education Round I ever seen.

Reasons:

1.Big changes on problem B:Wrong sample,too long queue(after change),etc.This is terrible.

2.Speedy Edu.Problem A,B,C,D is too easy and E is hard.4,600 people passed D,but only 367 pass E.This mean the rank between ~400 and ~4000 is FULLY depend on the Penalty.

More I know:the B is similar as atcoder contests

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

My solution to B got WA on test 1 at first, but once the samples were changed (and before the announcement that the previously solutions would be rejudged) I resubmitted the same code with a no-op to see if it would pass. Then both solutions gave a WA time penalty :(.

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

I didn't know that a priority queue is faster than a multiset, and if the intended solution has a complexity of O(n * log^2n), then, in my opinion, should have also considered the multiset solution.

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

    Priority queue is a binary heap which is faster than any balanced binary search tree by the constant factors and the access time of O(1)

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

So many errors in the statements... Contests of such scale should be thoroughly tested!

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

worst contest I have ever seen!

this round should be unrated due to long queue time(~1 min for every submission) and wrong examples in B.

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

dude python was not working for question c.It was giving tle at testcase 6

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

Problem B has a quite similar approach with this problem.

I find it a bit funny tho because problem B is about <>, problem C is about 01 and problem D is about () lol

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

Mostly of cheaters them are indian shame on you all cheaters you spoils contest (disclaimer not targeting indians but dumb cheaters for india) all cheaters ban from codeforces this is not your fathers platform you cheat and spoil platform !

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

Problem D statement was not clear

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

Using discrete to convert time complexity from nlog(1e18)log(1e9) to nlog(1e18)log(3e5) then pass pretest on Problem F. Time limit is toooooooooo tight.

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

One tip if you got WA on test 8 of E: Please notice the input format.

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

    you are perfectly right! In the contest I have great confidence in my algorithm. But always WA in test8.Damn!When I saw test 8 after contest, I just realized that I mixed up the team ID and seed ID,Oh Damn Damn Damn!!!

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

Can someone please assist me with submission :207266027 ? I am unable to determine why my submission is incorrect. Thank you very much.

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

800-Forces

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

Can anyone please explain why the answer to this test case is 4 for question 'E':

3 -1 7 -1 8 2 -1 -1 5

What I understood from the question is illustrated below: _ & 5th | _ & _ | 8th & _ | 2nd & 4th So according to this arrangement, 4th would have rank '5' which is not desired. So shouldn't the answer be 0?

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

Problem B ruined my contest. Please at least take a glance and make sure that the examples are correct (it was so obvious that the examples were wrong ...).

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

Solution 1837D - Bracket Coloring:

There are only 2 colors required,we can tag them as 1 and 2.

A reverse bracket sequence is a sequence that on reversal becomes a regular bracket sequence

We will categorize all the regular bracket sequences in one color as color 1 and all the reverse bracket sequences in another(Both are considered "Beautiful sequences") as color 2 because all of sequences(regular or reverse) if grouped together with similar types will still hold original sequence type. So our aim is to group all the sequences of one type in one color.

We take a stack and at every iteration check the if the stack is empty or not.If we have traversed through a regular bracket sequence or reverse bracket sequence then it will make the stack empty as we keep removing a pair on match.

A match for a regular bracket sequence is "()" and for a reverse bracket sequence is ")(" ,we put down all the regular bracket sequence as 1 and reverse bracket sequence as 2 and following this approach,this is the solution 207266592

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

Hello, I enjoyed this contest. thanks to the problem setters.

During the contest, I solved problems $$$A - E$$$. Just after the contest, I solved problem $$$F$$$.

Problem $$$A$$$: if $$$N \mod K == 0$$$ it's $$$N-1$$$, $$$1$$$ otherwise it's $$$N$$$.

Problem $$$B$$$: the answer is the longest increasing(or decreasing) subarray.

Problem $$$C$$$: how many disjoint $$$1$$$ s are there ($$$-1$$$ if the last number is $$$1$$$).

Problem $$$D$$$: if the number of opening brackets isn't the same as the number of closing brackets it's $$$-1$$$. otherwise, if it's a beautiful bracket sequence the answer is $$$1$$$ otherwise $$$2$$$. We can color the biggest beautiful bracket sequence with the color $$$1$$$ and the remaining brackets make a beautiful bracket sequence.

Problem $$$E$$$: We know which players will be eliminated in the first round. Let's say there is a $$$P$$$ number of $$$(-1, -1)$$$ matchup, and $$$Q$$$ number of players we need to eliminate on that round. On round $$$k$$$ the number of ways we can place the players that should be eliminated is $$$(2^{P_k}\cdot Q_k!)$$$. Then, we can assume those players are eliminated on that round and solve the problem for $$$k+1$$$-th round. Thus, we can recursively find the answer.

Problem $$$F$$$: I didn't solve this problem during the contest. I used multi_set, which I later changed into priority_queue to get accepted. My time complexity is $$$O(N \log^2 N)$$$. I don't know if the problem setters intended to cut submissions that used set. The idea of this problem is to find the answer with a binary search. For a chosen value, we check for each element to be the last problem of the Monocarp, and find the maximum number of editorials we can make in that situation. If it's over or equal to $$$k$$$ we can make it in for the chosen value. I still think the time limit for this problem is a little too tight.

Overall it was a good contest :)

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

The problems were very easy till D , it must be somewhat tough at least for C and D.

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

please start writing div3 contests

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

I passed F in last two minutes! Hope it won't FST.

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

D can u tell what's wrong with my soln 207261486 first i eliminate all the regular seq from string and colored them with 1 then i reversed remaining and colored them with 2, if inally the stack is not empty i print -1; then did above process again but this time i reversed first then printed min of above 2 processes

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

D can u tell what's wrong with my soln first i eliminate all the regular seq from string and colored them with 1 then i reversed remaining and colored them with 2, if finally the stack is not empty i print -1; then did above process again but this time i reversed first then printed min of above 2 processes

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

Seeing even experts getting WA for first time in B is such a relief..

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

just because slow server during contest time, I could not submit Prb D.After finishing the contest, the solution of D got accepted. It's very disappointing.

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

just because slow server,i could not submit prb D. after finishing the contest the D got accepted.it's really disappointing. :(

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

unrate it please.

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

Problem B is bad :( Promblem D is easy but I made many stupid mistakes... bad experience.

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

make it unrated!

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

"How many greedy questions have you prepared for this contest?" Problemsetters: Yes

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

This was not a good contest for div2. All problems were very easy compared to their expected hardness.

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

Stringforces XD...

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

Can anyone please explain why my solution is incorrect?

207239600

https://codeforces.com/contest/1837/submission/207239600

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

    >>><>>><>>><

    Your approach: [0 1 2 3 2 3 4 5 4 5 6 7 6] best answer: [0 1 2 3 0 1 2 3 0 1 2 3 0]

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

      Ok Thank you.

      i had two implementations on paper. But used the wrong one.

      when I looked at other's submissions, I realized that I could have used the other one (comparing max length of substrings of < and >). :D

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

Was this the easiest div 2D ever in terms of problem rating and solve count?

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

queue is so long!

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

maybe change the problemsetters for some time

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

Can anyone give a counterexample where my code gives a wrong answer?

207246737

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

What is this: not accepted / accepted
Only difference that the first one may only print out 2s instead of ones, but there is nowhere specified that colors must start with 1...

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

Wow, I am little surprised to see the number of submissions of B. Was the solution leaked somewhere ?

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

Hi this is the first time I join in a competition. But I only resolve the first three problems (A, B, and C). Will I get a rating score? Because I saw that my score is still 0 in my profile.

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

Я сегодня впервые участвовал в контесте и с интересом изучаю чужие взломы.

При этом мне показалось, что в некоторых случаях отдельные участники соревнования кое-где у нас порой специально публикуют решения с изъяном от имени клонов и потом их с гордостью взламывают.

Например, четыре успешных взлома задачи А: https://codeforces.com/contest/1837/hacks?verdictName=CHALLENGE_SUCCESSFUL&chosenProblemIndex=A — удивляют схожестью идеи и явным сходством в никах автора решения и взломщика. Или мне только кажется?

Возможно, есть какой-то принятый способ сообщать о подобных хитростях?

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

    хм, единственный "взлом" задачи В точно такой же:

    int main(){
        ios_base::sync_with_stdio(false);
        cin.tie(0);
        cout.tie(0);
        long long t = 1;
         cin>>t;
         if (t == 43) cout << "Hack me";
         else{
        while(t--){
            solve();
        }
         }
    }
    

    https://codeforces.com/contest/1837/hacks/911355

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

    А смысл? в таких раундах не дают доп. очки за взломы. А в раундах в которых дают очки за взломы, все разбиты по комнатам.

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

      да я тоже не знаю, в чём смысл заводить по нескольку аккаунтов или взламывать свои решения))

      Про очки мне вообще пока не особо понятно. Ну, кроме того что если лучше решать, то и результат будет лучше)

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

very high time limit for F

»
10 месяцев назад, # |
Rev. 2   Проголосовать: нравится +55 Проголосовать: не нравится
Standings big picture
Problem calculated difficulties
»
10 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

just me realising that speedforces and hackforces are a thing.:D

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

gordan ramsay after giving todays contest.

"My gran could do better!"

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

F is the most messed up problem I've ever seen. I can't believe it's that easy yet I can't solve :(

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

In problem B, if I start with the number X initially, if I encounter '<' I increment X else decrement X . Here is the code for it

vi ans;
ans.pb(5);
ll val = 5;

f(i, 0, n)
{
    if (s[i] == '>') {
        val--;
        ans.pb(val);

    }
    else {
        val++;
        ans.pb(val);
    }
}

deb(ans);

set<ll>st(all(ans));
cout << st.size() << endl;

}

Why is this approach wrong?

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

    If the sequence is ">><>>" then

    Your answer: $$$[5, 4, 3, 4, 3, 2]$$$

    Optimal answer: $$$[5, 4, 3, 5, 4, 3]$$$

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

anyone pls explain how to solve problem F

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

Solved 4 problems, couldn't crack problem E. But still felt accomplished with my performance, because it is first time when I solved 4 problems in an Educational Codeforces Round. Thanks to the problem setters who came up with these tricky problems.

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

someone pls explain how to solve problem F

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

this contest should be unrated because of the problem B.

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

My approach for Problem F:

Let us say we already have the k elements which are picked out from the original array, we can create a prefix and a suffix sum array and then iterate over the two picking the minimum of max(prefix[i], suffix[i]).

So now all we have to do is to find the k elements, we can find the k smallest elements in the original array and then take the maximum of that array, then check if we can/have to pick more than one occurrences of the max element from the original element, if yes we somehow have to find which occurrences of the max element do we have to pick in order to reach the minimum later on when we calculate the answer, I understand that the position of the max element matters but I cannot figure out how to optimize it in such a way so that it leads to the minimum ans.

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

Auto comment: topic has been updated by awoo (previous revision, new revision, compare).

»
10 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Help me someone on my post please. I can't understand this....

Here is the help post link:

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

good luck everybody!!!

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

I don't care how much you all hate this round. I'm gonna upvote. I turned blue.

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

Trash round.

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

My rating was updated to expert few days ago and today it is showing back to specialist, it has reduced by some points in this contest. Have anyone else faced this?