Vladithur's blog

By Vladithur, history, 8 months ago, In English
Hi, Codeforces!

Alexdat2000, Igorfardoc, and I are pleased to invite you to our Codeforces Round 890 (Div. 2) supported by Constructor Institute, which will be held on Aug/05/2023 17:35 (Moscow time). This round will be rated for participants with a rating lower than 2100.

We would like to thank:

You will be given 5 problems, one of which is divided into two subtasks, and you will have 2 hours to solve them.

One of the problems will be interactive, so please read the guide for interactive problems if you are not familiar with it.

The score distribution is 500 — 750 — 1250 — 2000 — (1500 — 1500)

UPD: Tutorial

UPD2: Congratulations to the winners!

Div. 2:

  1. AMDAM
  2. Aoi_Minoa
  3. baojiaopicua
  4. Valaki2
  5. JCY_

Div. 1:

  1. neal
  2. maspy
  3. A_G
  4. AmazingTalker_Frank
  5. heno239

We are thrilled to share some exciting news with you! We are teaming up with our partner, Constructor Institute in Schaffhausen, Switzerland, to bring you an amazing opportunity: a round supported and organized in collaboration with Constructor Institute, where you can explore Master's programs in Switzerland. Now we pass the floor to our partner.

CU

Hello, Codeforces community!

Constructor Institute in Schaffhausen (Switzerland) is pleased and proud to have the opportunity to support the round on Codeforces. We invite you to participate in it!

If you are passionate about studying in Switzerland and pursuing a Master’s degree, we encourage you to fill out the form to initiate the application process and scholarship interview. Our Institute representatives will be in touch with you to guide you through the next steps.

We offer two Master programs, both taught in English, with flexible duration of 1.5 or 2 years full-time:

Our Master's programs open doors to a world of opportunities. Many of our students have secured high-profile roles in multinational companies in Switzerland and across the globe. Additionally, our programs also serve as an excellent preparation for Ph.D. research in fields such as software engineering, cybersecurity, artificial intelligence, and other advanced topics.

​​We understand that financing your education can be a concern, and to support your journey, we are offering the following scholarships:

  • Tuition waiver scholarships — 20,000 CHF per year, covering the cost of tuition fees.
  • Full scholarships — 20,000 CHF per year, covering the cost of tuition fees, along with a monthly stipend of 2,000 CHF to assist with living expenses in Schaffhausen.

Both scholarships are non-repayable, providing you with financial peace of mind.

To learn more about Constructor Institute and its programs, visit our webpage.

Eligibility for the programs and its available scholarships:

  • You have obtained or you will obtain a Bachelor’s degree in Computer Science, Software Engineering, Physics, or a related field before the program starts.

To express your interest in this opportunity, please complete the form:

Complete the Form

We wish you good luck in the competition and enjoy solving the problems.

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

»
8 months ago, # |
  Vote: I like it -7 Vote: I do not like it

Omg Igorfardoc round!

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

Omg sponsored div2 round!

»
8 months ago, # |
  Vote: I like it -10 Vote: I do not like it

It will be interesting if Mike and the team can share how they prepare a contest.

  1. How each problem was created(Idea)?
  2. Problem statement
  3. How testers helped?
  4. How they decided problem difficulty?
  5. If any other challenges they have faced

So we can understand your efforts and hard work to conduct a contest.

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

    Yes, I agree as I believe it would greatly deepen all participants' understanding of the contest if the authors can share with us the problem statements beforehand.

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

      Problem statements won't help me. They should provide editorials for the questions before-hand

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

        Editorials won't help me, They should provide Author's solution before hand.

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

          Author's solution won't help me, They should hand me my -100 rating before hand

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

      I think he meant after the contest.

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

    Getting Problem statements before the round will be very useful to prepare for round.

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

    Go to catalog section. There you'll get most of your answers.

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

can i expect constructive algo problem? as it was sponsored by constructor institution

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

As a tester, I thought the problems were nice, and I recommend participating in this round!

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

As a tester, I hope my enjoyment when testing the round would be indicative of your enjoyments when participating in it.

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

orz tibinyte testing round !!!

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

Hope to become cyan!

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

Hoping to reach specialist this time.

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

Hope to become specialist before arrival of Joyboy

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

Hope to be constructive(as this round)

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

As a tester, I really enjoyed this round! Everyone should participate!

»
8 months ago, # |
  Vote: I like it -16 Vote: I do not like it
