nifeshe's blog

By nifeshe, 2 months ago, In English

Hi, Codeforces!

I'm delighted to invite you to the best/second best/third best round of 2025 so far! Codeforces Round 997 (Div. 2) will be held on Jan/17/2025 17:35 (Moscow time). You will be presented with at least $$$6$$$ and at most $$$6$$$ problems, one of which might be divided into two subtasks, and $$$2$$$ hours to solve them.

Many of you may not believe it, but the problems were authored and written by nifeshe with a great help from maomao90. Moreover, I would like to thank:

The score distribution is as follows: $$$500-1250-1500-2000-2250-(2750+1250)$$$.

I hope you will find a non-empty subset of problems to be interesting. Good luck!

UPD 1: Editorial

UPD 2: Congratulations to the top 5!

Div. 1 + 2:

  1. maspy
  2. BurnedChicken
  3. jiangly
  4. antontrygubO_o
  5. Sugar_fan

Div. 2:

  1. OdtreeKing
  2. saaaalty
  3. STUDENT0
  4. rainboy
  5. MamurjonDeveloper

UPD 3: First solves:

A. 00:02:01 by hitonanode

B. 00:02:17 by pipi0818

C. 00:03:52 by Proof_by_QED

D. 00:13:53 by wishgoodluck

E. 00:18:06 by zdc123456

F1. 00:27:48 by peti1234

F2. 00:28:40 by rainboy

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

»
2 months ago, # |
  Vote: I like it -20 Vote: I do not like it

According to the score distribution, it seems a bit easier than last div2 Round ?!

»
2 months ago, # |
  Vote: I like it -21 Vote: I do not like it

So now the LGM tag isn't even good enough for the "And You for participating!" line. They've trampled all over the meaning of the word legendary.

»
2 months ago, # |
  Vote: I like it +24 Vote: I do not like it

Believe it or not, I tested.

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

As a participant, i will try to solve A within 5 minutes.

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    i believe in you

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    lets do it!!

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

    Nike:Just Do It.

  • »
    »
    2 months ago, # ^ |
      Vote: I like it -24 Vote: I do not like it

    As a cheater who got her first contest skipped, I will try to cheat my way to Pupil in this round

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      But why u solved C only?? Didn't u got solutions of A or B?

      • »
        »
        »
        »
        2 months ago, # ^ |
          Vote: I like it -11 Vote: I do not like it

        I read many blogs after contest skips which mostly say they got skipped because their codes were short and common so I didn't copy A or B because the ones I found on youtube and telegram were very small like 10-12 lines only

        • »
          »
          »
          »
          »
          2 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Cheating with prepration.Crazy

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

            lmaao you call it preparation? My classmates took an entire course worth 3000 PKR which trains them on how to avoid plag while copying codes from telegram/youtube. They also give them resources to cheat like names of telegram channels, websites and even contacts of people who sell it at cheap rates (for problems E or F of Div 2. Upto D are mostly free. Paid only if you need D in less than 1 hour). They also give plag detector links where you copy paste both source code and your code and it tells you percentage overlap. Live contest doubt support is also provided like if you get WA after changing they tell you why it gave WA rather than giving solution to make you independent for future contests. They also have mock contests where you are given answer code and you have to change it during contest and then they are run through plag checkers to see if they match. My brother himself prepares 8 hours a day from that course but my parents didn't spend money for me because I am a girl and they don't want me to get a job. But what you call cheating isn't a noob's thing this also requires efforts and learning it is a science of its own if you want to learn how to change codes quick and bypass plag checker and test your code for plag live contest. I just try to learn as much as I can by seeing them. But that group has given some Candidate Masters (one from our country too) and Masters too. But not everyone gets there unplagged only the most efficient people do. Many get caught and get banned as Pupils/Newbies and many cant understand code enough to change it beyond A.

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

              :)

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

              speechless -_-

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

              maybe instead of cheating just learn how to code its not that hard

            • »
              »
              »
              »
              »
              »
              »
              2 months ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              The C question that got skipped for you from before, it looks AI generated. You're most probably being scammed by these sources in multiple ways. lmao.

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

    We have the same picture :)

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      maybe we have stolen this picture from the same person

»
2 months ago, # |
Rev. 2   Vote: I like it +9 Vote: I do not like it

