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

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

Neapolis University Pafos

Привет, Codeforces!

Мы рады объявить о новом долгосрочном партнерстве между Codeforces и Neapolis University Pafos. Теперь образовательные раунды будут проходить при поддержке Neapolis University Pafos. Следите за новостями и совсем скоро вы узнаете все подробности.

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

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

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

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

Спасибо тестерам раунда shnirelman и Optoed за ценные советы и предложения! Отдельное спасибо Vladosiya за помощь с раундом.

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

UPD: К сожалению, некоторые посылки по задаче E во время соревнования были протестированы неправильно. Это затронуло только 18 участников раунда, поэтому он остаётся рейтинговым. Участники в рейтинге, которых затронуло перетестирование задачи, могут запросить нерейтинговое участие (в оповещении, пришедшем им во время соревнования, есть инструкции, как это сделать). Если во время соревнования вы не получали в интерфейсе раунда оповещений по поводу этого — проблема с тестированием вас не затронула.

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

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

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

excited for A, B, C problems

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

    you practice so hard and participate almost every contest in codeforces!

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

      still pupil lol

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

        just keep coding and you will make it!

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

        You solve 600+ problem but most of there are 800 difficulty. solve more difficulty problem and also do virtual contest. It will help to improve your problem solving ability rapidly.

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

          how to keep up and make time for everything disappoints a bit. But still its better than solving problems topic wise... I guess every new things we see here in the contests might be more than enough to get the general overview in enhancing the ability....

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

Such a short and clear announcement I hope problems statements be like this too!

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

Mathforces lessgo

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

Excited af

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

Excited as f

»
8 месяцев назад, # |
  Проголосовать: нравится +154 Проголосовать: не нравится
R.I.P
»
8 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Interested in solving these problems :D

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

just an fyi that codeforces no longer supports c++20 (true at the time of writing this comment), so hopefully no unpleasant surprises during the contest!

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

    It's temporary and there is a very good reason for it (https://codeforces.me/blog/entry/126654).

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

      i am already aware of that thread. It is true that there is something subtle going on (probably related to the Windows heap). What I take issue is that we're just banning c++20.

      Whatever the problem may be, it is only affecting a small minority of all submissions. Straight up removing the compilers just creates larger inconveniences. We can make this issue known and those who are concerned may choose to use different compilers for c++.

      Back when Java's Arrays.sort was quadratic time, we didn't just ban the language. We're not banning pypy for being slower python with Fraction either.

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

        If submitting in C++20 is causing performance degradatinos for other users' submissions, that's a separate discussion. Then I agree removing C++20 would make sense. However, such things should at least be properly announced

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

          This issue is different: - As far as I know, the scope of the issue is not well understood. The issue is with variable length allocation, which appears in many submissions. I don't think it's fair to say that it affects only a small minority of submissions--only that a small minority of submissions have been shown to be problematic.

          • The inconvenience created by removing a compiler is substantially less than the inconvenience created by removing a language.

          • We can expect contestants to be familiar with the language itself, so it's fine to penalize contestants who use slow APIs from the standard library. It's generally not expected for contestants to be familiar with the details of a compiler, and less so with the operating system internals (which is most probably where the error lies).

          Unless this changes, and the build system is made completely public, it's actually the fault of the Codeforces platform for building on a system with this type of unexpected slowdown. So the correct thing to do is remove the compiler until the issue is resolved.

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

            I agree with most of what you said. However, I don't think the logical conclusion is to remove the compiler (which happens to remove the language c++20 entirely). I agree that it is the fault of the Codeforces platform, but they could just keep c++20 and admit there is a fault in the system. Instead, they decide to hide it by removing the language. I see no issue with a caveat along the lines of "we tried, but use at your own risk because we run code on windows".

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

Hope to get my rating back

Good luck for everyone!

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

Oh yes!!! Another Div.2 contest!

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

Binary search forces ?

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

Will there be an interactive problem?

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

As !tester predicting yet another mathforce

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

Just curious, this support change will only affect the policy-related/financial/sponsoring aspect of the round series, not the setters, won't it?

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

lets go =D

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