»
8 months ago, # |
  Vote: I like it +3 Vote: I do not like it

I say a full constructive and a happy specialist for me. gl everyone!

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

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

As a participant i recommend all of you to participate.

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

As a tester, good luck! (And give me contribution)

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

I'll solve at least 4 problems,good luck to me.

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

Based on the score distribution, I think this round would be speedforces.

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

Hiha, this round is going to be fun! >_<

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

hoping to become pupil again

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

As a tester, problems is excellent and cute :>

»
8 months ago, # |
Rev. 3   Vote: I like it +20 Vote: I do not like it

This Constructor Institute, it's the former "Schaffhausen Institute of Technology", right? Is it going to obtain (or maybe already has) accreditation any time soon? I also wonder what's the connection with Constructor University Bremen... They seem to share the logotype.

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

As a tester, ris noitubirtnoc em evig esaelp

»
8 months ago, # |
  Vote: I like it -34 Vote: I do not like it

Round Clashing with Leetcode Round

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

    Codeforces > Leetcode

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

      I know that Codeforces >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> Leetcode

      But for interview prepration as told by striver_79 u should have to give Leetcode Contest

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

hope i can ac C problem :)

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

Thanks,Constructor Institute.

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

Hope I can be a master.

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

5 problems? I think it will be hard.

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

    actually 6 problems,because one of the 5 problems is divided into two subtasks

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

Hoping to become pupil this contest

»
8 months ago, # |
Rev. 3   Vote: I like it +20 Vote: I do not like it

preparing for permutation problems :) DYK? A permutation is an array consisting of n distinct integers from 1 to n in arbitrary order. For example, [2,3,1,5,4] is a permutation, but [1,2,2] is not a permutation (2 appears twice in the array) and [1,3,4] is also not a permutation (n=3 but there is 4 in the array).

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

Wish you all lots of love, good luck and non-negative delta