Hope we can have easier E and F to solve. E and F for last Div.2 are not fit for rated participant(but it has nothing to do with me thinking they are good problems, especially E is interesting), only two can solve E and no one can solve F is abnormal.

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It seems like that E is much more friendly but F2 still hard.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

what is the contest duration

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I think this is the new shortest official contest blog, beating the previous contest's blog.

»
2 months ago, # |
  Vote: I like it +30 Vote: I do not like it

Hoping for the contest to have >2 solves on E, F! (oops)

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

B seems harder than usual

»
2 months ago, # |
Rev. 5   Vote: I like it +41 Vote: I do not like it

If I don't become specialist in this contest then I'll

spoiler
  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    good luck

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    nice one :)

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    1000 problem solved wow! why dont u start solving higher rating problems tho?

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Currently I'm learning various topics and practicing on others platforms and solving problems topic wisely..

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I think it will be interesting round !

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Hope to solve at least 3 and get specialist

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Mashaa allah on ur profile salah, i have no idea what will happen tommorow but i know that you put a lot of effort, best of luck.

»
2 months ago, # |
  Vote: I like it +5 Vote: I do not like it

This has probably been answered before, but why not have all the rounds on weekends? Americans can not compete in standard-time weekday contests.

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

    If you can't even compete in standard-time weekday contests, are you even free?

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Like the last contest, I don't want to mess up this one either. :)

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

hope i will become specilist i this contest

»
2 months ago, # |
  Vote: I like it -6 Vote: I do not like it

hard contest IG... 500-1250

»
2 months ago, # |
  Vote: I like it +50 Vote: I do not like it

"You will be presented with at least 6 and at most 6 problems" interesting description.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

score distribution looks so puzzled, especially second and last ones. Will test!

»
2 months ago, # |
  Vote: I like it +3 Vote: I do not like it

As a participant, I will try to beat rainboy ;)

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

believe it or not, i wish good luck to everyone(also to me, i hope ill finally reach pupil~)

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Im very sure that this will be one of the contest of all time

»
2 months ago, # |
  Vote: I like it +29 Vote: I do not like it

Guys I think there are 6 problems

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You got it wrong bro... There will be at least 6 and at most 6 problems.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

What will be a 1250 score div2b like be?

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Since score is relative to previous problems, I think problem A will be more easier as B is 1250 scored...

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I just want to break the curse of problem c. I'll definitely solve it this time ^.^

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

You will be presented with at least 6 and at most 6 problems.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

will be ending myself if i cant solve D.

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

My First contest. Hopping to solve at least one!!

Spoiler
»
2 months ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

how many question i have to perform for becoming specialist?

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

    This depends totally on Round.. But I guess 3 Problems would be a safe number for you. If the contest is easier, speed matters..

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

hopefully pupil

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can't wait to participate.

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

I will solve at least 0 problems and at most 6 problems.

Believe it or not...
»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Wish everyone have a good time!

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

hoping to solve C this time and D if possible

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

It's nice

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hoping I could get into 1600++ :D

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

good luck

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Serious disappointment after waiting for a week.

»
2 months ago, # |
  Vote: I like it +25 Vote: I do not like it

insane gap from c to d

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

wtf diff gap A *900 B *1400 C *1500 D *2200

»
2 months ago, # |
  Vote: I like it +3 Vote: I do not like it

B > C

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

rip

»
2 months ago, # |
  Vote: I like it +21 Vote: I do not like it

Why continue to make problems like C,it serves no purpose, extremely disappointed by the quality of problems.

»
2 months ago, # |
Rev. 2   Vote: I like it +19 Vote: I do not like it

first 56 minutes: Solve Problems

last 1 hour 4 minutes: stare at standings 💀

»
2 months ago, # |
Rev. 2   Vote: I like it +12 Vote: I do not like it

B >>>>> C, the order of B and C should be swapped. Who started with C will very likely to win a lot of rating in this contest

Also I have absolutely no idea how to solve D sadly. (last div2D was way better tbh)

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    i think D needs combinatorics, i couldnt figure it out tho

