Блог пользователя Vladithur

Автор Vladithur, история, 16 месяцев назад, По-английски
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.

  • Проголосовать: нравится
  • +441
  • Проголосовать: не нравится

»
16 месяцев назад, # |
  Проголосовать: нравится +35 Проголосовать: не нравится

Omg sponsored div2 round!

»
16 месяцев назад, # |
  Проголосовать: нравится -10 Проголосовать: не нравится

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.

  • »
    »
    16 месяцев назад, # ^ |
      Проголосовать: нравится +68 Проголосовать: не нравится

    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.

    • »
      »
      »
      16 месяцев назад, # ^ |
        Проголосовать: нравится +40 Проголосовать: не нравится

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

      • »
        »
        »
        »
        16 месяцев назад, # ^ |
          Проголосовать: нравится +18 Проголосовать: не нравится

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

        • »
          »
          »
          »
          »
          16 месяцев назад, # ^ |
            Проголосовать: нравится +81 Проголосовать: не нравится

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

    • »
      »
      »
      16 месяцев назад, # ^ |
        Проголосовать: нравится +23 Проголосовать: не нравится

      I think he meant after the contest.

  • »
    »
    16 месяцев назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

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

  • »
    »
    16 месяцев назад, # ^ |
      Проголосовать: нравится +14 Проголосовать: не нравится

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

»
16 месяцев назад, # |
  Проголосовать: нравится +92 Проголосовать: не нравится

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

»
16 месяцев назад, # |
  Проголосовать: нравится +54 Проголосовать: не нравится

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

»
16 месяцев назад, # |
Rev. 2   Проголосовать: нравится +12 Проголосовать: не нравится

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

»
16 месяцев назад, # |
  Проголосовать: нравится +12 Проголосовать: не нравится

orz tibinyte testing round !!!

»
16 месяцев назад, # |
  Проголосовать: нравится +14 Проголосовать: не нравится

Hope to become cyan!

»
16 месяцев назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

Hoping to reach specialist this time.

»
16 месяцев назад, # |
  Проголосовать: нравится +27 Проголосовать: не нравится

Hope to become specialist before arrival of Joyboy

»
16 месяцев назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Hope to be constructive(as this round)

»
16 месяцев назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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

»
16 месяцев назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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

»
16 месяцев назад, # |
  Проголосовать: нравится +48 Проголосовать: не нравится

»
16 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

As a participant i recommend all of you to participate.

»
16 месяцев назад, # |
  Проголосовать: нравится +29 Проголосовать: не нравится

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

»
16 месяцев назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

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

»
16 месяцев назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

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

»
16 месяцев назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

hoping to become pupil again

»
16 месяцев назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

As a tester, problems is excellent and cute :>

»
16 месяцев назад, # |
Rev. 3   Проголосовать: нравится +20 Проголосовать: не нравится

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.

»
16 месяцев назад, # |
  Проголосовать: нравится +68 Проголосовать: не нравится

As a tester, ris noitubirtnoc em evig esaelp

»
16 месяцев назад, # |
  Проголосовать: нравится -34 Проголосовать: не нравится

Round Clashing with Leetcode Round

»
16 месяцев назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится

hope i can ac C problem :)

»
16 месяцев назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится

Thanks,Constructor Institute.

»
16 месяцев назад, # |
  Проголосовать: нравится +21 Проголосовать: не нравится

Hope I can be a master.

»
16 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

5 problems? I think it will be hard.

  • »
    »
    16 месяцев назад, # ^ |
      Проголосовать: нравится +6 Проголосовать: не нравится

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

»
16 месяцев назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

Hoping to become pupil this contest

»
16 месяцев назад, # |
Rev. 3   Проголосовать: нравится +20 Проголосовать: не нравится

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).

»
16 месяцев назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

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

»
16 месяцев назад, # |
  Проголосовать: нравится +30 Проголосовать: не нравится

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?

»
16 месяцев назад, # |
  Проголосовать: нравится -16 Проголосовать: не нравится

I'm fed up with these constructor algo problems.