I fear nothing but bledest B

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

Hi

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

Hi

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

in what level these problems will be ?

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

hope I can make this

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

I hope E not too easy like last 2 Edu rounds good luck everybody

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

Who tested?

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

New sponsor, hoping for better rounds but i can't expect anything from edu ...

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

Educationals are too unpredictable. Scared to participate but gotta try :(

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

being mentally prepared before the contest

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

still have hope

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

in edu rounds you can submit as much right submissions as you want right? without any penalty?

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

D seems to be easier this time

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

The problems in this contest are really bad

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

anyone can explain to me the test in problem C ? Now, i still can't understand it!

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

    So, in first turn we move to (1,2) and than we have to move like an arrow on this cell, so this turn we end in cell (1,3). In second turn we move to (2,3) and again we have to move like an arrow, so from (2,3) we move to (2,4).

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

Problems were too hard, I need to get good. :(

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

can any body tell me what's wrong with my dp solution for problem C : submission

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

G is a cute problem, thanks!

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

D felt better than C. C was a bit annoying

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

Definitely sleep is the most important thing. My anxiety went under control and I broke two records today. I ran 2km in 10 min for the first time and solved A-E just a little more than an hour.

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

is there a z-function solution to D?

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

Can someone please explain D to me?

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

    If any index $$$i$$$ is part of the latter half of a tandem repeat of length $$$2j$$$, then $$$a_i = a_{i - j}$$$ (considering '?' as equal to anything) must hold, lets say $$$good_{i, j} = 1$$$ if this is satisfied for a given $$$(i, j)$$$ and $$$0$$$ otherwise. We can clearly calculate these values of $$$good_{i, j}$$$ in $$$O(n^2)$$$ time.

    Then any index $$$i$$$ to be the start of the second half of a tandem repeat of length $$$2j$$$, $$$good_{k, j} = 1$$$ must hold for all $$$i \leq k \leq i + j - 1$$$. This can be checked in $$$O(1)$$$ by storing prefix sums of $$$good_{i, j}$$$ or in a total of $$$O(n)$$$ over all $$$i$$$ by just iterating in decreasing order of $$$i$$$ and keeping track of the most recent pos $$$p$$$ where $$$good_{p, j} = 0$$$.

    So for each $$$1 \leq j \leq \lfloor \frac{n}{2} \rfloor$$$, we just iterate on $$$i$$$ in decreasing order and check all possible tandem repeats in $$$O(n^2)$$$ time.

    Code — 251486634 ($$$i$$$ and $$$j$$$ are swapped compared to my notation here)

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

    I did $$$n^2$$$ DP, where $$$dp[i][j]$$$ is the maximum length of repeat string we can get if the first half of the string starts from $$$i$$$ and the second half of the string starts from $$$j$$$

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

    I think tourist's solution for problem D is simple and easy to understand. He did it in under a frickin minute.

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

    Linear search on answer.

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

how to solve b ? I iterated over numbers and kept an array of pairs which holds the options available for the previous number which are leave it as it is or do the operation on it and based on this info I can decide for the current number what I can do for it but this was wrong

  • »
    »
    8 месяцев назад, # ^ |
    Rev. 4   Проголосовать: нравится +7 Проголосовать: не нравится
    1. Always break the first number (except if its digits are in desc order), as its a no-brainer.
    2. Try if the next number in array can be broken and sorting order is maintained. If yes, keep going otherwise you can't break.
    3. At end check if new array is sorted or not.
»
8 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Is the formula for F OEIS-able?

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

C was very similar to "binary path" problem , which came in a recent contest

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

Why are constraints on E so low?

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

    Yeah, it's a bit strange, since we could solve it in O(n). At first I thought it is some kind of DP problem after seeing the constraints.

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

    Is the checker algorithm runs in $$$O(N^3)$$$? Lol I dunno

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

Is problem D a prefix sums problem? I have an approach that looks like it should work.

Simply check if the number of values that correspond with each other in some substring s' is |s'|/2.

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

My brute force solution for D got accepted. Please, can someone hack it, since I know it's not an intended solution

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

abc were easy but because i am slow and have skill issue i will lose rating xD

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

Applied BFS on Problem-C, Now I feel stupid after checking out other solutions

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

    Actually I think BFS or DFS is the most straightforward solution to it

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

      Ok so the thing is, I completely forgot that you have to keep a VISITED SET in BFS.
      That was the reason for TLE.
      Now with the visited set my sol. gets Accepted

      Just your average newbie mistakes :)

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

[submission:251541342]Please tell me why my C is wrong

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

    void solve() {

    ll n;
    cin >> n;
    string s1, s2;
    cin >> s1 >> s2;
    if (s2[n - 2] != '>') {
        cout << no << endl;
        return;
    }
    ll tem1 = -1;
    bool x = false;
    for (int i = 0; i < n; i += 2) {
        if (s1[i] == '<') {
            x=true;
            break;
        }
    }
    if (!x) {
        cout << yes << endl;
        return;
    }
    for (int i = 1; i < n; i += 2) {
        if (s1[i] == '>') {
            tem1 = i;
        }
        else {
            break;
        }
    }
    for (int i = tem1 + 1; i < n; i += 2) {
        if (s2[i] != '>') {
            cout << no << endl;
            return;
        }
    }
    cout << yes << endl;

    }

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

is string algorithm required in problem D

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

@awoo Are you all right? If you have trouble making problems, please don't throw garbage around.

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

    If you think the problems are really good, you can vote against me because it really saves time for all of us.

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

anyone solved C using DP?

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

    Yes me

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

    initialize dp[0][0] as 1. if there is a '>' you can go to the next coloumn from left or up or down.

    dp[0][0]=1;
        for(int i=0;i<n;i++){
            if(str[0][i]=='>'){
                dp[0][i+1] |= dp[1][i];
                if(i) dp[0][i+1] |= dp[0][i-1];
            }
            if(str[1][i]=='>'){
                dp[1][i+1] |= dp[0][i];
                if(i) dp[1][i+1] |= dp[1][i-1];
            }
        }
        if(dp[1][n-1])
            yes
        else
            no
    
    • »
      »
      »
      8 месяцев назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Can you explain a little bit elaborately? I still can't get it!

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

        Suppose you are at str[0][i] then you can go to str[0][i+2] if str[0][i+1]=='>' OR you can go to str[1][i+1] if str[1][i]=='>'. The same is applicable to str[1][i].

        This is the basic concept.

        And for the dp part -->

        Initially you are at str[0][0] position, which is true. Now while traversing both row at the same time if you encounter '>' then you will check the dp value of previous coloumn of the same row and the same coloumn of other row. If any of these holds true, then you can go to the next coloumn of the current row.

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

Problem C can be solved without graph algorithms. I see most of the users have not used my very easy approach. 251492497

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

G was a nice one)

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