»
2 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Am I the only idiot that can't even figure out what B is asking. I swear the diagram they've given is wrong but maybe I'm just dumb.

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It took me a long time, too. But the graph has connections between two items if and only if the earlier item is smaller. My solution was to build a list with vector and insert() so that each node used only information from previous nodes to determine its relative position.

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

      Is the diagram they've given correct? My confusion lies in the fact that p1 = 4. In the adj matrix, it has edges to p3 = 1 and p5 = 5. But in the diagram they've given, 4 only has an edge to 5.

      • »
        »
        »
        »
        2 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Looking at it again, it seems connections in the graph are determined by relative position in the permutation.

        4 has no lesser elements before it, so there are 0 edges out of 4 to lesser elements. 5 has 4 lesser elements before it, so there are 4 edges out of 4 to lesser elements. I agree that it is a confusing problem, I assumed it was anti-LLM tech or something

      • »
        »
        »
        »
        2 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Yeah the mapping between p_i and i was the hardest part for me as well.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

problem C is such a piece of shit

le 'solution'

why this allowed?

»
2 months ago, # |
  Vote: I like it +10 Vote: I do not like it

Problems were pretty difficult but also really nice.

Thanks for the great contest!

»
2 months ago, # |
  Vote: I like it +17 Vote: I do not like it

This is (in my opinion) one of the best div2 rounds I have ever participated in. Thank you for the brilliant problems. I enjoyed every problem (except B). Ran out of time in F2 after getting the main observation in last 10minutes :(

  • »
    »
    2 months ago, # ^ |
    Rev. 5   Vote: I like it -10 Vote: I do not like it

    fuck B fr https://codeforces.net/contest/2056/submission/301459050 ദ്ദി ༎ຶ‿༎ຶ ) another rating minus

    edit: ok I solved it, now stop downvoting me ദ്ദി ༎ຶ‿༎ຶ ) https://codeforces.net/contest/2056/submission/301685928

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

    For you

    See difficultly gap between C -> D. It was one of worst time trial for div2. how to solve ABC fast, depending on time it can be gray or orange

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

      chill

      enjoy the problems. Quality is much more important than any difficulty imbalance (and before you say I am saying this only because I am too high rated for div2, I really like AGCs despite solving 0-1 problems)

      difficulty gap hardly matters in the long run (unless you secretly believe that everyone wants you to always suffer and gives only your rating the big difficulty gap each time)

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Congratulations! Please tell us, o'great man, solution to problem D. My mind is melting.

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Agreed for A and D. D especially is a very nice problem.

    Though B and C, the language for them was pretty bad. Spent more time reading the Q than thinking about the problems. Those two could have been way better phrased imo.

»
2 months ago, # |
  Vote: I like it +8 Vote: I do not like it

FastForces intensifies and C << A << B

»
2 months ago, # |
  Vote: I like it +19 Vote: I do not like it

I couldn't solve D, but it was an amazing problem imo.

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

For D, is it all odd lengths are automatically the answer calculate in O(n) for even length you sort the array of (value,index) in increasing order and then solve the equation

max(l.second, r.second) - min(l.second, r.second) = r - l

Use some Data structure to calculate this for all pairs having array[i].first == array[(i+1)].first

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    In that case, if we sort each and every subarray, doesn't the time limit get exceeded?

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      If you can solve the max(l.second, r.second) - min(l.second, r.second) = r - l in some O(log(n)) time the time complexity is O(nlogn) The max and min are in range from l to r can be computed with Segment tree but at each r for what l am i doing it?

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

        segment tree ahh! mb i did something like this:

        for (int i = 0; i < n; ++i) {
                for(int j=i;j<n;j++){
                    if ((j - i + 1) % 2 != 0){
                        ans++;
                        continue;
                    }
                    vector<int> b;
                    for(int k=i;k<=j;k++){
                        b.push_back(a[k]);
                    }
                    sort(b.begin(),b.end());
                    if(b[(j-i)/2] == b[(j-i)/2 + 1]){
                        ans++;
                    }
                }
            }
        

        for this time limit exceeds obv(im a newbie). i tried to implement it with freq array(as a<=10) to optimize it but still time limit exceeded.

        • »
          »
          »
          »
          »
          2 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Even if you used seg tree how are you dealing with the above 2 nested for loops?

»
2 months ago, # |
  Vote: I like it +1 Vote: I do not like it

thank you for contest!! D was good problem. However, I am not too sure about the point of question C

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

I think graph was introduced in problem B just to scare the participants.

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I got scared while the contest I thought dfs is the method to used

