myst-6's blog

Codeforces Round 982 (Div. 2)
By myst-6, history, 5 weeks ago, In English

Hello Codeforces! Me and yud08 are excited to invite you to take part in Codeforces Round 982 (Div. 2), which starts on Oct/26/2024 17:35 (Moscow time). You will be given 5 problems and 2 hours to solve them. Two problems are divided into two subtasks.

This round will be rated for all participants whose rating is strictly below 2100.

The problems were authored by me and yud08, and prepared by me.

We would like to thank:

We hope you enjoy the problems!

Score Distribution: $$$500 - 1000 - 1250 - (1250 + 1000) - (2000 + 1000)$$$

We actually wanted to continue the trend of posting photos of contest writers, but we could only find one photo containing both of us, which was a group photo that we took with some other UK informatics people! (I'm the one in the back of the picture who is wearing the MHC T-shirt and yud08 is the one whose head is popping out from the left side of the photo.)

20240921-153321

UPD1: Congratulations to the winners of the contests:

Div 1:

  1. jiangly
  2. neal
  3. SSerxhs
  4. A_G
  5. kotatsugame

Div 2:

  1. nathan_higgs
  2. purupurupururin
  3. Nonoze
  4. Hong_Meiling
  5. Nika_Tamliani

Also, first solves! (if any of these are wrong please let me know)

UPD2: Editorial is available here

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

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

As a tester, this is my first "as a tester" comment.

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

Since we all know real Codeforces rating is actually determined by rating * contribution, as a writer, give me contribution.

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

    This means I have to decrease my rating for increase my real codeforces rating?

    → Reply
»
4 weeks ago, # |
← Rev. 2   Vote: I like it +42 Vote: I do not like it

As a tester, the contest is very good and I like all the problems!

Also, orz myst-6

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

as a tester, i swear on skippity problem F can be solved by binary searching a segment tree and morphing the result into a dsu before finally getting the answer using a mixture of crt and fft (alternatively you can use a persistent 1729-dimensional convex hull trick on a sparse segment tree)

Also, orz myst-6

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

As a tester, do not miss the contest.

→ Reply
»
4 weeks ago, # |
← Rev. 2   Vote: I like it +10 Vote: I do not like it

Love the photo! Who are the other mysterious coders in it? One of them has a blank screen. We need to know :)

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

As a tester, just put the contribution in the comment bro

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

BucketPotato orz

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

Another quick chance to re-perform after all these greedy pains and hacks on map... Hope to reach pupil again this time

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

Last year I made the same question and still don't know why to make a contest on Ieeextreme day T~T Ik maybe it's not on clist but most of coders know about ieeextreme and its date. Anyway, Thanks authors for a new round ^-^

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

After this contest, I will be pupil!

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

I am the camera

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

Whats (1250 + 1000). Can someone explain?

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

    It's a problem with a subtask, subtask of a problem means it will be a similar problem but with harder constant or condition.

    Another way to see it is 2250 problem being splited out into (1250 + 1000) for easier approach. Which aimed at weaker contestant to have a chance at solving (like me, the lower rating part).

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

LongTrainDiv2

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

As a tester, I love the problems! ＼(＾▽＾)／

Also, orz myst-6

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

Hoping for the best Div.2 round. All the best to all contestants!

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

wtf these guys look too chad to be studying cs

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

    As someone who knows at least half of them quite well, I can confirm that they are real skibidi rizzlers with true chad energy.

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

      just put the code in the IDE lil bro

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

        RAHHHHHHHH VIM IS THE TRUE CHAD EDITORRRRRRRRR RAHHHHHHHH WHAT THE F___ IS AN IDE????????

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

      I'm not exactly sure what a skibidi rizzler is, but good for them I think.

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

      certified macaquedev moment

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

As a tester, I can confirm that problems have statements

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

clashes with lc biweekly

should I give cf div 2 or leetcode biweekly?

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