Problem C can be solved using a very easy approach instead of graph algorithms or dynamic programming. 251492497

void solve() {
   int n; cin >> n;
   string s, p;
   cin >> s >> p;
   string x;
   for (int i = 0; i < n; i++) {
      if (i % 2 == 0) x.push_back(p[i]);
      else x.push_back(s[i]);
   }
   for (int i = 0; i < n - 1; i++) {
      if (x[i] == '<' and x[i + 1] == '<') {
         cout << "NO\n";
         return;
      }
   }
   cout << "YES\n";
}
  • »
    »
    8 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Can u explain the logic

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

      You can see that you only have control over cells in positions either like (0, 2k) or (1, 2k + 1). So, you need to consider situations where you can't move to the cell on the right.

      ...<...
      ..<....
      or
      ...<...
      ....<..

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

      Let * be the cell in which you make 1st type of move. (i.e., you move in any four direction) it will not matter either '>' or '<' is in the '*' place.

      Example string1:

      *>*>*>*<*<
      >*>*<*>*>*
      

      Output1: YES

      Example string2:

      *<*><
      >*<*<
      

      Output2: NO

      if you are in the place '*'. then, there must be at least one '>' to the "right or down" or "right or up" from the current cell. if in both places '<' is there. then we can never move further from that cell.

      So we checked for some '*' cells, from which we could never move further. if there are no such cells, we can always reach our destination.

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

    what's the logic behind that ?

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