»
2 months ago, # |
  Vote: I like it +24 Vote: I do not like it

6000 solved C, 500 solved D nice complexity management!

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

E seems way easier without the equality in the 2nd condition. How to solve with the condition having $$$\leq$$$?

»
2 months ago, # |
  Vote: I like it +3 Vote: I do not like it

What a big gap bitween C & D!

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone tell me which test case my code failed in B. https://codeforces.net/contest/2056/submission/301455594

I thought I would solve at least 3 problems. I was really sure that C will give me hard time but well life can be very surprising sometimes.

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

    t=1 n=3 000 001 010 Correct answer: 2 3 1. Your answer: 3 2 1. I didn't quite understand your idea, but it seems that it's just wrong

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

      actuallyl it is an adjacency matrix so your input is fundamentally wrong. In undirected graph the matrix is symmetric

      • »
        »
        »
        »
        2 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        1
        3
        000
        001
        010
        

        I implied this input, it's just that I didn't know how to markup my comment prior

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

          Oh I misunderstood. I think I got the problem in my approach. Actually my idea was to start with the minimum element that is 1 and than see how many elements it is connected to which are more than it.

          Than I take the total number of these elements, subtract it by n and that is the position of 1. But I didn't implement the caculation process of subsequent elements correctly and that's where my downfall lay...

          Anyway thank you for your testing it helped me to understand problem in my code that has been bugging me for a while now.

          Have a great day/night.

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Any idea which test case is failing for my submission: 301434979 for Problem B. I used a bubble-sort-like approach.

      • »
        »
        »
        »
        2 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        1
        4
        0000
        0000
        0001
        0010
        Correct answer: 3 4 2 1
        Your answer: 3 2 4 1
        Had to perform sorcery to pull this out of the system tests
        
»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

tf is problem B?? problem D: wow small question(length wise) lets try it, tried it and was able to solve it in first attempt with time compl of O(n^3logn),optimized it and submitted still time limit exceeded.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone tell me what's wrong in my code?

CODE
»
2 months ago, # |
Rev. 2   Vote: I like it +6 Vote: I do not like it

hate speedforces and B ate all my damn time. 5 more minutes and could've done C whatever looking forward to better weekend contests

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

be me
spend almost 1 hour on problem B
can't solve it
reluctantly switch to problem C
solve it in 2 minutes flat
realize I only got 1000 points out of 1500 on C because of B
mfw B ruined everything

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    same

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you explain what C is saying in simple words please? I can't understand what problem C is saying

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

      it says we need a sequence of size n which have:
      1. count>size n (count=the number of subsequnces which are longest palindrome sequences in our ans)
      This is what I understood, couldn't solve it though

      • »
        »
        »
        »
        2 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        How I approached the problem- 1)Initially a sequence like 1,2,3....n Here f(a)=1(since the longest palindromes are 1,2,3,..n each of size 1) and g(a)=n but we need g(a)>n 2) lets change the last number to 1 so sequence is 1,2,3,4,5,.....n-2,n-1,1 now f(a)=3 (longest palindrome = 1,x,1 for all x in range [2,n-1]) but still g(a)!>n

        3) Lets replace one more number with 1 say with 3rd element (n>=6 given in que) 1,2,1,4,5,....,n-1,1 (longest palindrome = 1,x,1 for all x in range [2,n-1]) (Same as before) but now we can form it in more number of ways and g(a)>n

        code-

        void solve(){
                int n;cin>>n;
                vi a(n);
                for(int i=0;i<n;i++){
                    a[i]=i+1;
                }
                a[3]=1;
                a[n-1]=1;
                printArr(a);
            }
        
        • »
          »
          »
          »
          »
          2 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          thank you for helping, I actually gave up after 2nd step and decided to brute force the permutations which I was not able to implement and it was clearly not a time efficient approach

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It took me a long time, too.

»
2 months ago, # |
  Vote: I like it +1 Vote: I do not like it

not even in my dreams would i expect seeing graphs in a div. 2 B lol

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    u dont need knowledge pf graphs to solve it, they just used them to write the question in a different way .

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem C why we cannot do

