Educational Codeforces Round 143 [Rated for Div. 2]
By awoo, history, 21 month(s) ago, translation, In English

Hello Codeforces!

On Feb/16/2023 17:35 (Moscow time) Educational Codeforces Round 143 (Rated for Div. 2) will start.

Series of Educational Rounds continue being held as Harbour.Space University initiative! You can read the details about the cooperation between Harbour.Space University and Codeforces in the blog post.

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, Vladimir vovuh Petrov, Ivan BledDest Androsov, Maksim Neon Mescheryakov and me. Also, huge thanks to Mike MikeMirzayanov Mirzayanov for great systems Polygon and Codeforces.

Good luck to all the participants!

Our friends at Harbour.Space also have a message for you:

Hello Codeforces!

We look forward to seeing Mike Mirzayanov and Nikolay Kalinin again at our Barcelona campus when they teach Advanced Algorithms and Data Structures.

In this course, students focus on key and in-depth algorithms and data structures that form a modern computer specialist’s toolkit.

We are always excited to see Codeforces participants as our students at Harbour.Space! Once again we are giving a special discount for the single course participation in Barcelona, Spain (travel costs and accommodation are not included).

Sign Up Here→
Harbour.Space
APPRENTICESHIP OPPORTUNITY IN BARCELONA
NOVENTIQ x HARBOUR.SPACE

50% of the spots have been filled already, hurry up not to miss your opportunity to get selected!

At Harbour.Space University, we continue providing work-study opportunities; in this case, we offer motivated Data Scientists the opportunity to work and study in Barcelona in partnership with Noventiq, the leading global solutions and services provider in digital transformation and cybersecurity.

We are looking to distribute scholarships for intensive study programmes at the highest level for eligible candidates that will join our journey.

Candidates will be working on the following tasks:

  • Invent and implement approaches to solving problems of computer vision and machine learning, form requirements together with the team;
  • Plan experiments, train models, evaluate their quality and embed them in pipelines;
  • Work with data, the formation of technical requirements for markup;
  • Register the results of training runs of models and track the dynamics of their performance;
  • Write algorithms for pre and post-processing of images and videos, the logic of scenarios for processing media data;
  • Conduct research in the field of Computer Vision: classification, detection, segmentation;
  • Engage in the optimization of neural networks: distillation, quantization, pruning;
  • Prepare models for production.
  • Carry out the development of custom algorithms and modules for our video analytics platform

All successful applicants will be eligible for a 100% Tuition Fee Scholarship (22.900 €/year) provided by Noventiq company for the Data Science programme.

CANDIDATE’S COMMITMENT

Study Commitment: 3 hours/day You will complete 15 modules (each three weeks long) in one year. The daily class workload is 3 hours, plus homework to complete in your own time.

Work Commitment: 6 hours/day Immerse yourself in the professional world during your apprenticeship. You’ll learn from the best and get to apply your newly acquired knowledge in the field from day one.

University requirements

  • Bachelor's degree in the field of Mathematics, Statistics, Data Science, Computer Science or similar
  • English proficiency

Work requirements

  • Excellent knowledge and experience in using Python, as well as TensorFlow/PyTorch;
  • Experience in implementing Deep Learning models for commercial projects;
  • Experience in solving real problems in the field of Computer Vision
  • Experience with Linux OS, Git, Docker;
  • Understand the principles of operation of current popular architectures of neural networks;
  • Possession of the culture of conducting experiments, you know about reproducibility and logging, you can objectively assess the quality of the model;
  • Spanish language proficiency;
Apply Here Now→

UPD: Editorial is out

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

Comments Comments (152)
| Write comment?
»
21 month(s) ago, # |
  Vote: I like it +17 Vote: I do not like it

Like it! Educational rounds are always nice and educational!

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +62 Vote: I do not like it

5082-jpg

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +59 Vote: I do not like it

Humans are a strange species... We look for problems to solve them.

→ Reply
»
21 month(s) ago, # |
← Rev. 3   Vote: I like it -10 Vote: I do not like it

I wish good luck everyone and post meme to make you a bit happier)

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +2 Vote: I do not like it

Hope to become Pupil in this Round

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +3 Vote: I do not like it

In education round, we will have a great education!!!

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +4 Vote: I do not like it

Wish interesting new problems.

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +2 Vote: I do not like it

Hope to become specialist in this round :)

→ Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

As an inactive account, hope this round is educational.

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +6 Vote: I do not like it

