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

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

Neapolis University Pafos

Привет, Codeforces!

Благодаря поддержке Neapolis University Pafos, продолжается серия образовательных раундов. Университет предлагает получение степени бакалавра в области компьютерных наук и искусственного интеллекта со стипендиями JetBrains. Получите передовые навыки в области искусственного интеллекта и машинного обучения, которые подготовят вас к востребованным техническим карьерам. Любопытно? Присоединяйтесь к прямой трансляции во вторник, 29 октября в 17:00 UTC, чтобы узнать о программе CSAI, ее учебном плане, структуре курсов, стипендиях, стажировках для студентов и практическом подходе к обучению.

Хотите получить больше опыта в программировании и математических соревнованиях?
JetBrains Youth Challenge возвращается в ноябре 2024 года!

Кто может участвовать?
Возраст 13–18 лет.
Все, кто в настоящее время обучается в средней школе.
Зарегистрируйтесь сейчас.

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

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

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

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

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

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

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

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

qp

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

As a participant, I hope everyone participates and outperforms themselves in this contest.

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

I got a question, the penalty of time i.e. 10 minutes is the format of div. 3 and it is in this contest which is div. 2 so will the hacks have -ve points on unsuccessful attempts?

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

glhf

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

If I get minus again in this contest,I will leave CP.

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

I haven't lately been able to see any of the other users' submissions. Everything I see is "N/A" for source code, even for problems I have solved. Any solution to this very annoying issue? Thanks!

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

Could anyone tell me what means CP?

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

Today is my debut contest with Rainboy strategy , gonna start from $$$D$$$

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

As a contestant, I wish to test the problems live

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

Doing contest, problem B feels weird AF so imma skip it. Please correct me if it's skill issue.

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

$$$A$$$ is hard ._.

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

What the hell is this Problem B?

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

took 2 minutes for A and 2 hours for B