int n;
cin>>n;
for(int i=0;i<n;i++)
cout<<1<<" ";
  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Because that produces only a single palindrome with length N.

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    The maximum palindromic subsequence would then be the whole sequence, so g(a) = 1.

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    then f(a) = n, g(a) = 1, which is failed the problem condition g(a) > n

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    f(a) will be n g(a) will be 1 we need g(a) to be > n

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    f(a) becomes n, g(a) becomes 1.

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You will get only 1 longest sequence 1 1 1 1 1 1 ....ntimes

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    if do this, the longest palindrome subsequence of a is a, then f(a) = n and g(a) = 1

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Then the longest palindromic subsequence will be of length n, so f(a)= n, now g(a)=1 and its a condition in que that g(a)>n. Thus this wont work

    My solution-

    void solve(){
            int n;cin>>n;
            vi a(n);
            for(int i=0;i<n;i++){
                a[i]=i+1;
            }
            a[3]=1;
            a[n-1]=1;
            printArr(a);
        }
    
  • »
    »
    2 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    thanks everyone I understood now!

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem D, I came up with the following conditions for subarrays with even length $$$l$$$ and median is $$$m$$$:

If $$$x$$$ is number of elements $$$<m$$$ and $$$y$$$ is number of elements $$$>m$$$, then $$$l-2x \geq 2$$$ and $$$l-2y \geq 2$$$.

Following this observation, $$$O(10n^2)$$$ solution is obvious to me. How can this be improved to $$$O(10n \log n)$$$? I was trying some $$$\texttt{ordered_set}$$$ and $$$\texttt{order_of_key()}$$$ stuff but could not come up with the solution. Can anyone help me with it? Here is my submission link.

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    using inclusion-exclusion principle.

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Same here :-(

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

    For a particular subarray [l,r] we can say that it is bad if either of these 2 conditions are true l-2x<=0 & l-2y<=0. Both of these can't be true simultaneously unless m isn't present in that subarray.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem B was cool as it is the definition of topological sorting

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    lol

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    bruh how you even got answer with topological sort I did 3 wrong submission for that It ain't topological sort brother

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Convert the graph to directed graph by checking if there is an edge between two nodes and draw directed edge from the smaller node to the bigger node. After that run topological sorting on the new graph and this will be the answer

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

There was a problem with the checker of problem C. WA here AC here . Codes are same but specifically for only the third testcase it showed WA if i did not print a gap after the last integer(i printed newline). also F(a) would be 3 but the checker showed 5. hence the checker must be incorrect and i incurred a lot of extra penalty

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

    Consider spending more time thinking before claiming the checker is wrong.

    Hint
»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Why was B graph?

lol I did not expect this.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone give hints for D:))

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem C literally writes the answer for $$$n\ge 9$$$, and I don't know if it is intended.

  • »
    »
    2 months ago, # ^ |
    Rev. 2   Vote: I like it +3 Vote: I do not like it

    It literally writes the answer for all $$$n$$$ lol.

    My AC solution is just:

    1. Print first element of $$$n = 6$$$ sample ($$$1$$$).
    2. Print $$$n - 6$$$ values $$$4, 5, \ldots, n - 3$$$
    3. Print the remaining 5 elements ($$$1$$$ $$$2$$$ $$$3$$$ $$$1$$$ $$$2$$$) of the $$$n = 6$$$ sample.

    The intuition is that each element added in (2) increases the number of palindromes with the first two "1" by exactly 1, so it will always be $$$\gt n$$$.

    Now if only I could have figured this out before coming up with a general solution for $$$n \gt 9$$$ and individual hard coded cases for $$$6 \leq n \leq 9$$$ T_T

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      There's an even better solution.
      Just print $$$i$$$ for $$$1...(n - 2)$$$
      Then print $$$1$$$ $$$1$$$ as last 2 elements.

    • »
      »
      »
      2 months ago, # ^ |
      Rev. 2   Vote: I like it +5 Vote: I do not like it

      My AC solution is:

      1. For $$$n=6,7,8$$$, use the prefix of $$$[1,1,2,3,1,2,3,8]$$$.
      2. For $$$9\le n\le 14$$$, print the second sample and append different numbers.
      3. For $$$n\ge 15$$$, print the third sample and append different numbers.
  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I just print 1 1 2 3 4 ... (n — 2) 1 (palindromes are in the format 1 ? 1). This solution does not work with n < 6.

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    My solution is directly derived from the first sample. The following sequence:

    $$$\begin{align*} a = [1, 1, 2, 3, \ldots, n - 3, 1, 2] \end{align*}$$$

    satisfies the problem's condition, because $$$f(a) = 3$$$ and there are sufficiently many palindromic subsequences of length $$$3$$$.

    I really doubted myself when I found this, and I had to repeatedly check it...