Missing the picture of Harbour.Space University!

→ Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

I need an extension that predicts the rate of change of the rate during the round

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +15 Vote: I do not like it

C was an insightful problem for me. I thought at first I would need some complicated range query data structure but then I remembered being amazed that 1791F - Range Update Point Query could be solved with just a std::set. So I drew inspiration from that problem and decided to simplify my ideas and came up with a neat priority queue solution.

void solve(){
    int n;
    cin >> n;
    vector<long long> v(n, 0);
    for(int i = 0; i < n; i++) cin >> v[i];
    vector<long long> t(n, 0);
    for(int i = 0; i < n; i++) cin >> t[i];
    vector<long long> ans;
    long long sum = 0;
    priority_queue<long long, vector<long long>, greater<long long>> pq;
    for(int i = 0; i < n; i++){
        long long len = pq.size();
        long long res = t[i]*(len);
        res += min(t[i], v[i]);
        while(pq.size() && pq.top() < sum+t[i]) {
            res -= min(t[i], sum+t[i]-pq.top());
            pq.pop();
        }
        ans.push_back(res);
        pq.push(v[i]+sum);
        sum += t[i];
    }
    for(auto i : ans) cout << i << " "; cout << endl;
}
→ Reply
  • »
    »
    21 month(s) ago, # ^ |
    ← Rev. 2   Vote: I like it +19 Vote: I do not like it

    C is doable with just 1 sort + array iteration.

    → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      can you elaborate little more how we can do C

      → Reply
      • »
        »
        »
        »
        21 month(s) ago, # ^ |
          Vote: I like it +10 Vote: I do not like it

        Taster 1 only drinks tea 1. But we can add the capacity of taster 1 to teas 2...n, and pretend that taster 1 drinks all teas. This leaves the same amount of teas remaining after taster 1 drinks. At the end, we must remember to subtract (N — 1) * (capacity of taster 1) from the answer for taster 1.

        Similarly, we can add the capacity of taster 2 to teas 3...n, and pretend that taster 2 also drinks all teas. Doing this for all tasters, all tasters drink all teas, and now the order of the teas doesn’t matter.

        We can then sort all modified tea amounts, and the solution is not so far from here.

        → Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    Pretty cool, thanks for sharing! An alternative solution that I implemented uses binary search on prefix sums to find the rightmost drinker that can be satisfied and uses the $$$+1$$$ on left and $$$-1$$$ on right boundary trick. Solution

    → Reply
»
21 month(s) ago, # |
  Vote: I like it +1 Vote: I do not like it