Hi I'm new to Codeforces and I'm trying to improve by reviewing code from past contests. However, I noticed that when I go to the past contests page, select a problem, and click on the accepted submission numbers, the source code isn't showing—it's marked as 'N/A' for all submissions. Is there something I'm missing, or are the codes generally kept private? Any tips on how I can view code submissions would be greatly appreciated!

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

this is a really good practice of keeping the photos of people preparing the contest, it gives good vibes + i personally feel that yes in today's AI world still there is human interaction which makes me happy.

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

    Yes, I agree. I think it's nice to see the faces behind the screens.

    → Reply
»
4 weeks ago, # |
  Vote: I like it -6 Vote: I do not like it

wait a minute, I thought global round was going to take place

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

As a tester, I've purchased this contest for kids' enjoyment.

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

First CF after AFO.

CSP rp++ (CSP: a very important contest for Chinese OIers, just ended 30min ago)

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

Guys you giving LeetCode Biweekly or, Codeforces Div 2? Imma confused :(

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

    Ofcourse Codeforces, Codeforces is like a lover, who gives you a lot of emotional pain, but still you want to be with her.

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

Enjoy the contest, enjoy the problem, don't care about the score ！！！

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

hopefully i become newbie after this round

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

myst-6 fasrsi baladi?

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

Is there gonna be a hacking phase?

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

Hopefully I can become Pupil this Round And also, Good Luck everybody!

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

    Sorry bro just rated you negative it happened by mistake

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

Good Index.

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

hope i become specialist after this round :)

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

why is contest registration closed before the start?

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

Oh, speedforces today!

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

Any hints for E1? I feel like the nimber for each pile should only be revolving around $$$\text{popcnt}(x_i)$$$, but I hardly came up with anything...

Wasting 40min thinking about E1 while I could have been coding D2 should be one of the worst tactical decisions I've ever made XD

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

so close to solve C but failed...

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

Oh! Because I wasn't familiar with discretization, I lost a lot of ratings in this round.꒰╬•᷅д•᷄╬꒱

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

How do you solve C ? I couldn't solve it no matter what

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

Alright, so how to count the number of ways to achieve the result in D2? Struggled for an hour and still didn't get past TL8 (all other ideas just WA-ed).

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

    Take the DP table used to solve D1 (one with states [elements removed][value of $$$k$$$]). In this table, I'm assuming you found the minimal cost for each state by doing the minimum of costs required when increasing $$$k$$$ by 1, and when removing a prefix, where removing the largest one doesn't hurt.

    When increasing $$$k$$$ by 1, the number of optimal options assuming you do that is obviously just the number of optimal options for the state with $$$k$$$ greater by $$$1$$$.

    However, when removing a prefix, it's possible that removing a smaller prefix would also lead to an optimal solution. However, what you can note is that as the number of removed elements increases, the minimal costs required to finish are non-increasing. So, what you can do is first find the optimal cost, then use binary search to find the smallest prefix you can remove if you want to achieve that cost, and then calculate the sum of numbers of options for each prefix between the largest one with this cost and the smallest one with this cost (doable with suffix sums).

    Now, just compare the minimal costs obtained by increasing $$$k$$$ and by removing a prefix, if they're unequal, take the smaller one and the number of options for that operations, and if they're equal, take that cost and the sum of numbers of options for both of these operations.

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

How do you do C? I tried a graph solution but it was too slow.

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

    288149235 its not too slow tho

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

      288172503 see this why this gave me memory limit exceeded maybe because i used n in the nodes values?

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

      i wrote the same thing graph solution with unordered_map and got TLE after the contest does anyone know why? 288157167

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

        unordered_map has worse time complexities when comparing the worst case with normal maps , as there are hash collisions. So use maps instead

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

    well you can see that its a directed acyclic graph, so we dont actually have to store the indices or whatever, but just store the edges, and then you can go over all the edges in decreasing order of starting node, and store whether you visited an index in a set

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

      Deleted.

      (bcz it's just bfs/dfs on DAG with a map to check visited. I'm bad)

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