I found that the problems, up until E, weren't particularly interesting, they were more of implementation. I'm unsure if my solution for E was what was expected, I believe the constraints could have been tougher, since we can prove that no clique size can be greater than K and that there is a construction in which K size clique is possible.

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

problem C was similar to recent contest's problem "binary path"

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

The data range of problem E is so humorous that I stuck on it for 30 mins.

So I didnt even have time for the last problem. Sad.

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

Problem A,B Video Editorial (Audio : Hindi) If you are a Beginner, then You can refer to this video for explanation of problem A and B. I hope it's gonna help you if you weren't able to solve A or B during the contest !

YOUTUBE Editorial Link --Click Here

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

I can't believe how +3000 people come up with solution on D on time, cp too competitive 🙄

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

    No ,I think there is a brute force type solution of O(n^2) that is working or as told by Pirate_King below the pretest cases were weak allowing O(n^3) fully brute forced solutions

    Now for O(n^2) solution :-

    SEE THE SOLUTION LINK BELOW YOU WILL UNDERSTAND EASILY

    here we are brute forcing or looping for half length of tandem repeat hence we will make loop from i=1 to i=n/2 then for each length i of tandem repeat we will check with another loop from j=0 to i+j<n whether that length tandem repeat is present in string or not

    By checking whether current_index and current_index+currlength of tandem repeat we are searching are equal or not if equal then we will take count of consecutive index which is satisfying this condition if this count becomes equal to currenttandemsearchlength then the current answer becomes equal to currenttandemsearchlength now will calculate this answer for every length iteration and at last will print the answer(which automatically stores max length)

    254855666

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

      Your approach is very nice (Never seen it before). Is that like a standard algorithm or based on something ? I was curious of how one could modify the 2nd inner loop had the question said that tandem repeat is even-lengthed string where 1st-half and 2nd-half are reverse of each other.

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

    Look at the hacks bro. The testcases were weak so $$$O(n^3)$$$ solutions passed. Solve count gonna drop significantly after system testing

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

If I hack someone's submission successfully,does this hacking test be added to final tests?

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

Did anyone else also find this observation in problem c (diagonals)

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

The meaning of passage C was too ambiguous.

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

    Yes was confused between that robot have to reach last block(2,n) after performing both the operations OR robot have to just touch the last block

    P.S. robot have to reach last block after performing both the actions is correct way for C

    Actions

    There is a robot that starts in a cell (1,1). Every second, the following two actions happen one after another:

    Firstly, the robot moves left, right, down or up (it can't try to go outside the grid, and can't skip a move); then it moves along the arrow that is placed in the current cell (the cell it ends up after its move). Your task is to determine whether the robot can reach the cell (2,n)

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

Is anybody aware of the reason 251440010 results in a compilation error?

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

    Interesting -- apparently this is caused by a bug in the compiler. I also could reproduce the error with custom tests. Meanwhile I could avoid the error by moving the definition of vis to global (and initialize them appropriately).

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

    By C++ standard you can't declare an array of variable length. The size of it must be constant expression (known during compilation). However, there are compiler extensions that allow them, but anyways compiler is not obligated to have them. It seems that this particular version doesn't. Or it doesn't support boolean arrays of variable length explicitly. In any case this can't be considered a bug.

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

      I tried resubmitting the same solution, replacing the array type from bool to int 251558731. Evidently, the type of the array does not seem to matter in this case. Later this contest I submitted 251491928, which also uses arrays of variable size, but doesn't get CE. Just curious what exactly causes the bug, because the compiler logs aren't very helpful

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

      AFAIK that is a GCC extension and is supposed to compile.

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

    It seems to me that it has to do with the ordering of the dimensions in terms of constants. Simply changing the definition from $$$vis[2][n]$$$ to $$$vis[n][2]$$$ resolved the issue

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

I get TLE for problem C although the complexity of my code is just 4 * n. I even get TLE on test 1 although it run very fast in my computer. Help me please. https://codeforces.me/contest/1948/submission/251550212

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

