awoo's blog

By awoo, history, 5 weeks ago, translation, In English

Neapolis University Pafos

Hello Codeforces!

We are pleased to announce a new long-term partnership between Codeforces and Neapolis University Pafos. Now educational rounds will be supported by Neapolis University Pafos. Stay tuned and you will find out more soon.

On Mar/15/2024 17:35 (Moscow time) Educational Codeforces Round 163 (Rated for Div. 2) will start.

This round will be rated for the participants with rating lower than 2100. It will be held on extended ICPC rules. The penalty for each incorrect submission until the submission with a full solution is 10 minutes. After the end of the contest, you will have 12 hours to hack any solution you want. You will have access to copy any solution and test it locally.

You will be given 6 or 7 problems and 2 hours to solve them.

The problems were invented and prepared by Adilbek adedalic Dalabaev, Ivan BledDest Androsov, Maksim Neon Mescheryakov, Roman Roms Glazov and me. Also, huge thanks to Mike MikeMirzayanov Mirzayanov for great systems Polygon and Codeforces.

Big thanks to the testers shnirelman and Optoed for their valuable advice and suggestions! Special thanks to Vladosiya for his help with the round.

Good luck to all the participants!

UPD: Unfortunately, there were issues with the problem E judgement during the contest. There were only 18 participants affected by it, so the round stays rated. Rated participants whose verdict on problem E changed may request unrated participation (they have received the directions on how to change their participation to unrated). If you have not received any personal notifications about it in the contest dashboard, you have not been affected.

UPD2: Editorial is out

  • Vote: I like it
  • +279
  • Vote: I do not like it

»
5 weeks ago, # |
  Vote: I like it +11 Vote: I do not like it

excited for A, B, C problems

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

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

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it -15 Vote: I do not like it

      still pupil lol

      • »
        »
        »
        »
        4 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        just keep coding and you will make it!

      • »
        »
        »
        »
        4 weeks ago, # ^ |
          Vote: I like it +12 Vote: I do not like it

        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.

        • »
          »
          »
          »
          »
          4 weeks ago, # ^ |
            Vote: I like it -8 Vote: I do not like it

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

»
5 weeks ago, # |
  Vote: I like it -6 Vote: I do not like it

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

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Mathforces lessgo

»
5 weeks ago, # |
  Vote: I like it -8 Vote: I do not like it

Excited af

»
5 weeks ago, # |
  Vote: I like it -8 Vote: I do not like it

Excited as f

»
5 weeks ago, # |
  Vote: I like it +154 Vote: I do not like it
R.I.P
»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Interested in solving these problems :D

»
4 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

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!

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it -9 Vote: I do not like it

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

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      • »
        »
        »
        »
        4 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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

        • »
          »
          »
          »
          »
          4 weeks ago, # ^ |
            Vote: I like it +3 Vote: I do not like it

          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.

          • »
            »
            »
            »
            »
            »
            4 weeks ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

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

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Hope to get my rating back

Good luck for everyone!

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Oh yes!!! Another Div.2 contest!

»
4 weeks ago, # |
  Vote: I like it +5 Vote: I do not like it

Binary search forces ?

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Will there be an interactive problem?

»
4 weeks ago, # |
  Vote: I like it -11 Vote: I do not like it

As !tester predicting yet another mathforce

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
4 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

lets go =D

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Hi

»
4 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

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

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Who tested?

»
4 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

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

»
4 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

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

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

still have hope

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    No, 10 minutes penalty for each wrong submission.

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      i am asking for right submittions

      • »
        »
        »
        »
        4 weeks ago, # ^ |
          Vote: I like it +14 Vote: I do not like it

        I'm sorry, I read your question inattentively because the round was starting.

»
4 weeks ago, # |
  Vote: I like it +2 Vote: I do not like it

D seems to be easier this time

»
4 weeks ago, # |
  Vote: I like it -23 Vote: I do not like it

The problems in this contest are really bad

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      4 weeks ago, # ^ |
      Rev. 3   Vote: I like it 0 Vote: I do not like it

      Thank, but why TEST 3 is no way to 2,4 ? I think we can go 1,1 -> 1,2 -> 1,3 -> 1,4 -> 2,4 ~~~~~

      ~~~~~

      • »
        »
        »
        »
        4 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        When we move like you said:

        In first turn we will go to (1,2) than like arrow to (1,3). In second turn we will go to (1,4) than like arrow again to (1,3).

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
4 weeks ago, # |
  Vote: I like it +250 Vote: I do not like it

G is a cute problem, thanks!

»
4 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

D felt better than C. C was a bit annoying

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    I wrote BFS for C and it's easy.

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      oh ya I should have done bfs, I did with 2 prefix arrays.I will try bfs thanks .

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Can you explain your bfs approach? I wrote bruteforce and it took me a lot of time. Couldn't figure out how to write bfs for that.

      • »
        »
        »
        »
        4 weeks ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        For every cell check whether there exists a cell in the 4 directions, if yes see the direction inside the cell and move that way. Mark this new (final) cell as visited and add it to the queue, and continue.

        • »
          »
          »
          »
          »
          4 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          My bruteforce is also like that. Maybe I did bfs without actually thinking about it.

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +1 Vote: I do not like it
»
4 weeks ago, # |
  Vote: I like it +13 Vote: I do not like it

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.

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone please explain D to me?

  • »
    »
    4 weeks ago, # ^ |
    Rev. 5   Vote: I like it +15 Vote: I do not like it

    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)

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +16 Vote: I do not like it

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

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Linear search on answer.

