Vladithur's blog

Codeforces Round #890 (Div. 2)
By Vladithur, history, 3 years 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

Comments Comments (199)
| Write comment?
»
3 years ago, hide # |
 
Vote: I like it -7 Vote: I do not like it

Omg Igorfardoc round!

→ Reply
»
3 years ago, hide # |
 
Vote: I like it +35 Vote: I do not like it

Omg sponsored div2 round!

→ Reply
»
3 years ago, hide # |
 
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.

→ Reply
»
3 years ago, hide # |
 
Vote: I like it +92 Vote: I do not like it

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

→ Reply
»
3 years ago, hide # |
 
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!

→ Reply
»
3 years ago, hide # |
← 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.

→ Reply
»
3 years ago, hide # |
 
Vote: I like it +12 Vote: I do not like it

orz tibinyte2006 testing round !!!

→ Reply
»
3 years ago, hide # |
 
Vote: I like it +14 Vote: I do not like it

Hope to become cyan!

→ Reply
»
3 years ago, hide # |
 
Vote: I like it +8 Vote: I do not like it

Hoping to reach specialist this time.

→ Reply
»
3 years ago, hide # |
 
Vote: I like it +27 Vote: I do not like it

Hope to become specialist before arrival of Joyboy

→ Reply
»
3 years ago, hide # |
← Rev. 2  
Vote: I like it 0 Vote: I do not like it

Hope to be constructive(as this round)

→ Reply
»
3 years ago, hide # |
 
Vote: I like it +1 Vote: I do not like it

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

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

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

→ Reply
»
3 years ago, hide # |
 
Vote: I like it +48 Vote: I do not like it

→ Reply
»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

As a participant i recommend all of you to participate.

→ Reply
»
3 years ago, hide # |
 
Vote: I like it +29 Vote: I do not like it

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

→ Reply
»
3 years ago, hide # |
 
Vote: I like it +11 Vote: I do not like it

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

→ Reply
»
3 years ago, hide # |
 
Vote: I like it +8 Vote: I do not like it

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

→ Reply
»
3 years ago, hide # |
 
Vote: I like it +8 Vote: I do not like it

hoping to become pupil again

→ Reply
»
3 years ago, hide # |
 
Vote: I like it +6 Vote: I do not like it

As a tester, problems is excellent and cute :>

→ Reply
»
3 years ago, hide # |
← 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.

→ Reply
»
3 years ago, hide # |
 
Vote: I like it +68 Vote: I do not like it

As a tester, ris noitubirtnoc em evig esaelp

→ Reply
»
3 years ago, hide # |
 
Vote: I like it -34 Vote: I do not like it

Round Clashing with Leetcode Round

→ Reply
»
3 years ago, hide # |
 
Vote: I like it +7 Vote: I do not like it

hope i can ac C problem ：）

→ Reply
»
3 years ago, hide # |
 
Vote: I like it +13 Vote: I do not like it

Thanks,Constructor Institute.

→ Reply
»
3 years ago, hide # |
 
Vote: I like it +21 Vote: I do not like it

Hope I can be a master.

→ Reply
»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

5 problems? I think it will be hard.

→ Reply
  • »
    »
    3 years ago, hide # ^ |
     
    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

    → Reply
»
3 years ago, hide # |
 
Vote: I like it +2 Vote: I do not like it

Hoping to become pupil this contest

→ Reply
»
3 years ago, hide # |
← 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).

→ Reply
»
3 years ago, hide # |
 
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.

→ Reply
»
3 years ago, hide # |
 
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?

→ Reply
»
3 years ago, hide # |
 
Vote: I like it -16 Vote: I do not like it

I'm fed up with these constructor algo problems.

→ Reply
»
3 years ago, hide # |
← 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.

→ Reply
»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

How to approach C problem anyone??

→ Reply
  • »
    »
    3 years ago, hide # ^ |
     
    Vote: I like it +6 Vote: I do not like it

    binary search on answer.

    → Reply
  • »
    »
    3 years ago, hide # ^ |
     
    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$$$

    → Reply
  • »
    »
    3 years ago, hide # ^ |
     
    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.

    → Reply
  • »
    »
    3 years ago, hide # ^ |
     
    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.

    → Reply
  • »
    »
    3 years ago, hide # ^ |
     
    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.

    → Reply
»
3 years ago, hide # |
 
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?

→ Reply
»
3 years ago, hide # |
 
Vote: I like it +30 Vote: I do not like it

E2，seems to be bad. why 1e6.

→ Reply
  • »
    »
    3 years ago, hide # ^ |
     
    Vote: I like it +17 Vote: I do not like it

    so any hint?

    → Reply
  • »
    »
    3 years ago, hide # ^ |
     
    Vote: I like it +3 Vote: I do not like it
    why 1e6
    → Reply
    • »
      »
      »
      3 years ago, hide # ^ |
       
      Vote: I like it +31 Vote: I do not like it

      Is this the reason why E1 is so basic?

      → Reply
    • »
      »
      »
      3 years ago, hide # ^ |
       
      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.

      → Reply
    • »
      »
      »
      3 years ago, hide # ^ |
       
      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.

      → Reply
      • »
        »
        »
        »
        3 years ago, hide # ^ |
        ← 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...

        → Reply
        • »
          »
          »
          »
          »
          3 years ago, hide # ^ |
           
          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.

          → Reply
          • »
            »
            »
            »
            »
            »
            3 years ago, hide # ^ |
            ← 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 (mzen) 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: mzen's solution is described in their comment at https://mirror.codeforces.com/blog/entry/119058?#comment-1055388

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              3 years ago, hide # ^ |
               
              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.

              → Reply
        • »
          »
          »
          »
          »
          3 years ago, hide # ^ |
           
          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?

          → Reply
    • »
      »
      »
      3 years ago, hide # ^ |
      ← 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?

      → Reply
    • »
      »
      »
      3 years ago, hide # ^ |
       
      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$$$

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