i got so confused on B, worst performance in a while. i found C pretty cool, and D1 seems doable, but i just wasted too much time on B. nice round

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

    I hate problems like B :(

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

    I think B was kinda tricky. I just brute forced my way through the following code. It worked but the code was a mess.

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

hints for D1??

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

How to solve A? Really do not understand why my solution was wrong.

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

Awesome B. Cost me 1 hrs + 3 WAs. That B is fucking hard, C is much easier. I think D1 is easier than B, but I have no enough time to solve it.

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

    Was your solution $$$O(n^2)$$$ (which passes, and IMO isn't hard to do), or something better (which probably is much harder than C)?

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

      My sol is O(n^2). But I just can't get the idea during most of the time of the contest.

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

wtf was b's solution? I know im sleep deprived, but im felling dumb af

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

    Say x is at index i then all the elements after index should be smaller than x. And for all the elements before index i, we only care about the elements before the maximum element upto index i, we will need to remove all those.

    288132226

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

      idk if I understand it well, but thats basicly what I did I kept searching for the max element on the vector, then I removed all the elements from the right of it

      Then i searched again for the max element up to index of the last max and on and on

      Then my answer was the number of max elements — the max element between the max elements it passed only test 1

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

        alright so lets take an example

        3 6 9 4 2 5 2

        say i am checking for index, i = 5 (1 based indexing), so the idea is to make both the right side (i>5) and left side (i<5) suitable but i handled that sepertaely

        for the right side, so the no of elements greater a[j] > a[i] such that j>i is simply 1, i.e., only 5( for j =6)

        for the left side, the ideal way is to remove all the elements before the maximum upto i = 5. so the maximum upto i = 5 is 9 and no of elements before it is 2.

        so total = 1 + 2 = 3, so if i had to make i = 5 as sort of the "center" of my arrangement then i need to remove 3 elemnts

        Now i will run this algo for all i from 0 to n and keep on taking the min for it

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

    Since n is small, you can count for every index i, number of a[j]>a[i] such that j>i by brute force.

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

      what u do with that number then ?

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

        index with minimum count will be answer. For eg. a=[3 6 4 9 2 5 2] here cnt represent number of a[j]>a[i] such that j>i cnt=[4,1,2,0,1,0,0] now return min(i+cnt[i])

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

    brute force the following for each i and pick the minimum:

    i + # elements a[j] (j > i) such that a[j] > a[i]

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

I printed lots of pairs $$$(n,k)$$$ on problem E1 and try to guess answer, it takes me 2 hours, just for 1000 points?

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

As a newbie, I am just never able to solve B (crying emojis)

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

    Don't cry for things out of control, you can start with some easier problems or exercise thinking skills. It's unnecessary to worry about how many problems you have solved but how many skills you have learnt.

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

Problems A, B and C were pretty good, but D1 is too easy. It is a really standard DP problem. Also speedforces.

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

All dp? Solved B, C, D1 with dp.

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

    can you explain d1 approach?

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

      $$$ dp_{i, j} = $$$ minimum cost to remove the prefix of $$$a$$$ up to $$$i$$$ with $$$k$$$ at $$$j$$$.

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

      dp[ind][cur_k] => Minimum cost for the subarray a[ind:n] with current k value = cur_k

      I have used prefix_sum + binary search to get the maximum prefix length we can discard from a[ind:n].

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

    C is dp? I used sets to solve it

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

first time i got 3 pretest accepted on a div2. hoping that i can achieve 1200+

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

How to solve E1? My code is timing out when computing the SG function. Can someone help me?

#include <bits/stdc++.h>
 
#define int long long
 
constexpr int N = 1e5 + 6;
 
int mex(std::set<int> &s) {
  int m = 0;
  while (s.find(m) != s.end()) ++m;
  return m;
}
 
std::map<std::pair<int, int>, int> mp;
 
int SG(int x, int a) {
  if (x == 0) return 0;
  if (a >= x) return __builtin_popcount(x);
  if (mp.count({x, a})) return mp[{x, a}];
  std::set<int> s;
  int d = x;
  while (d > 0) {
    if (d <= a) {
        s.insert(SG(x - d, a));
    }
    d = (d - 1) & x;
  }
  return mp[{x, a}] = mex(s);
}
 
void solve() {
  int n;
  std::cin >> n;
  std::vector<int> a(n + 1, 0), x(n + 1, 0);
  for (int i = 1; i <= n; ++i) std::cin >> a[i];
  for (int i = 1; i <= n; ++i) std::cin >> x[i];
  int ans = 0;
  for (int i = 1; i <= n; ++i) ans ^= SG(x[i], a[i]);
  std::cout << (ans ? "Alice" : "Bob") << "\n";
}
 
int32_t main() {
  std::ios::sync_with_stdio(0);
  std::cin.tie(0), std::cout.tie(0);
 
  int t;
  std::cin >> t;
  // t = 1;
 
  while (t--) {
    solve();
  }
 
  return 0;
}
→ Reply
»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I don't understand why B's constraints are low when a non-n^2 solution is not hard to do and fits a div2 B. (Yes, I am annoyed that I didn't look at the constraints, which is totally my fault).

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

    I think that a better solution than $$$O(n^2)$$$ is a bit too hard for div2B (some people are already saying it was too hard). Maybe having an easy version where $$$O(n^2)$$$ passes and a hard version where it doesn't would work better?

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

    What is the 'fits a div2 B' solution? I see you used pbds to find the order and that is definitely not D2B level. It's more like a D2D.

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

      Well, finding the number of greater elements to the right is too standard to be a D2D, and yes it will be a slightly harder B but will make it not a speedforces at least. And making it a B1B2 is a great idea as the other reply mentioned. (And after considering now, yes the constraints is just alright I was just salty I didn't focus on it)

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

        It adds almost nothing to the problem other than having to know a very standard technique. We don't want a D2B-level idea problem to require a D2D-level data structure, just because a solution for the harder version using such a structure exists.

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

          To be fair, a lot of data structures other than pbds can also solve this in $$$O(nlog(n))$$$ (there are at least $$$2$$$ different segment tree solutions, for example), but I still definitely agree that having this as just div2B would be too hard, and my easy/hard version idea probably isn't actually that great either.

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

            It can be done in $$$O(n log(n)$$$ with sorting and 2 maps.

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

    If the constraint is tighter, I think we could solve it by fenwick tree. do you think so?

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

couldn't solve B

I'm screwed

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

    You can fix $$$i$$$ as starting element of $$$a$$$ after deleting some elements then simply bruteforce the number of remaining elements after applying Stalin Sort on this $$$a$$$.

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

For B I was trying to get traverse till the first decreasing slope (i,e. traverse till A[i] < A[i+1]). And then my peak would be A[i]. Any number greater than this peak also is to be deleted. This failed on pretest(3). So I would love new ideas ?

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

    Since n is small, you can count for every index i, number of a[j]>a[i] for j>i.

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

288174453 When I submit D2 at the last minute:

Passed pretests 1-7 ... :)

MLE in 8 :((

Lesson: use vectors to handle DP with uncertain array lengths ; )

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

    UPD: got AC after only change map to vector, if ML is 512mb map solution will also pass ;)

    288182896

    → Reply
»
4 weeks ago, # |
← Rev. 5   Vote: I like it 0 Vote: I do not like it

How to solve D1

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

    You can solve it using DP + Prefix sum, it will run in either $$$O(N * M * log_2(N))$$$ or $$$O(N * M)$$$.

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

I am so stupid, I forgot to return my memoized solution for C so kept getting TLE but didn't realize until after contest ended. I think I'm just not cut out for this.

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

Can someone tell me what's wrong with my D1?

Solved it. nevermind

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

D2 is a good problem.

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

    I agree, even though I struggled hard to debug it (eventually managed; it's also the first time I managed to make a debugger throw an exception, and it was completely my fault).

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

jiangly ORZ :0

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

Why $$$O(n^2)$$$ in B, eventhough it's easy to solve in $$$O(n)$$$ ?

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

    Yup, using pbds or Fenwick tree with coordinate compression in n*log(n) is not ok for div2.B to have such semi-advanced data structures. The core idea is ok for div2.B tho.

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

    How? $$$O(nlog(n))$$$ is doable, but what's an $$$O(n)$$$ solution?

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

I finally solved C by sorting the edges, but I wonder why the bfs solution got a TLE?

288136031

I used discretization to avoid map<ll, vector<ll>>, but then I got 3 MLE :(

288160146

Can anyone help me with the time complexity or the memory use of my solution?

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

    Before pushing y, you should check if it is already visited . If not,then push y into the queue and mark it as visited. You can use a set to do so

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

    is there any reason to avoid map<ll, vector>

    I have used it and got it accepted

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

    you forgot the "visited part" about bfs 288178077 heres mine with map bfs

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

Could someone please explain their D2 approach?

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

Did anyone solve C with DP? Please share your approach!

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

Very inspiring contest! I love it!

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

I'm like a little baby,don't konw d1 why？

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

dpforces

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

Thank you very much for the contest.

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

ahhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhh i passed c with map but got tle with umap ahhhhhhhhhhhhhhhhhhh

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

Nice shirts :)

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

Interesting problems!

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

Took way too much time for B and C. Good contest nevertheless!

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

For Problem C, I submitted the same code in contest, it got TLE'd. And when I submitted the same solution in practice, it got accepted.

Can anyone explain the reason behind it? Thank you!!

TLE submission

Accepted submission

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

    Looks like a c++20 vs c++17 issue.

    idk why this happens tbh tho

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

    because of c++20, It happened to me several times.

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

    Somebody submitted a hack in the last 4 seconds of the contest to TLE an unordered_map solution. It seems that maybe the hashing function works differently in different C++ versions, so when you changed the version it passed.

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

    unordered_map + different c++ versions + poor (not poor exactly) test cases

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

Solved A & B in 8 minutes but couldn't do C because I forgot to keep track of visited for my BFS solution :(

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

I reached blue with this one :D

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

I just want to understand, how my rating dropped if I solved 1 problem (A) say (+100pts) and then gave 1 wrong submission on B (-50pts). I got -44 delta. So I'll be glad if someone explains the drop.

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

    Rating change is only dependent on your ranking in the contest, not on number of points gained. More info on how the rating system works is here.

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

I hate DP

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

Problem C, Most of the codes have used dfs, I used bfs and got MLE.

I used the same adjacency list as others using map. The map will contain atmost 3e5 elements, The queue can have a maximum of 3e5 elements at a time. So that shouldn't give MLE. What am I missing here?

Submission Link : https://codeforces.me/contest/2027/submission/288164685

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

    I also got MLE on pretest 5 while using a queue . Then I switched to a priority_queue and removed all occurrences of the currently visited index from the map so that I don't revisit same index twice, which led me to get an AC. Hope it helps.

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

      But wouldn't keeping a visited array also make sure that you don't revisit the same index twice? I used a visited array and got MLE.

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

        Actually i just saw my code, and I was implementing BFS wrong (I was updating the vis array outside the for loop, so duplicates were coming). I figured it while typing the above comment.

        Thanks to you I figured it.

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

    You're setting vis[ind] = 1 only when it's popped from the queue, so your queue might contain something like $$$\mathcal{O}(2^n)$$$ numbers on that test since you're adding a lot of duplicates. Maybe if you move that line to where you're pushing into the queue, then it will pass.

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

      Yeah I did just that and it did pass. Thanks a lot for the help!

      Can't believe I made such a rookie mistake.

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

Overall very nice round!

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

Tomorrow morning КГБ knocks on the door of the author of problem B (Stalin Sort)...

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

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

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

Took me forever to solve problem B.

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

I liked the contest, (luckily) there wasn't much diff for me between $$$D1$$$ & $$$D2$$$.
What is the chance of getting $$$+3$$$ or more after rating roll back?

→ Reply
»
4 weeks ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

Tourist is your father, the GOAT of cp

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

I was thinking of solving C using a tree, but I couldn't figure out how to implement it.

UPD: nvm the editorial is out

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

please rename title of contest as "Educational DP Contest — AtCoder"

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

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

    Boss: "umm.. What happened to the user records in the database?"

    Me: "Deleted"

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

Wait who even consensually name themself nathan_higgs like this name is weird man

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

How to do B if the bounds were more strict?

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

I would like to report suspected cases of cheating in Codeforces Round 982 (Div. 2). I have identified multiple pairs of submissions with identical or nearly identical solutions. Here are the relevant submission links:

Pair 1: https://codeforces.me/contest/2027/submission/288161794 https://codeforces.me/contest/2027/submission/288145385

Pair 2: https://codeforces.me/contest/2027/submission/288152323 https://codeforces.me/contest/2027/submission/288137323

Pair 3: https://codeforces.me/contest/2027/submission/288163896 https://codeforces.me/contest/2027/submission/288155729

Each pair of submissions shows a high degree of similarity.

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

Finally, I'm Pupil!!

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

288252108 This is the accepted solution of mine.

288248589 In this, I got mle, and also time taken was high.

The only difference I made was just how I was using the visited set while doing bfs so can someone explain more about what exactly happened with me?

UPD: Got it!

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

Why would my java8 code run error through java21, and just a depth-first search shows stack overflow

→ Reply
»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Clarification Regarding Solution 288171719(https://codeforces.me/contest/2027/submission/288171719) Code... ~~~~~

include <bits/stdc++.h>

using namespace std;

define int long long int

define pb push_back

define input(arr,n) for(int i=0;i<n;i++){cin>>arr[i];}

define MOD 1e9+7

signed main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

int t; cin>>t; while(t--){ int n; cin>>n; vector<pair<int,int>>a(n+1); for(int i=1;i<=n;i++){ cin>>a[i].first; a[i].first+=i-1; a[i].second=i-1; } a[1].first=0; sort(a.begin(), a.end()); map<int,int>dp; dp[n]=1; for(int i=2;i<=n;i++){ if (dp[a[i].first]) dp[a[i].first+a[i].second]=1; } int ans=0;
for(auto it:dp){ if(it.second){ ans=it.first; } }
cout<<ans<<endl; } return 0; } ~~~~~ Dear Codeforces team,

I recently received a notification about a significant similarity between my solution (ID: 288171719) for problem 2027C and several others. I would like to clarify the circumstances and defend the originality of my work.

Explanation of My Solution

  1. Common Template: I have been using a specific template for Codeforces problems that includes optimizations like #define int long long int, ios_base::sync_with_stdio(false), and other macros for at least two months. This template is a standard part of my competitive programming workflow and might have contributed to structural similarities with other submissions.
  1. Standard DP Approach: The dynamic programming (DP) logic I used in my solution is a well-known and widely applied technique in data structures and algorithms, especially for problems that require efficient state management. This approach is common, and many participants are likely to arrive at similar implementations, as the use of dp in such problems is almost inevitable.
  1. Small Code Size: The solution is relatively short, and for problems like these, there are often limited ways to structure the code efficiently. This constraint naturally increases the likelihood of overlap between different participants' implementations.
  1. Use of Online Compiler: I used an online compiler, GDB, during the contest for convenience. While I ensured my code remained private, there is always a risk of unintentional exposure, though I have no evidence of such an incident occurring.

Request for Consideration

I assure you that I have always strived to compete fairly and in accordance with Codeforces' rules. I did not share my code or collaborate with others. If further clarification or investigation is needed, I am ready to cooperate.

Thank you for considering my explanation.

→ Reply