Segment tree beats in problem C 💘💘💘

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +7 Vote: I do not like it

    LOL No just basic binary search

    → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
      ← Rev. 2   Vote: I like it +16 Vote: I do not like it

      LOL Yes just segment tree beats

      int main() {
    int tt; cin >> tt;
    while (tt--) {
        int n; cin >> n;
        vector<long long> x(n), y(n);
        for (auto& c : x) cin >> c;
        for (auto& c : y) cin >> c;
        segtree<long long> st(x);
        for (int i = 0; i < n; ++i) {
            auto old = st.segment_sum(0, n - 1);
            st.segment_add(0, i, -y[i]);
            st.segment_max_equal(0, n - 1, 0);
            cout << old - st.segment_sum(0, n - 1) << ' ';
        }
        cout << '\n';
    }
}
      → Reply
      • »
        »
        »
        »
        21 month(s) ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Isn't it $$$O(n log^3 n)$$$ ? I thought It could not accept because of large $$$n$$$ constraint

        → Reply
      • »
        »
        »
        »
        21 month(s) ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Can u please elaborate your functions?? Like what does segment_max_equal does?

        → Reply
        • »
          »
          »
          »
          »
          21 month(s) ago, # ^ |
          ← Rev. 3   Vote: I like it +1 Vote: I do not like it

          It assigns $$$max(A_i, 0)$$$ to each $$$A_i$$$ in range $$$l \leq i \leq r$$$ (in this case all of $$$A_i$$$ 's)

          The logic behind his solution is that for taster $$$i$$$ you can decrease $$$b_i$$$ from all of [0, i] remaining drinks and then make negative drinks zero. after that, difference of old sum [0, i] and new sum [0, i] would be amount of drink taster $$$i$$$ drank in the process.

          → Reply
          • »
            »
            »
            »
            »
            »
            21 month(s) ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Oh, nice! I got it now, thank you!

            → Reply
          • »
            »
            »
            »
            »
            »
            21 month(s) ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Hey, I know you didn't write the code in question but I just cant seem to understand how he sets the max(Ai, 0) for every range in O(logN) time?

            I understand the first function set.segment_add(), it can be implemented with lazy propagation, but the second one, st.segment_max_equal(), I can't understand at all.

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              21 month(s) ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              Actually I don't know how max_equal operation works and I just use it as a black box. but if you are intended to get how it works I guess this post could be helpful.

              Here is accepted code of this approach: 194087474 (segment tree template is not mine and I took it from wery0 submissions. you can look at his original submission for the problem too)

              → Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    If u have code it up C problem using Segment Tree, then Can u please share the link of your submission

    → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I used range update and point query which could've been done with difference arrays easily but I coded out a lazy tree. submission

      → Reply
»
21 month(s) ago, # |
  Vote: I like it +1 Vote: I do not like it

So many submissions on D ;(

→ Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

How to Solve D?

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    I think the idea is each group needs to be colored either BRB or RBR inorder to extract the maximum 2 edges from each group and we cannot extract more than that from each group. Then we need exactly half of the group to have BRB and half to have RBR inorder to have n/2 vertices of each colors . For each group we can calculate the number of ways to color BRB so that we get max 2 edges and same for RBR

    I could not figure out how to implement the part where we select exactly n/2 groups to have BRB and n/2 to have RBR in the given constraints

    → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      its simple permutation and cobination qestion : just calculate nC(n/2): n!/((n/2)!*(n/2)!) i.e permutation of n objects out of which (n/2) are alike of 1st kind and (n/2) are alike of 2nd kind.

      → Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    For each triangle find # of ways to choose two edges to get the max value, multiply those numbers and finally multiply (n / 3 choose n / 6).

    → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Hmm.. I thought that n/3 choose n/6 is over than max of long long int. So I had the problem to multiply n/3 choose n/6 at max value of edge. How can I solve this problem?

      → Reply
      • »
        »
        »
        »
        21 month(s) ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        that's why in the qestion it is mentioned to use % with that number 998.... whatever it was.

        → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      got confused in such a simple thing in contest ;(((

      → Reply
      • »
        »
        »
        »
        21 month(s) ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        happens to the best of us bro.

        → Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +7 Vote: I do not like it

    Some observations:

    • It's never a good idea to color all three vertices in a triangle with the same color, since you would always get a higher total weight by coloring one of them differently from the others. Therefore, each triangle should be either 2 blue, 1 red or 2 red, 1 blue.
    • Since exactly half of the vertices must be blue and exactly half of the vertices must be red, this means that exactly half of them will 2-blue-1-red (I call them blue-heavy) and exactly half of them will be 2-red-1-blue (I call them red-heavy).
    • With $$$n/3$$$ triangles, there are exactly $$$n/3 \choose n/6$$$ ways to assign blue- and red-heaviness.
    • Now, given a triangle, we know 2 should be of the same color, but which two? Well, the edge between these two is the only edge from this triangle that will NOT contribute to the weight. So we should choose the edge with minimum weight.
    • However, there might be 1, 2 or 3 edges with minimum weight in the same triangle. This number is also the number of ways to color the triangle after you already decided if it's blue-heavy or red-heavy.

    Basically, if $$$f(\Delta)$$$ is equal to the number of copies of the minimum-weight edge in the triangle $$$\Delta$$$, then the required answer is $$${n/3 \choose n/6} \prod f(\Delta_i)$$$.

    My submission: 193883975. I first computed $$${n/3 \choose n/6}$$$ (by accumulating a factorial vector) and then checked each triangle one by one, sorting the three edges and counting how many copies of the minimum edge there is.

    → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      I have a Doubt .. what about cases with same color .. RRR [ This will give 0 Result I know] .. But in calculation .... we are taking only .. [Half --> RBB | Other-Half --> BBR ]
      can't understand what about RRR or BBB ... why are we not taking those cases ..

      → Reply
      • »
        »
        »
        »
        21 month(s) ago, # ^ |
        ← Rev. 2   Vote: I like it +5 Vote: I do not like it

        Each triangle can contribute at most one edge weight to the answer. Then RRR or BBB is impossible since in this case we can't maximize the answer. (if we change a RRB to RRR, where can we get the lost weight back?)

        → Reply
      • »
        »
        »
        »
        21 month(s) ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        If you have a $$$RRR$$$, then you must have a $$$BBB$$$ or $$$BBR$$$ somewhere.

        If you have $$$BBB$$$, then you can convert $$$(RRR,BBB)$$$ into $$$(RRB, BBR)$$$.

        If you have $$$BBR$$$, then you can convert $$$(RRR,BBR)$$$ into $$$(RRB,RRB)$$$.

        In either of the cases, the answer becomes "better".

        → Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

What's combinatorics behind D? How do you calculate how many different combinations you can have from the 3 types of triangles after counting their amount?

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    solved using only binary search and range updation where we perform update queries first and in the end calculate the ans

    → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Dont understand. I think you meant to reply to someone asking help about C.

      → Reply
»
21 month(s) ago, # |
  Vote: I like it +15 Vote: I do not like it

anyone else solved C using binary search + difference array?

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
    ← Rev. 4   Vote: I like it 0 Vote: I do not like it

    I have solved it using Binary search + dif array. The basic idea behind was that I calculated for every tea how many testers will be able to test the tea, for this I just calculated the prefix array of tea, each tester can have at max and then simply iterated the array by finding upper bound for each element in that prefix array.

    This is my submission 193883206

    → Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    me

    → Reply
»
21 month(s) ago, # |
  Vote: I like it +19 Vote: I do not like it

To some people E may be standard and obvious, but the thought process is fun, so I think it's a cool problem.

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
    ← Rev. 2   Vote: I like it +11 Vote: I do not like it

    The problem would become equivalent to this:

    we have an array in each operation you can decrease an element by one. Whats the minimum number of operations needed to make the array increasing/decreasing the array?

    Am I right?

    How do you solve this?

    → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it +18 Vote: I do not like it

      Not really, it's to make the array strictly increasing first and then strictly decrease (except 0).

      → Reply
      • »
        »
        »
        »
        21 month(s) ago, # ^ |
        ← Rev. 2   Vote: I like it +8 Vote: I do not like it

        by sorting the array I mean making it increasing.

        having the number of operations needed for each prefix and suffix the answer would be sum of these two plus the value of the Ith element

        btw whats the solution

        → Reply
        • »
          »
          »
          »
          »
          21 month(s) ago, # ^ |
          ← Rev. 2   Vote: I like it +28 Vote: I do not like it

          For each i calculate the min # of operations to make a[1..i] increasing. This can be done with a monotonic stack:

          For each i, find the biggest j < i such that $$$a_j - j \le a_i - i$$$, then $$$a_{j+1,\dots,i}$$$ should be set to $$$\dots, a_i - 2, a_i - 1, a_i$$$, let that cost be x, then $$$pre_i = pre_j + x$$$.

          Then calculate the similar thing for suffix, the answer is $$$\min(pre_i + suf_i + a_i)$$$

          → Reply
          • »
            »
            »
            »
            »
            »
            21 month(s) ago, # ^ |
              Vote: I like it +19 Vote: I do not like it

            yes, my problem is that I dont know how to calculate pre[i] and suf[i].

            → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
      ← Rev. 2   Vote: I like it +2 Vote: I do not like it

      I thing the problem is like.

      we have an array in each operation you can decrease an element by one. Whats the minimum number of operations to make it strcitly increasing then stricty decreasing?

      I just don't know how to do that.

      Maybe it's standard

      → Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    Can you give some hints to solve E ?

    → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      HInt
      → Reply
      • »
        »
        »
        »
        21 month(s) ago, # ^ |
          Vote: I like it +12 Vote: I do not like it

        I don't think, the difficulty of understanding it is comparable with the whole solution)

        → Reply
»
21 month(s) ago, # |
  Vote: I like it +14 Vote: I do not like it

For me D felt much easier to solve and took few minutes to think. Though i finally found an implementation flaw which was getting me tle in c and got accepted in the end with 5 mins remaining :)

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
    ← Rev. 7   Vote: I like it 0 Vote: I do not like it

    I miss D by 1 min :(. Due to PC for case 2 in which two values of edges are the same.

    → Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone please look at my Segment tree solution for problem C? And tell what's the problem with rangeupdate?

https://mirror.codeforces.com/contest/1795/submission/193906545

I think my template screwed up my really good rank.

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    How did you plan to use a segment tree with constraints <= 1e9?

    → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      It's giving the wrong answer at pretest 1.

      → Reply
      • »
        »
        »
        »
        21 month(s) ago, # ^ |
          Vote: I like it +12 Vote: I do not like it

        Pretest 1 is the sample.Having wrong answer on pretest 1 indicates that your program failed to pass the sample.

        → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      Well, it is possible with "implicit key" (I don't actually know, how it is called).

      The idea: you create the node, when you first need it. Every query creates up to $$$O(\log{n})$$$ nodes. So the size of tree is $$$O(q \log{n})$$$ and the total time is $$$O(q \log{n} \log{q})$$$. However, there can be problem with time limit.

      → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I iterated over each tea and checked till which person would the tea last until it's completed using binary search on prefix sum of persons capacities, all these persons in between will drink tea with there full capacities and last person will drink remaining, so i just stored and updated multiples of their capacities in segment tree and maintained an additional array that stores remaining tea that was drank by last person.

      Hopefully it wont get hacked

      → Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +22 Vote: I do not like it

    Problem C and 923B - Producing Snow are same.

    → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      Yes, it is. I copied my solution from 923B, slightly modified and submitted to this problem during the contest. Submission

      → Reply
      • »
        »
        »
        »
        21 month(s) ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        How would you remember that's i done before that , if you able to remember then then how to manage to find that problem name

        → Reply
        • »
          »
          »
          »
          »
          21 month(s) ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          I solved 923B yesterday morning before the contest during my work on reviewing all of the solved problems during 5 years if I can solve them (or just to catch main idea) faster or not, is there any progress or degradation. So, I just was lucky to read and solve this problem at the same day.

          → Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +12 Vote: I do not like it

    Most of div2C problems do not require segment trees.

    → Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I used segment tree and passed, although it's really dirty compared with others' solutions. You may check my code here: 193914285

    → Reply
»
21 month(s) ago, # |
  Vote: I like it +56 Vote: I do not like it

Did anyone else find D to be much easier than C?

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    by idea no, by implementation yes

    → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it +19 Vote: I do not like it

      the idea for D came to me almost instantly, however I had no idea how to optimize C lol

      → Reply
      • »
        »
        »
        »
        21 month(s) ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        to be honest D idea easy but you need more themes, and knowledge about MODs, factorials, when in C you need prefix sums and binary search

        → Reply
        • »
          »
          »
          »
          »
          21 month(s) ago, # ^ |
          ← Rev. 2   Vote: I like it 0 Vote: I do not like it

          Yeah need to look those up. I could only come up to a O(n2) solution for C with prefix sums

          → Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I thought D looked easier than C, but I only had 8 minutes to read it :(

    → Reply
»
21 month(s) ago, # |
  Vote: I like it +1 Vote: I do not like it

What would be the expected rating of E?

→ Reply
»
21 month(s) ago, # |
← Rev. 2   Vote: I like it +2 Vote: I do not like it

A: Check adjacent elements in the string u=s+reverse(t), any possible pair of towers is a pair of prefix and its corresponding suffix of u. If there's <=1 pair of adjacent same letters, we can cut the string from that position, otherwise there will be adjacent same letters in any pair of prefix and suffix.

B: Check if there's a range [l1, r1] with l1==k, and a range [l2, r2] with r2==k (range [k, k] will satisfy both conditions).

C: For each sort of tea, use binary search to find how many tasters it can serve. They will form a subsegment of [1, n], and for each segment [l, r], we do diff[l]++, diff[r+1]-- and the prefix sum of diff will be the amount of tea each taster can drink. Also we need to calculate the difference of a[i] and b_sum[r]-b_sum[l-1] (where r is the maximum r that b_sum[r]-b_sum[l-1]<=a[i]), and subtract it from ans[r].

D: It's always better to choose n/6 triangles to color it by RRB, and other n/6 triangles colored BBR. And for each triangle with weight w1, w2, w3, we check how many values of {w1+w2, w1+w3, w2+w3} is equal to the maximum of them, let this number be cnt[i], then the answer is C(n/3,n/6)*product(cnt[i]). (IMO D is easier than C)

E: We need to choose an index k, and let h[1...k] become increasing (strictly-increasing for non-zero elements), and h[k...n] become decreasing (strictly-decreasing for non-zero elements). Let b[i]=h[i]+i, c[i]=h[i]-i. Then for j>=k, we need to decrease b[j] to max(j, min(i=k...j)(b[i])), and for j<=k, we need to decrease c[j] to max(-j, min(i=j...k)(c[i])), and we can calculate ans[k] from prefix-sum of c[j] and suffix-sum of b[j]. We can iterate k from 1 to n and update prefix-sums, then iterate from n to 1 and update suffix-sums.

So how to implement it?
→ Reply
»
21 month(s) ago, # |
  Vote: I like it +10 Vote: I do not like it

Makkapakka orz

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +7 Vote: I do not like it

C's statement was difficult to understand

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +77 Vote: I do not like it

Screencast with commentary

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +13 Vote: I do not like it

Hi guys! you can check the video editorials for todays contest here

problem C: https://youtu.be/zHyyBxM7aiQ

problem D: https://youtu.be/EOmEXRpml6k

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    Great work bro try to be regular Upload editorial for all contents

    → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it +4 Vote: I do not like it

      yeah bro, I have been uploading all editorials regularly :)

      → Reply
»
21 month(s) ago, # |
  Vote: I like it +3 Vote: I do not like it

good contest TBH, BUT actually why would you make B much easier that A, you are missing the point for problem A, at least for me :)

→ Reply
»
21 month(s) ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

Can someone explain why my solution 193899252 in contest for D gave wrong answer? It is something related to modulus

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    you're supposed to mention the link to your submission as well so that people could see it.

    → Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yes. $$$\frac{X}{Y} \mod M \ne \frac{X \mod M}{Y \mod M}$$$.

    E.g.: $$$X = M + 1$$$, $$$Y = 2$$$;

    $$$\frac{X}{Y} \mod M = \frac{M + 1}{2}$$$, but $$$\frac{X \mod M}{Y \mod M} = \frac{1}{2} = 0$$$

    You should use modular inverse to calculate answer

    → Reply
»
21 month(s) ago, # |
  Vote: I like it -51 Vote: I do not like it

Really Bullshit Contest! Problems B and C are sharing the same clasic idea — range addiction queries ! (alghout the limitation varies)
Also problem D is mush easy to be problem D div2, if you've passed 9th grade, you may simply solve it! You may guess what I'm saying, UNRATE PLZ!

→ Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

can anyone please tell me the time complexity of tourist's C CODE

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    $$$n$$$ inserts on a multiset and at most $$$n$$$ deletions : $$$nlog(n)$$$.

    → Reply
  • »
    »
    21 month(s) ago, # ^ |
    ← Rev. 2   Vote: I like it +1 Vote: I do not like it

    I also implemented with same idea.

    Suppose our multiset S contain let say m elements and we are processing index i , so we can consider all the elements which are smaller than b[i] and erase them from the set and keep the elements greater than it. Deleting the smaller elements wont allow them to participate in further iterations and thus causing atmost n deletions.

    Now all the elements greater than it are decremented in the same amount delta, so we don't need to perform decrement operation in that range, what we can do is keeping a variable delta for tracking the decrements

    Now when we process the next index i + 1, we are essentially comparing an element x in set by considering x — delta with b[i+1].

    Smaller elements such that x <= b[i+1] + delta are removed from the set as they eventually become 0 and positive elements remain with the effective delta being delta = delta + b[i].

    TC: nlog(n)

    → Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

can anyone tell what should have been the approach in the second question my approach was if k lies in the interval of atleast one segment print yes else no please help me where am i wrong ?

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    The issue is that it must be possible for $$$k$$$ to be in the highest number of intervals, with no ties allowed. For example, if there is only one interval, with range $$$[k - 1, k + 1]$$$, then regardless of whether you keep or remove it, the number of intervals with $$$k$$$ will always be equal to the number of intervals with $$$k - 1$$$ and also the number of intervals with $$$k + 1$$$.

    What you need to do is find some interval that includes $$$k$$$ but not $$$k - 1$$$ and also find some interval that includes $$$k$$$ but not $$$k + 1$$$. If you can find both (note that the interval $$$[k,k]$$$ already satisfies both), then the answer is YES. Otherwise, the answer is NO.

    → Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

When will be the next icpc registration start, Or any other major Google compitition dates to register please let me know

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +16 Vote: I do not like it

https://mirror.codeforces.com/contest/1795/submission/193901690

https://mirror.codeforces.com/contest/1795/submission/193902178

I found these two cheating

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +3 Vote: I do not like it

where to find a complete solution of a contest problem?

→ Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Can Anyone enlighten me with why my submission giving TLE.i just couldn't figure it.i think my solution time complexity is O(n^2) and it should be able to pass in 2 seconds for given n.Correct me if i'm wrong. https://mirror.codeforces.com/contest/1795/submission/193882619

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    O(n^2) is not fast enough. With n being 2*10^5 n^2 is 4*10^10 which is too much. You need an O(nlogn) solution here, you can read about it in other comments.

    → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it +6 Vote: I do not like it

      Thank you so much for the reply. I was thinking blindly till now.

      → Reply
  • »
    »
    21 month(s) ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    Your time complexity is 4 * (10 ^ 10) in the worst possible scenario. As far as i know C++ can process no more than 10 ^ 9 operations in 1 sec(in the best scenario).

    → Reply
»
21 month(s) ago, # |
  Vote: I like it +11 Vote: I do not like it

I made video Solutions for A-E.

→ Reply
»
21 month(s) ago, # |
← Rev. 4   Vote: I like it -56 Vote: I do not like it

Deleted

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +63 Vote: I do not like it

    Care to explain how did you get your hands on someone else's code?

    → Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    Lol you should be really ashamed ! you are the worst cheater in history !

    → Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +7 Vote: I do not like it

    The trick you were trying to pull off by changing the contents of your comment, all the revisions are publicly available if you don't know. Just accept that you have cheated and come clean.

    → Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Approximate rating of C?

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +1 Vote: I do not like it

Is there any groups for post contest discussion Where we can discuss our approach to the problem like discord server or telegram or meet Or we can have a new one

→ Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Is this contest rated for 2100+

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    No, it's rated only for div2.

    → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      But there's no (*) in common standings for 2100+ participants and they are included in common standings

      → Reply
      • »
        »
        »
        »
        21 month(s) ago, # ^ |
          Vote: I like it +4 Vote: I do not like it

        yeah it's just broken for edu rounds

        → Reply
      • »
        »
        »
        »
        21 month(s) ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        it's still not rated for them, you can check other educational rounds.

        → Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Hi guys. Any rating predictions in D?

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +10 Vote: I do not like it

how to solve F?

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    binary search the answer, then do the tree dp, let dp[x] be the minimum score of a subtree of node x you can get, where the score of a subtree rooted at x is:

    if dp[x]<=0 that means that node x isnt yet painted black and that we have a white path starting at x in the subtree of x which is of length -1*dp[x]

    if dp[x]>0 that means that node x is painted black and that it contains currently a chip and that the chip needs dp[x] more steps which will go upwards from x

    → Reply
»
21 month(s) ago, # |
  Vote: I like it +3 Vote: I do not like it

Can anyone help me to review my code for Problem C, I got TLE on test 2 and I have no idea about it. I use the binary search and difference array, I think it is O(nlogn). But got TLE. https://mirror.codeforces.com/contest/1795/submission/193929768

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    make vectors global as this 193938114

    → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks, it works! But do you know why this will work, and my one will cause the TLE?

      → Reply
      • »
        »
        »
        »
        21 month(s) ago, # ^ |
        ← Rev. 3   Vote: I like it 0 Vote: I do not like it

        oh, I misread the n/N. Creating a vector of size N is O(N), and you create it for each testcase. So you will be TLE.

        → Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Your code complexity is $$$O(T * MAXN)$$$. $$$MAXN$$$ in this case is $$${10}^5$$$. If T is large (>= $$${10}^4$$$) you code will TLE

    → Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Whyy can't we do the nCr for prob D using FOR LOOPS! I've been stuck on Case 6 the entire time just because I didn't use a template...

→ Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

I can't believe I wrote this for A:
Sometimes it seems I just get stuck with some wrong observation for over an hour...
Submission.

→ Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

When will the ratings be updated?

→ Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Problems were very interesting, especially E was very beautiful problem. Thank to authors for such nice contest!! :)

→ Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

When will the ratings be updated?

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It usually takes a super long time to update your rating in EDU/div3/div4 rounds.

    → Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Can you help me see what's wrong with my code? So the problem is E,stk is the number of blood counts that differ by 1 from the number in a row. I would appreciate it.194084249

→ Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Hello i wish some of the codeforces managers review my comment. i've worked really hard on this contest but still got skipped because i've submitted the same codes for the first two problems (A and B) on my second account and i have proofs that i owne both of the accounts, and i can show the proofs for any of the managers.

the second account name : frb_husen2 account link : https://mirror.codeforces.com/profile/frb_husen2

→ Reply