»
2 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Problem A was harder than problem C.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

My solution for B is literally just a simple sort function, I don't know why it's considered to be "much" harder than A lol. Personally, I spent a little more time on A than B.

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    can you share your solution???

    • »
      »
      »
      2 months ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it
      Here it is
  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    maybe due to its wording, a more clear statement would have done its job.

»
2 months ago, # |
Rev. 2   Vote: I like it +9 Vote: I do not like it

Feeling the distinction of difficulty levels in the last two contests kinda frustrating. Each problem is cool when viewed individually, but together in a single contest, they don't form a reasonable difficulty gradient.

Btw, I thought getting the answer for $$$n\geq9$$$ directly from the sample is the intended solution for C. It's interesting to see it's not

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

Is this the intended solution to D? Or is there an easier approach?

  1. Iterate on each possible median $$$1 \leq m \leq 10$$$.
  2. For each median, iterate over $$$r$$$ and count the number of $$$l$$$ with median $$$m$$$.

Notice that a given range [l + 1, r] is not good if either of the following are true:

  • $$$\text{prefix_lt}_{r} - \text{prefix_lt}_{l} \geq \frac{r - l}{2}$$$
  • $$$\text{prefix_gt}_{r} - \text{prefix_lt}_{l} \geq \frac{r - l}{2}$$$

where $$$\text{prefix_lt}$$$ and $$$\text{prefix_gt}$$$ represent the prefix sum of numbers less than and greater than $$$m$$$ respectively.

This can be re-written as:

  • $$$2 \cdot \text{prefix_lt}_{r} - r \geq 2 \cdot \text{prefix_lt}_{l} - l$$$
  • $$$2 \cdot \text{prefix_lt}_{r} - r \geq 2 \cdot \text{prefix_lt}_{l} - l$$$

Notice that the two conditions are mutually exclusive, so you can just subtract these two counts separately:

$$$r - \text{cnt_prefix_lt_upto}(2 \cdot \text{prefix_lt}_{r} - r) - \text{cnt_prefix_gt_upto}(2 \cdot \text{prefix_gt}_{r} - r)$$$