»
16 месяцев назад, # |
Rev. 2   Проголосовать: нравится +38 Проголосовать: не нравится

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.

  • »
    »
    16 месяцев назад, # ^ |
    Rev. 3   Проголосовать: нравится +7 Проголосовать: не нравится

    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

  • »
    »
    16 месяцев назад, # ^ |
    Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

    .

  • »
    »
    16 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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 ?

    • »
      »
      »
      16 месяцев назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится

      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.

»
16 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How to approach C problem anyone??

  • »
    »
    16 месяцев назад, # ^ |
      Проголосовать: нравится +6 Проголосовать: не нравится

    binary search on answer.

  • »
    »
    16 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    16 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

  • »
    »
    16 месяцев назад, # ^ |
      Проголосовать: нравится +6 Проголосовать: не нравится

    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.

  • »
    »
    16 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

»
16 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
16 месяцев назад, # |
  Проголосовать: нравится +30 Проголосовать: не нравится

E2,seems to be bad. why 1e6.

  • »
    »
    16 месяцев назад, # ^ |
      Проголосовать: нравится +17 Проголосовать: не нравится

    so any hint?

  • »
    »
    16 месяцев назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится
    why 1e6
    • »
      »
      »
      16 месяцев назад, # ^ |
        Проголосовать: нравится +31 Проголосовать: не нравится

      Is this the reason why E1 is so basic?

    • »
      »
      »
      16 месяцев назад, # ^ |
        Проголосовать: нравится +36 Проголосовать: не нравится

      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.

    • »
      »
      »
      16 месяцев назад, # ^ |
        Проголосовать: нравится +24 Проголосовать: не нравится

      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.

      • »
        »
        »
        »
        16 месяцев назад, # ^ |
        Rev. 4   Проголосовать: нравится +19 Проголосовать: не нравится

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

        • »
          »
          »
          »
          »
          16 месяцев назад, # ^ |
            Проголосовать: нравится +3 Проголосовать: не нравится

          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.

          • »
            »
            »
            »
            »
            »
            16 месяцев назад, # ^ |
            Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

            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.me/blog/entry/119058?#comment-1055388

            • »
              »
              »
              »
              »
              »
              »
              16 месяцев назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится

              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.

        • »
          »
          »
          »
          »
          16 месяцев назад, # ^ |
            Проголосовать: нравится +18 Проголосовать: не нравится

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

    • »
      »
      »
      16 месяцев назад, # ^ |
      Rev. 2   Проголосовать: нравится +14 Проголосовать: не нравится

      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?

    • »
      »
      »
      16 месяцев назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

»
16 месяцев назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

hint for E2?

  • »
    »
    16 месяцев назад, # ^ |
      Проголосовать: нравится +19 Проголосовать: не нравится

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

  • »
    »
    16 месяцев назад, # ^ |
      Проголосовать: нравится -7 Проголосовать: не нравится

    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

  • »
    »
    16 месяцев назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    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.me/blog/entry/49812 for details.

    • »
      »
      »
      16 месяцев назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      I did exactly this but didn't AC

      • »
        »
        »
        »
        16 месяцев назад, # ^ |
          Проголосовать: нравится +10 Проголосовать: не нравится

        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).
        • »
          »
          »
          »
          »
          16 месяцев назад, # ^ |
          Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

          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

    • »
      »
      »
      16 месяцев назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Wow, thanks

»
16 месяцев назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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

»
16 месяцев назад, # |
  Проголосовать: нравится +19 Проголосовать: не нравится

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

»
16 месяцев назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

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?

  • »
    »
    16 месяцев назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    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

    • »
      »
      »
      16 месяцев назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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?

      • »
        »
        »
        »
        16 месяцев назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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).

        • »
          »
          »
          »
          »
          16 месяцев назад, # ^ |
          Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

          Can we do it for E2

          • »
            »
            »
            »
            »
            »
            16 месяцев назад, # ^ |
            Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

            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

»
16 месяцев назад, # |
  Проголосовать: нравится +14 Проголосовать: не нравится

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).

»
16 месяцев назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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

»
16 месяцев назад, # |
Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

WA on 6th pretest in C anyone?