I get TLE for the problem C although the time complexity of my code is just 4 * n. I get TLE on test 1 but it runs fast in my computer. Help me please. https://codeforces.me/contest/1948/submission/251550212

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

    You declared this array char a[2][maxn];

    Then below, you accessed at a[2][j - 1] (a[2] is out of range, so it will cause an undefined behavior)

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

I got fst in E when the contest was not over yet, haha!

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

    Optimistically thinking, you are the first 18 people to solve this problem. It's enough to show that your programming level is really very high (maybe)

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

      May be one day I will also be one top 18 people to get this problem (❁´◡`❁)

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

      The checker did not checked if a is a permutation.
      I got impacted too, but I don't think I was among first 18 people.
      I was among first 18 people to get an AC without printing a permutation.

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

Problem B:(Test: #2) __ I want to see 452nd test case.. Can it possible???

(Test: #2: wrong answer expected NO, found YES [452nd token])

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

Below are The Few Submissions which was same in the today's contest. Please recheck it accordingly there may be more, and they should be penalized for it. It makes the competitive programming unfair. - 251535056 - 251535221 - 251537839 - 251533059 - 251538840

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

((Problem B: (Test: #2) wrong answer expected NO, found YES [452nd token]))

I want to see 452nd test case.. Can it possible???

Code: 251557312

  • »
    »
    8 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    5
    77 0 79 42 69
    
    • »
      »
      »
      8 месяцев назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Thanks a lot...__ But how I find ithe 452nd test case?? Plz, tell me the process...

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

        I can only get small testcase.

        You can write

        if (testcase == 452)
        {
          //output the case; For example
          cout<<n<<"*";
          for (int i=0; i<n; i++)
            cout<<a[i]<<"*";
        }
        

        You can seperate the case with "*" but can't use space/enter.

        When the testcase is not too large, you can find the testcase in Checker comment.

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

Can someone explain the second testcase of problem E ? vertex 4 is a part of 2 cliques (1, 2, 4) & (3, 4, 5)

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

    Presented arrangment of values really allows to relate 4th index for both cliques, but we don't need it to be in both cliques the same time (since we need splitting, not coverage of graph)

    So we choose to relate it to first clique and leave second clique without it (which doesn't prevent the remnants of the second clique from still being a clique)

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

I see we got an issue with the checker of E... but can we start hacking on it now? Open hack is not available for E yet.

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

    There are 40*80 distinct testcases, and there are 5 test files (1 sample and 4 hidden).
    I believe system tests do cover all the distinct testcases.
    The only hack possible should be TLEs by repeating the same test if someone is doing some bruteforces.

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

      Yes, but I did find a solution that could possibly get hacked with TLE, that's why I want to try :)

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

This was last. No more educationals for me.

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

In problem B , my code 251556695 is failing on the 302nd token of test case 2. My code seems correct to me .Can any one point out my mistake ?

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

For problem E, case n = 5 and k = 4, this assignment gets accepted:

a[1] = 2, a[2] = 1, a[3] = 4, a[4] = 3, a[5] = 5

c[1] = 1, c[2] = 1, c[3] = 1, c[4] = 1, c[5] = 2

even though the node 3 the is in both cliques (1, 2, 3, 4) and (3, 5).

I guess a pair is not counted as a clique, but the definition in the problem does not specify this.

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

    It is not in both cliques. You define cliques by the array c. c[3] has exactly one value, thus it is in exactly one clique. The constraint is that the nodes you mark with the same id really form a clique, not that those are all the cliques in the graph.

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

Hack my solution for D (it's O(n^3)). https://codeforces.me/contest/1948/submission/251558115

It got hacked in Python, but the C++ one still hasn't got hacked.

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

For C, any specific reason that grid is limited to 2 * m instead of n * m?

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

Hello !

I need help please for problem B , i couldn't see why my code is wrong .

it's giving me WA in test 2 (testcase 98th). This is my code 251574144

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

    I think you're splitting a_i only if a_(i+1) is lesser. What you missed is, if you're splitting some element, all the previous elements must be splitter.

    For {11, 11, 11, 12, 9}, I think your solution will only split 12 and eventually return false because 11 is greater than the 1 that came from 12.

    I explained a pretty similar thing in my editorial here: https://www.youtube.com/watch?v=_12qOUDlWTE&ab_channel=DecipherAlgorithmswithSaptarshi

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

    Consider the following case:

    3
    11 12 6
    

    Clearly, the answer is "YES", as the array breaks up into 1, 1, 1, 2, 6. However, the output is "NO", as your code only splits apart 12 (but not 11) after comparison with 6.

    I only realized this after WA on the same testcase, and did the following:

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

Folks interested may take a look at my explanations for problems A to E in this round! Tried to touch upon the intuitions that I used to solve those problems during the contest. https://www.youtube.com/watch?v=_12qOUDlWTE&ab_channel=DecipherAlgorithmswithSaptarshi

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

https://codeforces.me/problemset/submission/1948/251537282 Can someone please help me find error in this logic for Problem B

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

Problem G is so cool!

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

why TLE on problem C , using dp solution : submission

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

How to solve E ?

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

finding the edge case for a greedy solution is probably the hardest thing in the universe any one have any tip for this ?

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

https://www.youtube.com/live/6wd0ccbYgg0?si=Iq4ptF7Wa1ztl8Nm Someone was living streaming the contest

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

    Their main account Antonio_Colapso_07

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

      I believe it's not the main. For sure It's the same guy, It's just another alt of his. I was also looking for his main as he said in his stream is max rating is 1847.

      (I don't know why i was obsessed for finding his main acc. I just didn't like how casually he's streaming and people are interacting in the chat. As if, They don’t understand that what he's doing is wrong to the community.)

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

    Please can u write a separate blog so that the whole community can know how this guy is killing the whole spirit of competitive programming. I think his main account should immediately be blocked.

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

can any one drop the answer of A.

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

Oh no. I am one of the 18 people. But still will become master!

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

I couldn't understand one thing, official and unofficial standings are same,but since it was rated for <=2100 ,shouldn't they be different?plz correct/help

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

    for div 3s and div 4s, only "trusted participants" are included in the official standings but it will be rated for <= 1600 and <= 1400 respectively. there's no such restriction for this one so everyone's included in the official standings but it will be only be rated for <= 2100

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

yeah i have become CM in codefoces in 1 yearsr

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

nice contest

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

Is that contest increase rating score??

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

problem D can use a BF algorithm to solve it. Can it make the different from other people?

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

When will the ratings update

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

Has the system testing ended ?

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

Really nice observation in F, I enjoy solving it.

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

Problem D (Tandem Repeat) Video Editorial :

Audio : Hindi

YOUTUBE VIDEO LINK --Click Here

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

When will the ratings be released??

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

Oh, and d can be n^3, is that what they meant? sad...

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

Pathetic time constraints given as O(n^3) solutions passed in problem D

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

What a great codeforces round,I get Expert in this round!

Thanks!!!

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

Scratched my head debugging for a hash-based solution for D during the contest and WA3

When I found the correct solution only takes 25 lines of trivial code:

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

C is a cute problem, thanks!

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

Для проблемы G это вообще не проблема, это станет лучше, но нужно время, чтобы адаптироваться к новой ситуации

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

это вообще не проблема, это станет лучше, но нужно время, чтобы адаптироваться к новой ситуации

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

Dear Organizers,

I write to address the plagiarism accusation I received regarding my submission for Problem C — Arrow Path on Codeforces. It has been brought to my attention that my solution bears a resemblance to that of another user, Aditya_Sarthak/251536325. I wish to emphasize that any similarities between our submissions are coincidental, and I am perplexed by this discovery.

I would like to point out that my submission, under the user ID Shivam_0001/251506209, predates Aditya_Sarthak's submission by approximately 42 minutes, as verified by submission timestamps. Additionally, the coding template utilized in my solution remains consistent with my established coding style from previous submissions, further substantiating my claim of innocence.

I kindly urge you to thoroughly consider these facts before rendering any judgment. I trust that a fair assessment of the evidence will exonerate me from any wrongdoing.

Thank you for your attention to this matter. Shivam_0001