(except for the case where the median value isn't present in the subarray, lets ignore that since I ran out of time trying to fix that, we will likely have to store the "l" values till we see an $$$m$$$ after it)

$$$\text{cnt_prefix_lt_upto}$$$ / $$$\text{cnt_prefix_gt_upto}$$$ can be fairly directly implemented with a Fenwick Tree (bit).


So this feels way too overcomplicated for a problem D to me, am I missing an easier solution or is my brain just fried today?

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    you can solve it by doing the -1/+1 trick for medians + a sprinkle of PIE.

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I dont think they are mutually exclusive, they may each equal exactly half?

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    We can calculate by inclusion-exclusion principle: Let b be any subarray of a of even length, cnt[i] = # of occurences of i in b. b is not good iff there exists some j, such that cnt[1]+cnt[2]+...+cnt[j] = |b|/2.

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

My $$$D$$$ solution:

First, we notice that maxa is quite small, which inspires us to enumerate the median.

Suppose we determine the median $$$m$$$ and only count the even-length subarrays. The subarrays we are looking for must satisfy the following conditions:

  • Contain at least one $$$m$$$;
  • The number of elements less than $$$m$$$ is less than half the length of the subarray;
  • The number of elements greater than $$$m$$$ is less than half the length of the subarray.

It seems difficult to count the subarrays directly based on these conditions. We transform this problem by considering the subarrays that do not satisfy the conditions:

  • Contain at least one $$$m$$$;
  • The number of elements less than $$$m$$$ is greater than or equal to half the length of the subarray, OR the number of elements greater than $$$m$$$ is greater than or equal to half the length of the subarray.

This makes it easier to count. Next, we explain how to count the subarrays where the number of elements less than $$$m$$$ is greater than or equal to half the length of the subarray.

Let the array be $$$v$$$. If $$$a[i] < x$$$, set $$$v[i]$$$ to 1; otherwise, set $$$v[i]$$$ to -1. Then, calculate the prefix sum array $$$pre[i]$$$. This allows us to find the number of indices $$$j$$$ such that $$$pre[j] \leq pre[i]$$$ using a binary indexed tree (BIT).

We also need to ensure that the subarray contains at least one $$$m$$$, which can be maintained by using a waiting area wait. When calculating the prefix sum $$$pre[i]$$$, we do not immediately insert it into the BIT but instead place it in the wait area. Once we encounter a new $$$a[i] = m$$$, we insert the information from wait into the BIT and clear the wait area.

»
2 months ago, # |
  Vote: I like it -20 Vote: I do not like it

Is it a speed typing contest, like three digit rank after solving three questions and also 8k rank after solving three questions (⁠ ⁠╹⁠▽⁠╹⁠ ⁠)ʘ⁠‿⁠ʘ

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    yeah but usually higher rated people got better ranks so nothing changed.(I reached my goal finally)

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Any idea which test case is failing for my submission: 301434979 for Problem B. I used a bubble-sort-like approach.

»
2 months ago, # |
  Vote: I like it +47 Vote: I do not like it

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

What is wrong with my B submission ? : 301457552

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Lost D because of an extra unnecessary assert :(

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

i am unrated and solved first qun in this contest will i get rated

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

why is everybody hating the round. i think author made a great job. that round teaches how not to afraid of tasks. task B — is not even the alghoritms on graphs. C task was really good and funny and teaches that you don't have to be afraid if task marked by letter C,D or smth else. i appreciate the author :)

and, nifeshe , i play chess too, text me if you wanna play with me)

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

In 3rd question all pretests passed but in the final checking it was not checked and was neither accepted nor failed in any test , I expect this as a glitch in the website , kindly look into this and help to get the correct standing .

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

My C solution 1 1 2 3 .....n-2 1 Here g(a) = 2n-5 which will work for all n>5

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

D is an amazing problem!!

Spoiler
»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Solving D felt so good, finally CM-ing. Loved the contest! The question quality was really nice, although difficulty of C felt a bit off compared to normal C's.

  • »
    »
    2 months ago, # ^ |
      Vote: I like it -16 Vote: I do not like it

    u r sus. U have comments in your code + u have skipped code.

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      He is one of those cucks that uses chatgpt for help. His skipped code is all GPT.

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      i tend to comment my code in harder questions. also i have never had a skipped contest wtf ? cope for your skill issue instead of being jealous

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

        u have a GPT generated code that got skipped in round 949. lol, Cope? I feel pity not jealousy for losers who are so low IQ that they need GPT for div2 B.

        • »
          »
          »
          »
          »
          2 months ago, # ^ |
            Vote: I like it -12 Vote: I do not like it

          LOL. blud probably regrets commenting. Funny thing you cant delete comments on codeforces. Great feature mike.

        • »
          »
          »
          »
          »
          2 months ago, # ^ |
          Rev. 2   Vote: I like it +6 Vote: I do not like it

          my good sir, that code was copied from geeks for geeks since it was a standard function (you can verify this).. i resubmitted it after i found a better solution, not knowing that resubmitting an AC makes your previous AC submission skipped

          if you have enough braincells, you should realize that a skipped submission due to copying makes your whole contest skipped, and that contest was rated for me

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

            why would you resubmit a question that u already had AC? Dont get the point. Did you predict its gonna get skipped?

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

              i didnt know at the time that re-submission costs you lol. i wasnt able to solve D and felt like i worked out B myself (instead of just googling bitwise or of a range: https://www.geeksforgeeks.org/bitwise-or-or-of-a-range/ the code is this exact article btw), and i wanted to resubmit my new soln.. didnt want to waste time till contest ended because i literally didnt know it would cost me ?

              and fyi i am icpc regionalist in my region with like ~ 50 onsite rank, so baseless accusations like this are quite offensive

              • »
                »
                »
                »
                »
                »
                »
                »
                2 months ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

                Also fyi i hate cheaters too (you can see my controversial blog replies to some posts), but sometimes you should think a bit more before making accusations ??

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

                You being good doesnt mean you wont cheat. Masters have been caught cheating. Someone said this when psychotic_d was caught. "Anyone can cheat. An expert can cheat to become CM, An international Master can cheat to become LGM, only person who probably dont benefit from cheating is tourist himself in his prime". So thats a lame excuse. Hopefully you dont cheat but u r definitely sus.

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

                  Sure, but it does add credibility.

                  And it is kind of lame that instead of apologizing for making accusations without much evidence (for example, being unaware that resubmitting after getting an AC makes your submissions skipped, and that submissions skipped due to cheating skip your whole contest), you still quote "anyone can cheat".

                  Sure bro, with that logic, you can be a cheater too. Maybe, have some actual evidence (like a skipped contest?) before making such accusations ?

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

It is my first-contest on the platform and i am able to solve problem A but my rating is not shown on a dashboard any one help plzz. Why it is not showing ??

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I guess the problem writer chose $$$n≤100$$$ in problem C because they also do not have a good way to calculate the value of $$$g(a)$$$.The small range of $$$n$$$ makes a brute-force search of all cases possible. I think this is probably not what they wanted.

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

For problem C, simple solution, we can do 1 1 2 3 ... upto (n-3) 1 2. with this method the length of longest palindrome subsequence will always be 3.

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

    You printed $$$n+1$$$ elements for each test case instead of $$$n$$$. Therefore, the checker read 1 1 2 3 4 1 for the first case, and read 2 1 1 2 3 4 5 6 7 for the second case. Note that it doesn't care whether the elements are on the same line or not. With 2 1 1 2 3 4 5 6 7, the longest palindrome subsequence is 2 1 1 2, of which the length is indeed $$$4$$$.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I've just found the solutions of bieybay are obfuscated (sample: 301404672, 301404858, 301405070), which is against the contest rule. This person should be disqualified.

»
2 months ago, # |
  Vote: I like it +6 Vote: I do not like it

How did MamurjonDeveloper solve b in 2 mins .... his submissions seems sus.maomao90

»
2 months ago, # |
  Vote: I like it +4 Vote: I do not like it
Meme on problem C
»
2 months ago, # |
  Vote: I like it +13 Vote: I do not like it

What's with the constraint of n in C? Why is it so small?

Also you can just put random distinct numbers at the end of the 3rd sample answer, as g(a)=190 which is >=100

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    because the checker took O(n^2) to check if your sequence is valid every test case

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

In the second matrix of the B's sample, it says that p1 < p3 and p1 < p5, but why the output is p1 = 4? Can anyone explain that to me?

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It is a bit confusing for example p3 (node 1) in the permutation satisfies the condition p3<p4 so p3=1 and p4=3 there is a edge between them

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    B is not a graph algorithm problem actually

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      So is B incorrect or am I confused in somethings bro ?

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Slowest first solve for A problem

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

good contest ... But where is rate

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

wtf is 2 mn

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

I'm editing my comment because I can't delete it

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You can delete your comment before two minutes of posting time

»
2 months ago, # |
  Vote: I like it +8 Vote: I do not like it

I think first solve also need to divided into div 2 and div 1+2,I don't want to lost my problem C"s first solve.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

For some reason i felt B should have been C and C should have been B in this contest. :P

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    both of them are div2B in my opinion

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    but yeah C took me 21 minutes to solve B took 28

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

      i wasted most of my time on B just to realise after contest it was simple toposort. C was ig done in 10 minutes.... should have tried C 1st

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

B and C should be exchanged

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

how can I become a tester of official div2 round

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

why was C easier that B?

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I'm happy to join in codeforces

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

Hello Codeforces Team,

I recently received a notification about my solution (Submission ID: 301463482) coinciding with other submissions (301458678 and others) during [Contest Name, Round #997].

I would like to clarify the following:

Submission Details:

I wrote the code independently and did not engage in any form of code sharing or collaboration during the contest. I used VS Code and submitted the solution directly to Codeforces.

the problem solving logic is apperaring similar but this is ig a coincidence i have not used any external tools or public platforms like ideone with public settings

i am ready to provide a nessesary screenshot as evidence or mydraft code from my laptop to demonstrate that i worked on the problem independently Please let me know if any further clarification or evidence is required. I sincerely request you to review my case as I have always adhered to the contest rules.

Thank you for your understanding, and I apologize for any unintended misunderstanding.

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

As a tester, I have a proof that upvoting this comment will lead to positive delta. But the proof is too long to fit the margin.