Submission: 217341446

  • »
    »
    16 месяцев назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    long

    • »
      »
      »
      16 месяцев назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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)

  • »
    »
    16 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Improve your binary search correctness. You need a standard.

    • »
      »
      »
      16 месяцев назад, # ^ |
      Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

      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.

  • »
    »
    16 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

    • »
      »
      »
      16 месяцев назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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)

    • »
      »
      »
      15 месяцев назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

»
16 месяцев назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

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

  • »
    »
    16 месяцев назад, # ^ |
      Проголосовать: нравится +44 Проголосовать: не нравится

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

»
16 месяцев назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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?

  • »
    »
    16 месяцев назад, # ^ |
      Проголосовать: нравится +6 Проголосовать: не нравится

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

»
16 месяцев назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

Most balanced contest ever!

»
16 месяцев назад, # |
  Проголосовать: нравится +12 Проголосовать: не нравится

Cool problems, thanks. :)

»
16 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
16 месяцев назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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;

}
  • »
    »
    16 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    What's your logic?

  • »
    »
    16 месяцев назад, # ^ |
    Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

    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

    • »
      »
      »
      16 месяцев назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится

      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.

»
16 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Hints for B?

  • »
    »
    16 месяцев назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    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]

  • »
    »
    16 месяцев назад, # ^ |
      Проголосовать: нравится +18 Проголосовать: не нравится

    Distribute money from rich to poor

    • »
      »
      »
      16 месяцев назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      How is that?

      • »
        »
        »
        »
        16 месяцев назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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.

»
16 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

please help in C

»
16 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
16 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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)$$$.

»
16 месяцев назад, # |
  Проголосовать: нравится +23 Проголосовать: не нравится

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?

»
16 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
16 месяцев назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится

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

»
16 месяцев назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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.

  • »
    »
    16 месяцев назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    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

    • »
      »
      »
      16 месяцев назад, # ^ |
        Проголосовать: нравится +4 Проголосовать: не нравится

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

      • »
        »
        »
        »
        16 месяцев назад, # ^ |
        Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

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

        • »
          »
          »
          »
          »
          16 месяцев назад, # ^ |
            Проголосовать: нравится +4 Проголосовать: не нравится

          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?

  • »
    »
    16 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    16 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

»
16 месяцев назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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 :')

»
16 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Does 11k+ submission of B justified ??

  • »
    »
    16 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    What do you mean?

    • »
      »
      »
      16 месяцев назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

      • »
        »
        »
        »
        16 месяцев назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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.

        • »
          »
          »
          »
          »
          16 месяцев назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          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.

»
16 месяцев назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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!

»
16 месяцев назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

Could anyone help me out with C Submission

»
16 месяцев назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

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

»
16 месяцев назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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?

  • »
    »
    16 месяцев назад, # ^ |
    Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

    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.

    • »
      »
      »
      16 месяцев назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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.

»
16 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    16 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

»
16 месяцев назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится
Spoiler
»
16 месяцев назад, # |
Rev. 2   Проголосовать: нравится +22 Проголосовать: не нравится

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.me/contest/1856/submission/217343160 Here is my submission to e2 after contest which got ac https://codeforces.me/contest/1856/submission/217365641

  • »
    »
    16 месяцев назад, # ^ |
      Проголосовать: нравится +10 Проголосовать: не нравится

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

    • »
      »
      »
      16 месяцев назад, # ^ |
        Проголосовать: нравится +10 Проголосовать: не нравится

      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.

  • »
    »
    16 месяцев назад, # ^ |
      Проголосовать: нравится +21 Проголосовать: не нравится

    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.

    • »
      »
      »
      16 месяцев назад, # ^ |
        Проголосовать: нравится +37 Проголосовать: не нравится

      Why not set stack size to be equal to max memory limit for any problem?

»
16 месяцев назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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

https://youtu.be/jxLu6DMDV7o

»
16 месяцев назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Hope to become cyan!

»
16 месяцев назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

Let's go I'm master now!

»
16 месяцев назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится

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

»
16 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
16 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
16 месяцев назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

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.

»
16 месяцев назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

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

»
16 месяцев назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

Thanks for the round, pE2 was really interesting!

»
16 месяцев назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    16 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    12
    1 2 1 2 1 3 1 2 1 1 1 2
    
»
16 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
16 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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