hardest B i've ever seen fr

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

    Actually I found A harder than B.

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

      I feel like you either observe the solution instantly for A or you don't at all.

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

        i literally kept testing everything I could think of on A and somehow it passed

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

          Well, you just had to fix any two points of the two lines at the corners of the (x * y) rectangle, then vary the other two on x and y axes. I got TLE tho 288664487

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

            5e3 * 1e3 * 1e3 = 5e9 , obviously TLE , you should always aim for <1e9 (unless the time limit is huge).

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

            you did some overthinking, if y>k and x>k you can just make an "L" on the grid, and if k>x or k>y you make an X on the grid xd

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

              I had that idea but idk why i messed up. This costed me the whole round, because i gave up on A.

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

    Ahh, so it's not just me? I literally have NO idea how people managed to come up with B's solution in such less time :(

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

      I guess since n was low enough for n^2, for odd n we can just brute force as we need to insert one extra number anywhere in the given array. Obviously, only at max 2*n possible values as we want new number to be closest to each a[i].

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

      B is a standard problem, and it took me nothing to figure out the solution.

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

how to solve E?

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

    How to solve D? Is it a Segment Tree?

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

      It's just some prefix sum stuffs

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

      prefsums + binary search. you can check my sol https://codeforces.me/contest/2026/submission/288582700

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

        damn that's a lot of prefix sums

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

          i gave up after trying too much prefix

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

            I used $$$4$$$ different prefixes in total ._.

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

              Yea I just upsolved it and this problem was a pain. It took me quite a bit to implement it and iron out all the bugs...

              Also not very "educational". It doesn't really teach you to think differently, just "implement harder".

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

      (assuming 1-based indexing everywhere) consider the b array as divided into blocks as this: (n size block) (n — 1 size block) (n — 2 size block)..... now consider one block which has starting element of pair as i. what is the sum of this block? s(i, i) + s(i, i + 1) + s(i, i + 2) + ... s(i, n) where s(l, r) is sum of a from l to r. you will see that in this expression, a[i] is added n + 1 — i times. so calculate suffix array on a[i] by this rule (a[i] * (n + 1 — i))

      now if i want sum of k blocks, i need sum of block 1, sum of block 2, ... sum of block k i.e. suff[1] + suff[2] + .... suff[k] so create a prefix array on the suffix array created before.

      now consider this problem: we want to find sum 1 to x, in array b:

      first find number of blocks that are completely covered say k — 1 (use binary search) add pref[k — 1] then we are at block k, now if this block has l as left point of the pairs. we want to find (l, l) + (l, l + 1) +.... (l, l1) (l1 depends on where x lies in this block. now for this we can add suff[l] — suff[l1 + 1] directly. but note : this followed rule (a[i] * (n + 1 — i), but now a[i] has not been added (n + 1 — i) times. you will see that now a[i] has been added (n + 1 — i) — (n — l1) times. so you need to subtract s(l, l1) * (n — l1). again have a prefix array on original a for this say this answer we calculated for sum of b from 1 to x, is given by f(x), then given query is answered by f(r) — f(l-1).

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

    I saw lots of max flow solutions.

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

    answer is n — max pair matching in the graph, where left side vertices are 1,2...n and right side 0,1,2...59 ,edges i <-> j where a[i]'s j-th bit is set.

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

B?!!!! Why is n < 2000? Is it really n^2 for odd n? How to solve B?

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

    Yepp just brute force for every index For every index I push a[I] +1 just after a[I] and then check the minimum among all maximum You can see my code

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

      Thanks, can you give a case where the picking the either last or first doesn't work for odd n? I couldn't come up with such a case

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

    yeah, for even N you just sort and pair up, and for odd you test all possible Ai that you could pair up with the extra cell

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

    You can do in O(n + log2(max(ai)) using binary search. You can check this comment.

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

    I did it with o(n^2). You can actually remove each element and cut the array at that position to make the array two even array and solve it.

    I think this intuition is less complex to solve the problem. By also accepting o(n^2) authors try to make the problem simpler.

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

    I did it in O(N). You can check out my solution: 288539510

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

please don't write problems like B again

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

What is the solution for B?

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

    You can binary search for each k from low = 0 and high. = (arr[n-1] — arr[0])

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

      why return cnt >= n/2;

      how you got this idea?

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

        I will try to explain it here, let me know if you get it or not.

        cnt is the count of pairs, number of pairs should be n/2, as 2 elements make up a pair. Also imp thing is we only have to check diff between conseq elements as least diff of any j with current i will be when j = i + 1 as array is increasing. eg: if n = 6. there should be 3 pairs. if n = 7, there should be 3 pairs and the remaining 1 we can match by adding our available "atmost one addition case".

        n is even : Lets say a = {1, 5, 8, 10, 13, 14} and k = 3 here 1 and 14 would not get a pair (as (5-1) = 4 > k & 14 doesn't have a pair to match with), whereas (5, 8) and (10, 13) can make up pair. So cnt = 2. As we can only add atmost 1 number, we can't make pair for both 1 and 14. So k = 3 is not feasible. if cnt was 3 (= n/2) then that means all the numbers have pairs. So its feasible.

        n is odd : Lets say a = {1, 5, 8, 10, 13} and k = 3 here 1 would not get a pair (as 5-1 = 4 > k), whereas (5, 8) and (10, 13) can make up pair. So cnt = 2 (= n/2). As we can only add atmost 1 number, we can make a pair for 1 by adding 0. So k = 3 is feasible.

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

    observe if we have n==even , then we cant take the extra element as that can't be compensated by any other element while making pairs so just find the max difference b/w consecutive elements, if n==odd , we have the choice to leave one element and find an extra new one for it, we can do this for each element and store the max diff to the right of it and to the max diff b/w consecutive elements to the left of it and take the max of both the overall answer for this case would be minimum of all such cases

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

c's gonna make me cry when i see the case im failing on

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

please don't write problems like B again

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

    Actually, I think it's a very good and tricky problem. No one on my friends list got it on the first try.

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

      after the first WA2, i waste about 50mins. at WA5 bcos i were minimizing the ans with 1e15 :(

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

    What? It's just a standard binary search problem.

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

after the contest, i felt like it is somehow harder than the last div1+2

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

Many low-rated people solved D in the last 15 minutes, I don't know if it's my skill issue but I don't think it is an easy problem. So please skip those who cheated.

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

I attempted only the first two problems and found both of them weird, or maybe I am making some blunders; I don't know.

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

couldn't solve any thing I'm mad but at least the problems are not guessing problem

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

I mean I like prefix sums, but prefix sums of prefix sums of prefix sums is too much man.

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

AC D at 1:59 :)

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

Thank you very much for contest.

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

I spent close to 38 minutes for problem A and got one wrong on B just in hurry of choices Struggle is real kn geometry problems

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

today D feels like a buffed version of 2009F - Firefly's Queries.

Which I regret haven't upsolve the problem yet...

But idk maybe I'd stuck on this anyway.

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

E: Build a bipartite graph with n vertexs on the left and 60 vertexs on the right. For each 1<=i<=n and 0<=j<60, we add an edge if a[i] has j-th bit set on. For any subset of left nodes, the score is (number of chosen left vertexs )-(number of right vertexs with edge connected to chosen left vertexs ) = (number of chosen left vertexs )+(number of right vertexs without connection to chosen left vertexs )-60, then the answer is (Size of maximum independent set)-60. By the Konig theorem: In any bipartite graph, the size of maximum matching is same as minimum vertex corver, and (size of minimum vertex corver)+(size of maximum independent set)=n+60, we can calculate answer by any maximum matching algorithm.

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

If i've submitted twice of one problem which one will be counted? If first one is hacked then second one counted?

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

There is nothing educational about B.

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

B reminds me with this problem

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

im really confused why my binary search submission failed on B, and then my brute force one passed. obviously n is 2000, so i kinda knew it was brute force, but i didnt come up with any counter test case for my binary search one, can someone give a counter example?

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

In problem E, what does "set bit" mean ?

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

https://codeforces.me/contest/2026/submission/288585044

can someone help why this is wrong?

Greedy solution. Logic is that I store all the i where s[i] == 1 in a greater int set. ans = (n*(n+1))/2

I iterate over them{ count = 0; I have 2 variables l and r, I iterate over l from n->0. if I find s[l] == 0, then count++; if I find s[l] == 1 then I check on count, if it is 0 then I move more left.

When my 0s are exhausted, I move to r and only check the 1s from 1->n, if there is a 1 corresponding the I make count++, if there isnt then I break,

if there is a count then I reduce the answer by the indes of the one in the starting loop}

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

    The algorithm I used:

    1. Greedily scan from right to left
    2. If s[i] = 1, pair it with rightmost '0' (pos<i)
    3. Else pair it with the leftmost '1'

    In 2,3 just store the i, in these cases only, you will be saving money.

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

    If s[i] = 0, the value $$$i + 1$$$ would be added to the cost no-matter what.

    Go from right to left. The idea is to greedily exhaust the rightmost $$$1's$$$ with the first encountered $$$0's$$$ from right to left. If we exhaust in pairs, we will be able to remove as many $$$1's$$$ as possible.

    Use a std::deque to store the cost generated by $$$1's$$$. Larger values are stored in the front.

    if s[i] == 0,
    if !dq.empty() do pop.front(); if it is empty, we can pair it with the already exhausted $$$1's$$$.
    do cost += i + 1

    if s[i] == 1 do dq.push_back(i + 1). Finally when the dq contains $$$1's$$$, we can greedily exhaust the largest(front) and smallest(back) values.

    https://codeforces.me/contest/2026/submission/288593783

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

    Consider 1100011111

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

Does anyone know what's wrong with my solution for B at 288576824? It seems to me like it should work, but sadly it fails on test 2.

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

    Check my braindead solution (that divide to 2 cases of N like you): 288562462
    (Why braindead? It just bruteforce every possible choice of "removal" in case N is odd and find the "best" choice (variable "minn")).
    (Case N is even, my solution is the same as yours)

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

PD I know prefix sum. But just too heavy implemention... run out of time. :(

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

Do I understand right that problem F is just:

Code persistent queue on 6 stacks, in stacks we store knapsacks, so when answering the query we can just take left and right knapsacks and bruteforce the sum on each edge

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

Is large number in cpp necessary to solve problem D?

Is there a great large number template in cpp? emmmmm

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

how to solve C?

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

    I transverse the array from back to front and use deque to be able to pop front efficiently. The greedy part is to match higher indexed '1' with any first '0' found and pop it. Then, if there are still '1's remaining, just pick the lowest half.

  • »
    »
    4 недели назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится
    • think of a number 0 can carry the most expensive 1 (right most one)
    • after eliminate all the 0, the array is left with all the 1, then again, a left most 1 can carry the right most one. (*)
    • the answer is sum of all 0 index and all 1 index left in (*)

    main take away is just greedy and 2 pointers

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

      I was knowing it was greedy and came up with this idea but couldn't implement again. Fck my implementation skills fk it

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

        Chill mate, look at me hard stuck in pupils for 4 months already and still die trying. You peaked in specialist is a good stuff, keep going.

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

          ahh mate I peaked there I am trying really hard right now solving 1300-1500 range alot hoping to improve soon

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

wrong A why cant long long ? https://codeforces.me/contest/2026/submission/288534007

0 0 68724335200 68724335200 0 68724335200 68724335200 0 0 0 68724335200 68724335200 0 68724335200 68724335200 0 0 0 68724335200 68724335200 0 68724335200 68724335200 0 0 0 68724335200 68724335200 0 68724335200 68724335200 0

wrong output format Expected int32, but "68724335200" found (test case 1)

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

Can anyone try to hack this submission? I think greedy cannot pass this problem.

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

In these contests, is wrong answer on Test 1, considered as a penalty ?

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

Either I am getting dumb day after day, or A,B,C are actually getting difficult contest after contest.

Yesterday was Div (1 + 2) contest.

Today it is simply Div-2 contest.

I felt like today's ABC were more difficult, than Yesterday's ABC.

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

    Nope

    Today I solved ABC, but yesterday C was giving me an insomnia...

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

    I also found yesterday's B much easier than today's A or B. Both today's and yesterday's A were a bit more complicated written than usual. Today's C was much easier (at least for me) than yesterday's C, sadly I ran out of time. :D

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

Worst contest is codeforces history.

Why is 1 blunder in 1 single contest worth a -150 delta?

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

A had a really nice hint for the idea that AB, CD are diagonals of a square with side min(x,y) i.e. K<=1414 , hinting the appearance of root of 2

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

Problem E seems familiar

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

Problem C seemed quite interesting to me, the idea felt so satisfying.

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

Could anyone please explain how to do B? I used binary search, but it didn't work.

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

    just brute force the point which will be paired with a point outside the given set.

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

    you could use binary search or brute force (idk the binary search way)

    but in the bruteforce way, if n is even, you just pair up all cells, and if its odd, you test removing every cell and pairing up the others to see which way is cheaper

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

      Thank you. Got AC.

      But I'm still wondering why my BS solution didn't work.

      Anyways, thanks.

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

        np!

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

        Cause you have added random things in your code which is greedy when you saw the sample test cases

        if(n%2!=0 && !x && (((num[i]-num[i-1]+1)/2<=mid) || i==1))

        i) why i==1 is getting a free choice

        ii) why n%2!=0? it makes no sense. If you approach is because you are already going to use one point to get even points then you are correct but making such mess in the same line? Cause later you are doing i==1 which means you are skipping a element at position = 0. Which again makes no sense cause you can pair any of the i so why position i=0 is getting a priority?

        iii) (num[i]-num[i-1]+1)/2 <= mid makes no sense because the new point you will be placing will be not at the middle it will be anywhere ITS FREE WILL. By placing it at the middle of num[i] and num[i-1] gives no contribution cause you are meant to stick the power up for the first element that violates the <=mid thing with its next right neighbor (according to greedy approach).

        I hope you understand that you have just written many wrong things and messy in a single line.

        Dont be sad or angry about it. Understand it calmly and keep grinding.

        If you need my bs approach (a clean code) https://codeforces.me/contest/2026/submission/288520406

        Thank You!

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

          No I got it. I should have read the question carefully to fully understand it. Couldn’t give my best performance today.

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

            Its okay buddy. Sometimes we perform good and sometimes we perform bad.

            Cheers that you are consistent with giving contests! Keep grinding 😇

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

    It's optimal to paint neighbors.

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

      why this case 2 and not 1 please answer


      2 1 3

      we can paint cell number 2 what is wrong with that ?

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

        You have to choose two cells at a time. In this test case the no. of cells is even. So you can't choose any cell outside this given set.

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

Miss chance to become master AGAIN by declaring $$$a_i$$$ of Problem E as int, not long long.

Note: shifting more than bit width is an undefined behavior, so I get WA1, not WA2 or WA3, which is confusing to me.

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

D is very reminiscent of Mosaic from this year's IOI.

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

Can anyone please explain why my solution fails:

Method: For even n, directly calculate the max distance between all pairs (a[0],a[1]), (a[2], a[3]).....

For odd n, calculate min(max(((a[0],a[1]), (a[2], a[3]).....), ((a[1],a[2]),(a[3],a[4]).....))).

Submission

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

The worst contest in codeforces history

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

Spent a lot of time thinking about E after coming up with the obvious Maximum Matching algorithm, not able to believe its actually the intended solution.

While not having a template for it cost me today's E, I am really surprised Maximum Matching was allowed to appear in E, especially when the idea that each bit should have atleast one unique entry is quite simple.

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

    I agree that it is too much for E. But it seems to me that we have no right to complain, since this is Educ and in fact it is intended for this: you know an algorithm — 3 minutes will be enough for you, if you don't know — you are cooked for the next two hours.

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

"Euclidean or Manhattan" missing from "A"s statement.

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

Are there any ways to solve problem E with dp? I tried to solve it with dp but get WA.

Let dp[i][j] represent the value of mask such that the number of 1-bits in mask is minimized when constructing a subsequence of length j with i as the last element of the sequence.

I think we can combine with some greedy tactics, such as save more than one mask for each dp[i][j] at a time.

Sorry for my bad English.

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

    No it's not possible because even a mask where the bits might not be minimized might be better for bigger j and many other stuff

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

The worst contest in codeforces history

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

Using random to solve E: (This is gonna WA on test 2) (OMG, it's running on test 10!) (OMG, it's running on test 20!) (OMG! It ACCEPTED!!!) (I'm going to submit a lot of them to ensure I can pass main test) (passed 6/27) (ALL 6 AC submissions are hacked, rank 103->511 QAQ)

So is there a way to hack these submissions at a high possibility? Or it was just because I was to silly when randomizing? Can these submissions be hacked? 288611596 288611196

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

    Okay, I've come up with a hack and hacked myself:(

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

for problem B this case

2
1 3

why the answer is 2 and not 1

if k=1 then we paint 1 and 2 and then we can easily paint 2 and 3 ??????????? why I'm reading the statement wrong every time ????

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

    You can only paint WHITE cells. So, after you paint 1 and 2, cell 2 will be black, so you can't use to paint 2 and 3 since you can only paint white cells.

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

    i spent a few seconds thinking the same thing during the contest lol

    notice that the problem statement mentions in bold letters that you can only paint white boxes. once you've done the operation on 1 and 2, 2 becomes black so you can't operate on the second box anymore.

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

Seems that problem F only have operation 3 in the sample. See here

code copied from jiangly's code and add one assertion on operation 3. Only have 96 tests during the contest while the verdict is RE on 97.

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

    My bad :( We only discovered that during the contest. Somehow all incorrect solutions we had were incorrect even on that set of data and all correct were still correct after the generators got fixed. Luckily, not a lot of people got affected by the incomplete tests.

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

      I now got affected due to some runtime error that only fires if there's actually operations of this type in the input.

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

.

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

could someone provide counter example for this submission , im getting WA on test 5, and the solution seems kinda silly but it runs in O(60*n^2) in worst case scenario, and it seems correct to me. basically what i do is for every element i, lets call it valid, if for every bit that is set in in a[i], it has atleast 1 valid neighbour. first we assume all indices are valid, and then we check if there is an element that isn't and if there is such an element we delete it, and also since it may have made some other indices valid, but now doesnt anymore, we have to repeat this until no changes occur. this runs in O(60*n^2) in the worst case where we delete 1 element per iteration, and every element will be deleted, so its fast enough. but its getting WA on test 5 and i cant seem to find a simple counterexample.

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

i went from getting a +65 in yesterday's contest to literally not being able to solve a single problem today. cf contests are SUCH a rollercoaster i swear :\

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

Sorry Demon_Master

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

Educational contest educated me that I know nothing. Nothing: No, you don't know me. Me: He knows me. He: Who, are you? Who: No, I am not "?". Not: No, your not Not. No: I know.

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

C was easier than B, also A was weird. not a balanced contest tbh,

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

The pretest of B is quite weak.I solved 5 problems, but I hacked my own B successfully.

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

What the hell was that B question ?? After several incorrect submissions, I came to a conclusion that its a BS + DP problem.

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

    For even numbers, it is only possible to paint them pairwise from left to right. For odd numbers, you can delete one element and solve it as even numbers.

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

    you can bruteforce it: for n even, just pair up all values, for n odd, fix every value and pair the others and see which way you get the minimum cost

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

I can't figure out why this code got WA on D. How mysterious.

#include <bits/stdc++.h>
#define MAXN 300005
using namespace std;
typedef long long llong;
llong n,q,L,R;
llong a[MAXN],presum[MAXN],sumsum[MAXN],press[MAXN],ppsum[MAXN];
llong find_pos(llong p) {
	llong l=1,r=n+1;
	while(r!=l+1) {
		llong mid=(l+r)/2;
		if (n*(n+1)/2-(mid-1)*mid/2>=p) l=mid;
		else r=mid;
	}
	return l;
}
llong query(llong p) {
	if (p==0) return 0;
	llong len=find_pos(p),order=n-len+1;
	llong starting=n*(n+1)/2-len*(len+1)/2+1;
	llong minus=presum[order-1];
	llong ans=ppsum[p-starting+order]-ppsum[order-1]-minus*(p-starting+1)+press[order-1];
	return ans;
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n;
	for (llong i=1;i<=n;i++) {
		cin>>a[i];
		presum[i]=presum[i-1]+a[i];
		ppsum[i]=ppsum[i-1]+presum[i];
		sumsum[1]+=presum[i];
	}
	press[1]=sumsum[1];
	for (llong i=2;i<=n;i++) {
		sumsum[i]=sumsum[i-1]-(i-1)*(n-i+2);
		press[i]=press[i-1]+sumsum[i];
	}
	cin>>q;
	for (llong i=1;i<=q;i++) {
		cin>>L>>R;
		cout<<query(R)-query(L-1)<<'\n';
	}
	return 0;
}
»
3 недели назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Hard A. However, 3k people solve it in 5 mins. I DO think lots of cheaters in A. D is good. I need to practice more prefix sums, to find indexes faster.

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

can someone explain why this solution is not working for c ~~~~~

include

include

using namespace std;   int main() { int tc; cin >> tc; while (tc-- > 0) { int n; cin >> n; string str; cin >> str; int s = 0, e = str.length() — 1; long long ans = 0;

while (s <= e) {
        if (e - 1 >= s && str[e - 1] == '0') {
            int idx = e - 1;
            while (idx >= s && str[idx] == '0') {
                ans += (idx + 1);
                idx--;
            }
            e = idx;
        } else {
            ans += (s + 1);
            s++;
            e--;
        }
    }
    cout << ans << endl;
}
return 0;

} ~~~~~

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

please help me to find why this code is not working for c https://codeforces.me/contest/2026/problem/C

//this is code
#include <iostream>
#include <string>
using namespace std;
 
int main() {
    int tc;
    cin >> tc;
    while (tc-- > 0) {
        int n;
        cin >> n;
        string str;
        cin >> str;
        int s = 0, e = str.length() &mdash; 1;
        long long ans = 0;
        
        while (s <= e) {
            if (e - 1 >= s && str[e - 1] == '0') {
                int idx = e - 1;
                while (idx >= s && str[idx] == '0') {
                    ans += (idx + 1);
                    idx--;
                }
                e = idx;
            } else {
                ans += (s + 1);
                s++;
                e--;
            }
        }
        cout << ans << endl;
    }
    return 0;
}
»
3 недели назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Awesome contest!I am rank 3 and will become IM!

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

Why unrated?

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

MinusForces

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

problem D makes me feel like I'm not participating in CP …… All of the difficulty is to write the code. Too little about algorithm and too much about coding. Well, maybe it can help us improve our coding ability ……

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

    problem E is also not good. If you know Maximum Weight Closed Subgraph you can solve it quickly, but if you don't know that you are hardly solve it.

    I think Div .2 D and E should have good ideas without too hard code or too hard algorithm.

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

      Isnt the point of Educational Rounds to teach these topics to a wider range of participants?

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

      By your logic, Problem F is also formulaic for those who knows tree division — it is just to decompose the knapsack dp onto a tree. However, in my opinion an edu round is to be formulaic as it aims to educate.

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

        In my opinion, Edu round is more important to teach participants how to solve problem rather than a specific algorithm. In most contests like ICPC, only learned algorithms is not enough, it's more important to know when to use it and how to use it.

        It is acceptable to set problems like E or F. But I think problems which have more thinking instead of hard hard code or hard algorithm are better in a 2 hour edu round.

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

Where is the EDITORIAL of problem F?

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

sbsbsbsbsbsbsb

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

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

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

I enjoyed this contest. It was really good! I don't understand why this post is downvoted.

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

Why can't I earn points in the last two games?

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

For problem D

The approach to this problem starts by precomputing powers of 2 up to the maximum needed range. This allows us to quickly apply these powers to elements without recalculating them each time, making the solution more efficient. For each element in the array, we break it down into two parts: an odd part and the largest power of 2 it can be divided by. This decomposition is useful because it lets us keep track of how much "doubling power" each element has.

To efficiently combine elements and maximize the sum, we use a stack. For each new element in the prefix, we check if we can combine it with elements already in the stack to get the highest possible sum. We do this by removing elements from the stack that have lower effective doubling power, adding their contribution to the sum, and redistributing powers to make the current element as strong as possible. After processing each element, we push it onto the stack, updating the sum for the current prefix.

Finally, we output the maximum sum for each prefix, taking results modulo to handle large numbers. This approach naturally follows from the problem’s constraints, as maximizing sums by doubling requires managing powers of 2 and combining elements optimally. As a result, it’s not unusual for solutions to resemble each other since the problem’s setup leads directly to this method.

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

sorry everyone i cheated on this round on problem -B ,may god forgive me !!!!!1