hint for E2?

→ Reply
  • »
    »
    3 years ago, hide # ^ |
     
    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

    → Reply
  • »
    »
    3 years ago, hide # ^ |
     
    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

    → Reply
  • »
    »
    3 years ago, hide # ^ |
    ← 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://mirror.codeforces.com/blog/entry/49812 for details.

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

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

→ Reply
»
3 years ago, hide # |
 
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.

→ Reply
»
3 years ago, hide # |
 
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?

→ Reply
  • »
    »
    3 years ago, hide # ^ |
     
    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

    → Reply
    • »
      »
      »
      3 years ago, hide # ^ |
       
      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?

      → Reply
      • »
        »
        »
        »
        3 years ago, hide # ^ |
         
        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).

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

          Can we do it for E2

          → Reply
          • »
            »
            »
            »
            »
            »
            3 years ago, hide # ^ |
            ← 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

            → Reply
»
3 years ago, hide # |
 
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).

→ Reply
»
3 years ago, hide # |
 
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.

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

WA on 6th pretest in C anyone?

Submission: 217341446

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

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

→ Reply
  • »
    »
    3 years ago, hide # ^ |
     
    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.

    → Reply
»
3 years ago, hide # |
 
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?

→ Reply
»
3 years ago, hide # |
 
Vote: I like it +8 Vote: I do not like it

Most balanced contest ever!

→ Reply
»
3 years ago, hide # |
 
Vote: I like it +12 Vote: I do not like it

Cool problems, thanks. :)

→ Reply
»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
3 years ago, hide # |
← 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;

}
→ Reply
  • »
    »
    3 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    What's your logic?

    → Reply
  • »
    »
    3 years ago, hide # ^ |
    ← 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

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

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

      → Reply
»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Hints for B?

→ Reply
  • »
    »
    3 years ago, hide # ^ |
    ← 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]

    → Reply
  • »
    »
    3 years ago, hide # ^ |
     
    Vote: I like it +18 Vote: I do not like it

    Distribute money from rich to poor

    → Reply
    • »
      »
      »
      3 years ago, hide # ^ |
       
      Vote: I like it 0 Vote: I do not like it

      How is that?

      → Reply
      • »
        »
        »
        »
        3 years ago, hide # ^ |
         
        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.

        → Reply
»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

please help in C

→ Reply
»
3 years ago, hide # |
 
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

→ Reply
»
3 years ago, hide # |
 
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)$$$.

→ Reply
»
3 years ago, hide # |
 
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?

→ Reply
»
3 years ago, hide # |
 
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?

→ Reply
»
3 years ago, hide # |
 
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

→ Reply
»
3 years ago, hide # |
 
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.

→ Reply
  • »
    »
    3 years ago, hide # ^ |
     
    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

    → Reply
  • »
    »
    3 years ago, hide # ^ |
     
    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.

    → Reply
  • »
    »
    3 years ago, hide # ^ |
     
    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....

    → Reply
»
3 years ago, hide # |
← 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 :')

→ Reply
»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Does 11k+ submission of B justified ??

→ Reply
  • »
    »
    3 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    What do you mean?

    → Reply
    • »
      »
      »
      3 years ago, hide # ^ |
       
      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

      → Reply
      • »
        »
        »
        »
        3 years ago, hide # ^ |
         
        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.

        → Reply
        • »
          »
          »
          »
          »
          3 years ago, hide # ^ |
           
          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.

          → Reply
»
3 years ago, hide # |
 
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!

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

Could anyone help me out with C Submission

→ Reply
»
3 years ago, hide # |
 
Vote: I like it +11 Vote: I do not like it

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

→ Reply
»
3 years ago, hide # |
← 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?

→ Reply
  • »
    »
    3 years ago, hide # ^ |
    ← 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.

    → Reply
    • »
      »
      »
      3 years ago, hide # ^ |
       
      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.

      → Reply
»
3 years ago, hide # |
 
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.

→ Reply
»
3 years ago, hide # |
 
Vote: I like it +7 Vote: I do not like it
Spoiler
→ Reply
»
3 years ago, hide # |
← 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://mirror.codeforces.com/contest/1856/submission/217343160 Here is my submission to e2 after contest which got ac https://mirror.codeforces.com/contest/1856/submission/217365641

→ Reply
  • »
    »
    3 years ago, hide # ^ |
     
    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.

    → Reply
    • »
      »
      »
      3 years ago, hide # ^ |
       
      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.

      → Reply
  • »
    »
    3 years ago, hide # ^ |
     
    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.

    → Reply
»
3 years ago, hide # |
 
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

→ Reply
»
3 years ago, hide # |
 
Vote: I like it +1 Vote: I do not like it

Hope to become cyan!

→ Reply
»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Is this ratings without cheaters or what? MikeMirzayanov

→ Reply
»
3 years ago, hide # |
 
Vote: I like it +6 Vote: I do not like it

Let's go I'm master now!

→ Reply
»
3 years ago, hide # |
 
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

→ Reply
»
3 years ago, hide # |
 
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.

→ Reply
»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
3 years ago, hide # |
← 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.

→ Reply
»
3 years ago, hide # |
 
Vote: I like it +8 Vote: I do not like it

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

→ Reply
»
3 years ago, hide # |
 
Vote: I like it +8 Vote: I do not like it

Thanks for the round, pE2 was really interesting!

→ Reply
»
3 years ago, hide # |
← Rev. 2  
Vote: I like it 0 Vote: I do not like it

https://mirror.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?

→ Reply
  • »
    »
    3 years ago, hide # ^ |
     
    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
    → Reply
»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

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

→ Reply