As usual quietpan did well. Wish solvemproblr had given :(

»
8 months ago, # |
  Vote: I like it -91 Vote: I do not like it

A literally A very Very Very Very Very bad contest : ( ( ( ( ( ( (

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

It's good to see that cf is finally improving on their problem statements.

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

For me, this was the coolest contest I've been to in the last couple months. Namely in the fact that the tasks mostly do not require knowledge of complex algorithms, all the solutions are quite short. Thank you! And a question. in E2 n = 1e6 to prevent bitset O(n^2/64) solutions?

»
8 months ago, # |
  Vote: I like it -16 Vote: I do not like it

I'm fed up with these constructor algo problems.

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

A: If a[i]<=a[i+1], then 0 <= max(0, a[i+1]-1) and a[i]-1 <= a[i+1]-1 <= max(0, a[i+1]-1), therefore max(0, a[i]-1) <= max(0, a[i+1]-1), then a[i]<=a[i+1] holds after any times of operation. If a[i]>a[i+1], we need to perform a[i] operations to make a[i]=a[i+1]=0. So the answer is max(a[i]) where a[i]>a[i+1].

B: If n==1 there's no solution, let's assume n>=2. Let t be the number of occurences of 1 in a[i]. If t==0, then we can let a[1]+=n-1 and a[i]-=1 (2<=i<=n). Let's assume t>=1. Then sum(i: a[i]==1)(b[i] — a[i]) >= t because b[i] is positive integer and b[i]!=1, so b[i]>=2. Therefore, sum(i: a[i]!=1)(b[i]-a[i]) <= -t --> sum(i: a[i]!=1)(a[i]-b[i]) >= t --> sum(i: a[i]!=1)(a[i]-1) >= t. So if sum(i: a[i]!=1)(a[i]-1) < t, there's no solution. Otherwise, we can construct a solution: First turn 1 into 2, then we reduce the maximum element in a by 1 for t times. If there's some a[i] remain unchanged, then a[i]>1, then we can reduce them by 1 and add them to any occurence of 2.

C: For any 1<=i<=n-1, let's find the maximum value it can become by binary search. Assume the value we are checking is T. Then we need T-a[i] operations on i-th element. If a[i+1]>=T-1 then we are done. Otherwise, we need T-1-a[i+1] additional operations on (i+1)-th element, Then check if a[i+2]>=T-2. We repeat this process until we find some j such that a[i+j]>=T-j, or we have used more than k operations. Then we can solve the problem in O(n^2*log(k)).

D: We can solve the problem by D&C (Divide and Conquer). Assume we need to find the index of maximum element on [L, R]. If L==R then the answer is L. If L+1==R, we can do query(L, R) and the answer of query is 1 if p[L] is the maximum (0 otherwise). In general cases, we choose M close to (L+R)/2 and solve (L, M) and (M+1, R) recursively, assume their answer be x, y. Then we only need to find if p[x]<p[y]. Let's do query(x, y) and query(x, y-1), the difference of answer of the queries means "there are how many i such that x<=i<=y-1 and p[i]>p[y]". If p[x]<p[y], then we have p[i]<=p[x]<p[y] for x<=i<=M and p[i]<p[y] for M+1<=i<=y, so the difference will be 0. Otherwise we have p[x]>p[y], so the difference will be at least 1. Then we can solve the problem. The cost of queries will be not greater than 2*n^2 for the top layer, 4*(n/2)^2 = n^2 for the second top layer, 8*(n/4)^2 = n^2/2 for the third top layer and so on. So the total cost is not greater than n^2*(2+1+(1/2)+(1/4)+...)=4*n^2.

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

    For C, how does O(n^2*log(k)) pass so seamlessly if n=1000 and n^2*log(k) = about 2e9?

    Edit: Soz idk why I thought n^2 = 1e8 imma kms

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

      $$$n^2 \log_2 k = 1000 \cdot 1000 \cdot \log_2 10^8 \approx 10^6 \cdot 26 = 2.6 \cdot 10^7$$$, not $$$2 \cdot 10^9$$$

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

      1000*1000*20 = 2e7...

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

      your maths is blowing my mind

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

      log_2(1e8) ~= 26, n^2 = 1e6

      n^2lgk ~= 2.6e7

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

      $$$O(n^2)$$$ has very little constant, and if you count $$$n*n*log(1e9)$$$, it's actually $$$30'000'000$$$

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

      We can optimise the min max range to

      long low = max;
      long high = max + 1000;
      
  • »
    »
    8 months ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    .

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

    In B why can't we just jumble up the elements of the array such that a[i]!=b[i] and all elements will remain same so the sum of array a will be equal to array b ?

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

      because you can have an arr=[2,2,2] and still come up with answer [1,1,4] while if you try to jumble you will still end up with having the same array.

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

How to approach C problem anyone??

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

    binary search on answer.

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

    binary search to find the maximum possible $$$a_i$$$ we can make for every $$$i$$$

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

    YocyCraft's solution is good — in order to find it, you probably have to make the observation, that it has to be optimal to increase only one segment of numbers. After that, you can try starting that segment at every number.

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

    Note that we can binary search the answer, as the following gives rise to a monotonic function -

    We ask the simpler question: "Is the value X attainable after at most k operations?"

    Since the constraints on n are small enough, an O(n^2) solution suffices.

    Loop through the array, checking if we can make this current element equal to X. We can calculate the cost required to make this element equal to X, by simulating the process, making sure that the next element is adjusted appropriately using recursion. If we can afford the cost, then we say that we can attain X. Otherwise, we are unable to achieve X.

    Careful implementation must be done, but this is the general overview of the logic.

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

    Ough, probably I need to learn binary search, as I didn't try to use it and wrote $$$O(n^2)$$$ solution, which I thought is very difficult for $$$C$$$ problem.

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

Could anyone please tell me how my E1 question didn't pass the test 7?

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

E2,seems to be bad. why 1e6.

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

    so any hint?

  • »
    »
    8 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it
    why 1e6
    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it +31 Vote: I do not like it

      Is this the reason why E1 is so basic?

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

      Many people using 2log FFT didn't pass. The bitset solution is not educational, just very intentional and unnatural. Your goal is to educate, not to show off.

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

        what is 2log FFT btw?

        Guess: it is divide and conquer and performing FFT on each array $$$O(n*log(n))$$$

        hence $$$n*log^2(n)$$$

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

      Do you know how it feels like to only come up with a $$$\mathcal O(n\log^2 n)$$$ solution when $$$n = 10^6$$$?????? I thought about the 2log FFT for almost an hour and struggled on how to optimize it, but you finally tell me it actually is intended solution?????????

      $$$\mathcal O(\dfrac{n^{1.5}}{w})$$$ is a totally brute, I agree with you. But that doesn't mean you have to limit it ———— It can still pass, it's not a big number. From a progressive perspective, this is a worse solution, indeed. but within the scope of programming competitions, some things just simply cannot be hacked. Come on, Codeforces don't have Quantum machines; I don't think it is allowed for you to enlarge the data range at will.

      I think it's so bad, really. It's not a joke. Nor E2 problem itself is educational.

      • »
        »
        »
        »
        8 months ago, # ^ |
        Rev. 4   Vote: I like it +19 Vote: I do not like it

        I'm not saying it is an intended solution, it's not. I am saying that it is possible to get AC with it with some optimizations. The intended solution is the $$$O(\frac{n \sqrt n}{32})$$$. It is just that we are not concerned whether or not the alternative $$$O(n \log^2 n)$$$ will TLE or AC.

        I'm personally not sure how my comment got intepreted as $$$O(n \log^2 n)$$$ is the intended solution...

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

          Oops, it seems that we have some different understandings on your word "force"......

          So since you are not concerned about the alternative solution, why don't you just reduce the data range to $$$5\times 10^5$$$ or less? You say that you are not concerned. And in that case, all $$$\mathcal O(\frac{n^{1.5}}{w})$$$ solutions will definitely pass without caring about constants.

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

            The word "force" is used here to mean that we wished to separate $$$O(n^{1.5})$$$ and $$$O(\frac{n^{1.5}}{w})$$$. In fact, a tester (Umi) submitted $$$O(n^{1.5})$$$ that we are still unable to hack.

            To suggest to contestants to contests that we do not want to accept $$$O(n^{1.5})$$$, we made constraints much bigger than normal $$$O(n^{1.5})$$$ problems.

            Edit: Umi's solution is described in their comment at https://codeforces.com/blog/entry/119058?#comment-1055388

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

              You think the impression is more important than the actual? You want people to think nsqrtn as unpassable, but some people still could pass? You are just like the ostrich who sticks its head in the sand.

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

          But seems that many $$$O(\frac{n \sqrt n}{32})$$$ solutions didn't passed?

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

      I heard some of my friends used FFT and got TLE,and some got PP;And I also found some implemented-nice bitset solutions passed,and some bad $$$O(\frac{n \sqrt n}{32})$$$ solutions got TLE.Is this really suitable for a CF contest?

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

      How to solve it with FFT in $$$\log^2 n$$$? I can only understand how to do it in $$$\log^3 n$$$

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

hint for E2?

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

    I haven't solved it, but it looks like $$$O(n^{1.5})$$$ knapsack

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

    I boiled to problem to:

    solve the following problem for each $$$i$$$ from 1~n:

    denote a = $$$[sz_v]$$$, where $$$v$$$ is all the direct sons of $$$i$$$ and $$$sz_i$$$ denotes the subtree size of $$$i$$$. find a subset of $$$a$$$ $$$v$$$ such that $$$\sum v$$$ multiplied by $$$\sum a-\sum v$$$ is maximum.

    but i don't know how to solve this:( seems that top performers used some sort of crazy stuff lol

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

    Intended complexity is $$$\mathcal{O}(\frac{n\sqrt{n}}{32})$$$. The key idea is that the total sum of values for the knapsack isn't too large. So the number of distinct elements is small. See https://codeforces.com/blog/entry/49812 for details.

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

      I did exactly this but didn't AC

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

        The $$$\frac{1}{32}$$$ factor is actually significant! In your solutions, I see that you either

        • use vector<int> (which doesn't help)
        • use vector<bool> which is a bitset, but you do not use bitwise operations on it (shift + or, instead of manual loop).
        • »
          »
          »
          »
          »
          8 months ago, # ^ |
          Rev. 2   Vote: I like it +1 Vote: I do not like it

          I didn't know we could do bitwise operations on vector of bool. Either ways, that's a stupid thing to trap a solution on, I think bounds should have been looser

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

      Wow, thanks

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

Anyone who had wa7 on e1, how did you deal with it?

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

i wish all cf problem statements are like this contest. even though I did badly in it.

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

Any idea for E1? I thought of a dfs approach, in which I visited every node and counted the total number of nodes in it's subtree. Then according to the number of immediate children to the node, I tried dividing the total number of nodes in the subtree into two groups such that both the groups have roughly the same number of nodes.

I kept getting wrong answer on test case 7 for some reason I don't understand. Can anyone provide some insight to it please?

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

    Your idea is very good, the only part that is missing is how exactly you are dividing the subtrees into two groups. In order to do that, you have to use a kind of knapsack-DP in order to calculate all sizes of the two groups

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

      Can you please elaborate a bit, my idea was also similar but I didn't know how to approach further with it.

      Can you please tell me what are the dp states?

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

        For a certain node: dp[i] = true iff there exists a subset of the subtrees of the node that have together exactly i nodes. For each subtree with k nodes, you update the dp-array by setting dp[j] to true iff dp[j-k] is true. For a node which has m subtrees with n nodes together, this runs in O(nm).

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

          Can we do it for E2

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

            That method does not work for E2. Consider the case of the root having the other 10e6-1 nodes as children: Then, the dp-array has the size of 10e6-1 and we iterate through it 10e6-1 times. It is possible to improve that by small constant factors, but for E2 you have to make bigger changes

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

It is interesting, that transition from E1 to E2 looks like a super standard problem that everyone should know how to solve, yet so much struggle to do so. (Note, personally idk how to solve E2).

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

Just wanna know how many people got WA on problem D because of making query with l = r LOL.

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

WA on 6th pretest in C anyone?

Submission: 217341446

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

    long

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

      Thank you for your invaluable feedback, but I did use long long for my calculations in C (also the answer can't exceed a 32-bit integer)

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

    Improve your binary search correctness. You need a standard.

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

      I did not use binary search, I tried to do a greedy $$$O(n^2)$$$ solution, you can observe that the maximum value can be obtained if you build a pyramid that is tilted to the left.

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

    Your situation is same as mine. During contest, I also got WA 217328079 on 6th pretest in C. Our approaches are similar. Both the outer loop and inner loop are counting backwards.
    Once I changed the inner loop to count forward, I can get AC. See my 217375396. Not sure why yet.

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

      I have just found the mistake in my implementation — I wasn't updating the height of the first element in the sequence after lifting the entire sequence, the correct submission: 217377033 (the only difference is that I have added the current variable)

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

      Take a look at Ticket 17042 from CF Stress for a counter example.

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

Who decided E1 was a good problem on 5th position?

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

    I mean, according to the problem points (1500 for E1, 2000 for D), it was expected that E1 would be easier than D.

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

just asking to confirm if it is just with me or happening with u also? Did the first question took more than 5 minutes to load for u all?

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

    No. You might want to try mirrors of codeforces like m1.codeforces.com, as they work much faster

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

Most balanced contest ever!

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

Cool problems, thanks. :)

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

wasted 30 minutes on C because I did not read the constraints carefully

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

Had high hopes from this contest, but got stuck at A:(

Please help me what went with my logic/code ; It keeps failing on pre-test 2. I am not able to find a test case, where this fails. If you could provide me with one, I can word out the error myself. Thanks!

#include <bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(),(x).end()
#define ll long long

void solve(){

    ll n;
    cin>> n;

    vector<ll> v(n);

    for(ll i=0;i<n;i++){
        cin>>v[i];
    }

    if(is_sorted(all(v))){
            cout<<0<<endl;
            return;
    }

    ll index = max_element(all(v)) - v.begin();
    if(index!=n-1){
        cout<<*max_element(all(v))<<endl;
        return;
    }
    else{
        ll index=INT_MIN;
        for(ll i=n-1;i>=1;i--){
            if(v[i]<v[i-1]){
                index=i;
                break;
            }
        }
        cout<<*max_element(v.begin(),v.begin()+index)<<endl;
    }   
}

int main(){  

	ll t;
	cin>>t;

	while(t--){
		solve();
	}

    return 0;

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

    What's your logic?

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

      If the array is already sorted, we need 0 operations, so print 0.

      Else find the index of maximum element If the maximum element is not at the last index, we need to make the max element = 0 for sorting the array, in this case the number of operations is equal to the value of the maximum element.

      else if the maximum element is at the last index, find the first index from last after which the array is sorted or find the first index i from last where v[i]<v[i-1] ; once you get the index ; array from i to n-1 is already sorted & you need to make the maximum element in range[0,i] equal to 0 for making the remaining array sorted, thus max element in range[0,i] is the answer.

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

    you are making it too complicated, try to observe the basic pattern

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

      knot_scared you are right ; the simple idea just didn't click for me today & I went for overcomplicated ideas ; but I just want to know where my idea is lagging. I am not able to find a test case, where this fails. If you could provide me with one, I can work out the error myself. Thanks!

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

    I will give you a test case where your solution fails but keep in mind that you should in general go for the simplest solution. Try to solve the problem again and find the simplest way to solve if you want to improve.

    1

    4

    7 4 10 10

    your codes answer: 10 correct answer: 7 after 7 operations the array becomes 0 0 3 3

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

      OmarAboutaleb77 thanks for your help man! The max_element() points to the first such value if multiple max values are there. Would surely go for simple logic only. Thank you.

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

Hints for B?

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

    Rough Idea: Just watch out for number of 1s in a. If there are none, then a_i := a_i — 1 for all i in {1,2,...,n-1} and a_n := a_n + n-1 Otherwise, let y be number of 1s and x is sum of non-one numbers... increase each of these y 1s to 2 and so, if x — y >= y, then YES else NO. [This works because you can reduce these non-one numbers to cover up the y increment and if something is still unchanged, reduce it by 1 [not equal to zero as this value is at least 2] and increase one of the 1s (original) by another 1]

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

    Distribute money from rich to poor

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

      How is that?

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

        Take the money from the richest guy and make the change in the lives of the poorest guys.

        [Richest] [Mediocre] [Mediocre] [Poor] [Poor] [Poor] [Poor] [Poor]

        The richest guy wants to affect the lives of as much people as possible. The richest guy knows that Mediocre guy will not appreciate 1 cent donation as much as the poor guys would. That's why the richest guy always targets the poorest to make the most impact on the population.

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

please help in C

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

    use binary search on each index.

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

    Binary search on the answer + bruteforcing every position where the maximum value will be

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

C was a good problem E1 also. I solved it with DFS+SUBSET SUM Dp

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

Is it possible to solve C without binary search? My idea is to check each subarray and find the maximum value achievable, but was not able to implement it in $$$O(n ^ 2)$$$.

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

    I'm waiting for the sys testing to be over, so I can see what I did wrong in my $$$O(n^2)$$$ approach (intuitively I think it's totally possible)

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

    Yes its possible, you need to maintain the maximum allowed value of ai for subarray [i,j] based on values in [i,j] and j+1. Rest is just sum of AP and prefix sums

    Solution : https://codeforces.com/contest/1856/submission/217318594

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

well,E1 is easier than D and it can easily AC,but E2's score is lower than D,it makes A+B+C+D+E1 > A+B+C+E1+E2 . you know , AC E2 is more and more and more harder than AC D.

Is it good?

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

Could anyone tell me why my E1 code returns the wrong answer on test #13?

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

my E2 solution without bitsets fits in half of TL, can anyone hack? 217346719

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

Knapsack part of Problem E might match for many contestants if they used same website to get the code

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

A question to anybody who solved C: this problem is about BS on the answer. How do you understand a problem requires being approached in this way? Is there a particular signature or something which makes you think in this direction? Is it the constraints? The fact that the operation was mentioned to be performed no more than k times? Does it ut just comes with experience and/or by solving similar problems(if yes please suggest some)? Any good insight is appreciated.

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

    If problem is such that answer at some point is possible then it must be possible for all either less or greater values then we can try to think of binary search. A better and formal name for this behaviour is montonic function. A monotonic function is a function which is either entirely nonincreasing or nondecreasing

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

      in this case the function is like if we can get a value x then for sure we can get another value <= x?

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

        Yes, so that's why we only then need to search for values > x

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

          ok. Which is if I found that for some x is possible. I know the best ans so far is x and I look in the interval [x+1, hi]. Makes sense. So once this is clear the problem becomes how to check if it is possible to get some value. Right?

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

    when the problem is about minimum or maximum, it is pretty common to use binary search.

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

    It's a feeling, a hunch. At first you digest the problem and then you start bruteforcing different techniques in you head.

    This is basically what's going on inside of my head

    Hmm... N is pretty small. Does bruteforce work? Hmm, N is 1000, so N^3 it will be 10^9 ops, so probably will not pass. Maybe dp will work? Not sure how to apply it... What about two pointers... hmmm... seems like doesn't apply either. Oh there is this interesting sequence 6, 7, 5, 4, 3, 2, 1.... could I use n * (n + 1) / 2 somehow here?? Hmmm... I don't see how to apply it.. What about binary search?... Looks like I'm onto somthing... lets research it further....

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

      you make it clear xD. Going by exclusion also brings you there

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

      I thought about bruteforce and dp but didn't able to think in a bs way.

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

can someone tell me why i got FST on E1? 217343471
my approach: I calculated the subtree size for each node. then for every node, stored the subtree sizes of its child nodes in an array. then did a dp to partition the array in 2 sets such that the difference of their sum is minimized. and then added their product with answer.

upd: got ac after making the graph directed :')

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

Does 11k+ submission of B justified ??

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

    What do you mean?

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

      I think it was pretty good idea and I don't think that much number of submission is justified

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

        I am gonna get downvoted, but I also find it suspicious that everybody was able to find the idea. I have seen way easier Bs with less subs.

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

          You can't just say that "I have seen way easier Bs with less subs.". You aren't measuring objective difficulty here. You're measuring how you felt about the problems. You have seen Div2B's whych were easier for you but harder for most people. This time the problem was easier for most people (many probably guessed the amswer), but harder for you.

          This is actually a thing that happens to everyone. I remember two recent contests and their Div2E's (both were 2400 rated problems): I was able to solve one in about 15 minutes, while I couldn't get the other one even after 90 minutes.

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

Please help me, i'm unable to understand what's wrong with my code. When i'm running it on my laptop's Visual studio code it's working fine and giving the expected results as in the output but when submitted as answer then it says wrong answer on pretest 1.

Here is my code for Problem A of Contest 890 (Div 2):


#include <bits/stdc++.h> using namespace std; int main() { int t; cin>>t; while(t--) { ios::sync_with_stdio(false); cin.tie(nullptr); int n,ans=0; cin>>n; int arr[n]; for(int i=0;i<n;i++) cin>>arr[i]; for(int i=1;i<n;i++) { if(arr[i-1]>arr[i] && arr[i-1]>ans) { ans=arr[i-1]; } } cout<<ans<<"\n"; } return 0; }
  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Got it! I just saw that i have put ios::sync_with_stdio(false); cin.tie(nullptr); in the while loop by mistake which is not its right place.

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

    You can compare your solution with that of mine.

    //@author: @ihnaqi
    //@href: https://codeforces.com/contest/1856/problem/0
    
    use std::io;
    use std::cmp;
    
    fn input() -> String {
       let mut s = String::new();
       io::stdin().read_line(&mut s).unwrap();
    
       s
    }
    
    pub fn main() {
       let s = input();
       let mut t = s.trim().parse::<i32>().unwrap();
    
       while t > 0 {
          solve();
          t -= 1;
       }
    }
    
    fn solve() {
       let s = input();
       let n = s.trim().parse::<i32>().unwrap();
       let mut v: Vec<_> = input().split_whitespace().map(|x| x.parse::<i32>().unwrap()).collect();
    
       if is_sorted(&v) {
          println!("0");
       }
       else {
          let mut res = -1;
          for i in (1..=n-1).rev() {
             if v[i as usize] >= v[(i - 1) as usize] {
                continue;
             }
             else {
                res = i;
                break;
             }
          }
          let mut max = v[0];
          for i in 1..=res {
             max = cmp::max(max, v[i as usize]);
          }
          println!("{}", max);
       }
    }
    
»
8 months ago, # |
  Vote: I like it +1 Vote: I do not like it

After getting FST on problem D, I dropped from rank 3 to rank ~200. I am not surprised because in each recursion I ask three queries (r-l)*(r-l). If my code did not pass the pretests, I would come up with the solution.

And I think the score division in problem E is not suitable.

Sorry for my bad English!

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

Could anyone help me out with C Submission

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

I hope rating changes will update before i get to sleep.

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

My FSTed solution for E2 involves heuristics to solve the simplified problem "partitioning the given set of positive integers $$${a_1,a_2,\cdots,a_k}$$$ into two, so that the difference between the smaller sum and $$$\frac{\sum a_i}{2}$$$ is minimized." Specifically:

  1. If $$$\max a_i \geq \frac{\sum a_i}{2}$$$, then the smaller sum is $$$\sum a_i - \max a_i$$$.
  2. Otherwise, if $$$k \leq 20$$$, brute force over all possible subsets using the meet-in-the-middle technique.
  3. Otherwise, assume $$$g$$$ is the $$$\gcd$$$ of all the integers, I claim that the smaller sum is the largest multiple of $$$g$$$ not greater than $$$\frac{\sum a_i}{2}$$$.

I am curious about how to construct strong tests for such heuristics. Any ideas on constructing them?

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

    If you have subtree of size $$$1$$$, gcd always be $$$1$$$, so you claim that you can always make exactly $$$\frac{\sum{a_i}}{2}$$$. Just make any test with large $$$k$$$, where it can't be achieved.

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

      Actually, my intention is to ask for the ideas behind the construction, not just the test makes my solution fail.

      But I have also come up with one idea: For example, if the set of numbers are $$$1,3$$$ and $$$g$$$ repeated $$$2k'$$$ times ($$$g$$$ and $$$k'$$$ are ome sufficiently large integers), then the $$$\gcd$$$ of them is $$$1$$$, but it is impossible to select a subset with sum $$$\frac{\sum a_i}{2}$$$.

      I have never realized that the construction can be that easy :(, thanks for your reply.

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

nice round, specially the statements are. short and clear

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

Really that many people found B2 solution that easily???!! I guess I need to improve my intuition.

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

    Well it's kinda constructive problem, you should approach them a little bit differently from others

»
8 months ago, # |
  Vote: I like it +7 Vote: I do not like it
Spoiler
»
8 months ago, # |
Rev. 2   Vote: I like it +22 Vote: I do not like it

I'd like to report probably a system issue.Vladithur MikeMirzayanov. During the contest i submitted my solution to e2 and it got rte on test 17. I had 20 minutes to debug it but i didn't manage to do it in time. Surprisingly after contest it appeared that the reason for rte was probably stack overflow because of dfs recursion. (i changed in ac submission after contest only recursion to iteration and it easily got ac). Therefore here are 2 questions:

  • Shouldn't the memory for stack recursion be included for overall memory limit?
  • If there exists separate limit for stack, shouldn't be the verdict mle instead of rte? The verdict really misguided me (in terms of what to debug)

Here is my 1st submission to e2 which got rte: https://codeforces.com/contest/1856/submission/217343160 Here is my submission to e2 after contest which got ac https://codeforces.com/contest/1856/submission/217365641

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

    According to this blog about compiler options, stack for C++ is limited to 256 mb.

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

      I see. However that blog was 13 years ago so there could be some updates. Moreover, my complaint is also that the verdict imo should be mle not rte in this case.

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

    Command lines have not undergone significant changes. For example, for gcc11-64-winlibs-g++20, the command line looks like this: g++.exe -Wall -Wextra -Wconversion -static -DONLINE_JUDGE -Wl,--stack=268435456 -O2 -std=c++20 -o %name%.exe *.cpp.

    I think the verdict of RE is more appropriate. The process in the operating system terminated with an error, and that's what RE is. It's a different situation from trying to allocate more memory and reaching the ML.

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

Video Editorial for problems A,B,C,D and E1;

https://youtu.be/jxLu6DMDV7o

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

Hope to become cyan!

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

Is this ratings without cheaters or what? MikeMirzayanov

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

Let's go I'm master now!

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

Best Div2 A is easy to read and B is easy to read too

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

I really want to say that bitset is a way to optimize your code, and it really can be used in races for answers.

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

https://codeforces.com/contest/1856/submission/217389353 can anyone tell me why i am wrong in this submission ? thank you !

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

One of the tag in problem C is Dp. has anyone solved problem C using DP ? if yes then please share the approach of DP.

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

I enjoyed this game, its concise problem description made me feel comfortable.

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

Thanks for the round, pE2 was really interesting!

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

https://codeforces.com/contest/1856/submission/217324302

10

8 1 11 1 2 1 1 1 1 1

total sum of this array is28

so we can make another array like this

2 2 2 2 10 2 2 2 2 2

so why this case ans is no?

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

    Your Answer is wrong for Test 2.. 3rd one.. which is

    12
    1 2 1 2 1 3 1 2 1 1 1 2
    
»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Thanks for contest!A little late,but contest was great!

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

https://codeforces.com/contest/1856/submission/217873662 Could someone tell me what I am doing wrong?

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

hey i got a warning mail from codeforces that "Your solution 217270813 for the problem 1856A significantly coincides with someone else...." as it was a basic implementation based question and i used the variable names as common so it might be a coincidence and i used ideone compiler so i dont know if due to that this happed. please look into it.

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

hey i got a warning mail from codeforces that "Your solution 217337076 for the problem 1856C significantly coincides with someone else...." as it was a basic implementation based question and i used the variable names as common so it might be a coincidence and i used ideone compiler so i dont know if due to that this happed. I did not share my code to anyone. This is second time i got a warning without any copying or cheating. I belive in fair play. Please look into it.