»
4 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    4 weeks ago, # ^ |
    Rev. 4   Vote: I like it +7 Vote: I do not like it
    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.
»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Is the formula for F OEIS-able?

»
4 weeks ago, # |
Rev. 3   Vote: I like it +4 Vote: I do not like it

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

»
4 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

Why are constraints on E so low?

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    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.

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +7 Vote: I do not like it

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

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
4 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

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

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

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

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    4 weeks ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    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;

    }

»
4 weeks ago, # |
  Vote: I like it +4 Vote: I do not like it

is string algorithm required in problem D

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it -18 Vote: I do not like it

    It's not, only DS or algorithm you need is prefix sum or segment tree

»
4 weeks ago, # |
Rev. 4   Vote: I like it -90 Vote: I do not like it

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

  • »
    »
    4 weeks ago, # ^ |
    Rev. 3   Vote: I like it -16 Vote: I do not like it

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

»
4 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

anyone solved C using DP?

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yes me

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      How?

      • »
        »
        »
        »
        4 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        • »
          »
          »
          »
          »
          4 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Please share your idea.

          • »
            »
            »
            »
            »
            »
            4 weeks ago, # ^ |
            Rev. 3   Vote: I like it 0 Vote: I do not like it

            So the idea is, we always move forward and never make a move backwards. So we take dp[i][[j][turn] which denotes we are at ith row and jth column and if it's our turn (1) to move or not. Then we check if the current turn is our turn then we can move right/down/up (we check all 3). If it's not our turn we check if the direction is forward or not if not we return false saying there is no way using this path

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    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
    
    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      • »
        »
        »
        »
        4 weeks ago, # ^ |
        Rev. 2   Vote: I like it +1 Vote: I do not like it

        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.

»
4 weeks ago, # |
  Vote: I like it +10 Vote: I do not like it

G was a nice one)

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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";
}
  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can u explain the logic

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      4 weeks ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      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.

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    what's the logic behind that ?

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

»
4 weeks ago, # |
Rev. 2   Vote: I like it -12 Vote: I do not like it

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

»
4 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

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.

»
4 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

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

»
4 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

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

  • »
    »
    4 weeks ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    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

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

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

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Why do you ask?

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I want to know if I having a false solution but no one hacked me.Others' hacking test could affect mine?

»
4 weeks ago, # |
Rev. 2   Vote: I like it +3 Vote: I do not like it

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

»
4 weeks ago, # |
  Vote: I like it +4 Vote: I do not like it

The meaning of passage C was too ambiguous.

  • »
    »
    4 weeks ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    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)

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Wow, i thought it just had to reach there and was having pain implementing, thanks for this

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    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.

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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.com/contest/1948/submission/251550212

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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)

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      thank u so much, I got AC. But why didn't I get complication error instead of TLE

      • »
        »
        »
        »
        4 weeks ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        Because your code is not complicated enough

»
4 weeks ago, # |
Rev. 2   Vote: I like it +18 Vote: I do not like it

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

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +18 Vote: I do not like it

    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)

    • »
      »
      »
      4 weeks ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

Code: 251557312

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    5
    77 0 79 42 69
    
    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      • »
        »
        »
        »
        4 weeks ago, # ^ |
        Rev. 4   Vote: I like it +1 Vote: I do not like it

        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.

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    4 weeks ago, # ^ |
    Rev. 2   Vote: I like it +1 Vote: I do not like it

    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)

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    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.

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

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

»
4 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

This was last. No more educationals for me.

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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 ?

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +1 Vote: I do not like it
    input:

    Expected answer is YES.

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks! It was just a careless mistake I did. I wrote ans.size()>1 instead of ans.size()>0 :(

»
4 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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.

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    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.

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

»
4 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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

»
4 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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
»
4 weeks ago, # |
Rev. 2   Vote: I like it +1 Vote: I do not like it

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

»
4 weeks ago, # |
Rev. 3   Vote: I like it -11 Vote: I do not like it

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

»
4 weeks ago, # |
  Vote: I like it +15 Vote: I do not like it

Problem G is so cool!

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

why TLE on problem C , using dp solution : submission

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Maybe try using array for dp instead of vector

»
4 weeks ago, # |
Rev. 2   Vote: I like it +7 Vote: I do not like it

How to solve E ?

Hint
»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Their main account Antonio_Colapso_07

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

»
4 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

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

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    4 weeks ago, # ^ |
    Rev. 2   Vote: I like it +1 Vote: I do not like it

    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

»
4 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

nice contest

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Is that contest increase rating score??

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
4 weeks ago, # |
  Vote: I like it +14 Vote: I do not like it

When will the ratings update

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Has the system testing ended ?

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Really nice observation in F, I enjoy solving it.

»
4 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

Problem D (Tandem Repeat) Video Editorial :

Audio : Hindi

YOUTUBE VIDEO LINK --Click Here

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

When will the ratings be released??

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
4 weeks ago, # |
  Vote: I like it +6 Vote: I do not like it

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

»
4 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

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

Thanks!!!

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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
»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

C is a cute problem, thanks!

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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