vovuh's blog

By vovuh, history, 3 weeks ago, In English

Hello! Codeforces Round #786 (Div. 3) will start at May/02/2022 17:35 (Moscow time). You will be offered 6 or 7 problems (or 8) with expected difficulties to compose an interesting competition for participants with ratings up to 1600. However, all of you who wish to take part and have rating 1600 or higher, can register for the round unofficially.

The round will be hosted by rules of educational rounds (extended ACM-ICPC). Thus, during the round, solutions will be judged on preliminary tests, and after the round it will be a 12-hour phase of open hacks.

You will be given 6 or 7 (or 8) problems and 2 hours to solve them.

Note that the penalty for the wrong submission in this round (and the following Div. 3 rounds) is 10 minutes.

Remember that only the trusted participants of the third division will be included in the official standings table. As it is written by link, this is a compulsory measure for combating unsporting behavior. To qualify as a trusted participants of the third division, you must:

  • take part in at least two rated rounds (and solve at least one problem in each of them),
  • do not have a point of 1900 or higher in the rating.

Regardless of whether you are a trusted participant of the third division or not, if your rating is less than 1600, then the round will be rated for you.

The problems were invented and prepared by Adilbek adedalic Dalabaev, Alexander fcspartakm Frolov, Ivan BledDest Androsov and Mikhail awoo Piklyaev. Also huge thanks to Mike MikeMirzayanov Mirzayanov for great systems Polygon and Codeforces.

Also huge thanks to I_Remember_Olya_ashmelev, Vladosiya, mesanu and I.AM.THE.WILL for testing the round and valuable feedback on the problems!

Good luck!

UPD: Editorial is published!

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

»
3 weeks ago, # |
  Vote: I like it +21 Vote: I do not like it

Good luck everyone!

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it -26 Vote: I do not like it

    I will also give this contest today

    #include<bits/stdc++.h>
    using namespace std;
    int main(){
       cout<<"I will also give this contest :)"<<"\n";
    }
    
»
3 weeks ago, # |
  Vote: I like it +40 Vote: I do not like it

omg vovuh div3s are back!!! :D

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Yes, I hope no smurfs and good luck to everyone!

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Hope for the best!

»
3 weeks ago, # |
  Vote: I like it +23 Vote: I do not like it

Best way to celebrate my birthday!! Vovuh's Div3s are lit!

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

sheesh finally I can start again ... after 5 months :|

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Hope I turn Pupil this Round

»
3 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

I have been participating in Div3 for quite a long but this contest never went unrated for me. I wish it doesn't happen again after this contest.BTW, Best of luck everyone.

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

Best Wishes everyone for the contest and Happy Eid to all of you.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

»
3 weeks ago, # |
  Vote: I like it +27 Vote: I do not like it

vovuh, welcome back

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Wish high rating for all!

»
3 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

I have a question why some of the announcements don't give us exact numbers of problems?

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

    I think because they don't have a final problemset yet, maybe because they have 8 or more problems made but they are not sure which problem to put on 1-2 places, and they will decide later

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

hopefully i get specialist yoooo

»
3 weeks ago, # |
  Vote: I like it +5 Vote: I do not like it

Eid Mubarak today

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

Did someone notice, its Codeforces Round #786(the holy number) on the eve of Eid-al-Fitr!!! Such coincidence Much wow!

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

vovuh welcome back in div 3s

»
3 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

welcome back in div 3s, vovuh

»
3 weeks ago, # |
  Vote: I like it +6 Vote: I do not like it

You will be offered 6 or 7 problems (or 8)

or 9

»
3 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

Eyeing specialist from a distance 0_0

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

cfbr++

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I hope to turn expert this round. =)

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Hope I will be specialist after this div3 contest!!!

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Div3 is back again !

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I want be specialist after this contest.

»
3 weeks ago, # |
  Vote: I like it -8 Vote: I do not like it

vovuh welcome back

please make the time of the contest 2 : 15

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

While(1)Rp++;

»
3 weeks ago, # |
  Vote: I like it +2 Vote: I do not like it

Long time these authors have not done div 3. All good solutions!

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Good Luck everyone!!!.

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

I think this will be a div 3 round.

»
3 weeks ago, # |
  Vote: I like it -11 Vote: I do not like it
#include<iostream>
using namespace std;
int lucky;
int main()
{
    lucky = 2147483647;
}
»
3 weeks ago, # |
  Vote: I like it -38 Vote: I do not like it

Very Bad contest

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

THIS CONTEST IS AWESOME!!!!!!!

»
3 weeks ago, # |
  Vote: I like it +42 Vote: I do not like it

Marinush

»
3 weeks ago, # |
  Vote: I like it +21 Vote: I do not like it

Why there is not any example or description note for test cases in problem F... can't really understand the test cases :(

»
3 weeks ago, # |
  Vote: I like it +19 Vote: I do not like it

Spent 30 minutes to understand F :(

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

I has closed div 3. Very good problems! Upd: hacked E :(

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I think D is the hardest problem :))

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it -17 Vote: I do not like it

    I think D is shit and unnatural.

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

    what was your approach? I tried like this but failed — the pairwise mins in array A must have an increasing order. for odd n the pairing excludes the first element, but it has a constraint to be the smallest integer.

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

      sort each pair of (N, N — 1), (N — 2, N — 3).... and check if you can get sorted array. your solution does not work for 2 4 3 5.

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

        thanks a lot for the reply. i understand my mistake and realize my level of dumbness.

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

      In the Problem D. why does the test case fail if we use the condition:

      if(n == 1){
      cout << "YES\n";
      }
      
  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Orz

»
3 weeks ago, # |
  Vote: I like it +20 Vote: I do not like it

G is a simple but educational problem. Hope there will be more problems like this in the following div2/3 contests.

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

    Can you explain it please?I think it's the longest path in the graph after deleting some edges but there are some cases that I choose edges that I shouldn't

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

      It's a simple dp problem where you first topsort the vertices, and then for each vertex $$$u$$$ with in-degree greater than 1, you iterate over the parent nodes $$$v$$$ ($$$v \rightarrow u$$$), and if the parent node has out-degree greater than 1, you update the dp value as $$$dp_u = dp_v + 1$$$.

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

        Since the graph is a DAG, you can use memoized search instead of topsort

»
3 weeks ago, # |
  Vote: I like it +2 Vote: I do not like it

E — Breaking the Wall, Wrong answer on test 32. What was that?

»
3 weeks ago, # |
  Vote: I like it +35 Vote: I do not like it

can u unfreeze the standings + let us submit

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Interesting tasks and good round! Thanks :)

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

I did'n noticed that problem G statement:'a valid directed acyclic graph', I tried tarjan to shrink strongly connected components into points (poor english).Although it was unnecessary, I'm just wondering if this algorithm would be correct without such a condition.I would be grateful if someone could help me.

»
3 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

Why results are frozen?

I can't submit((

»
3 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it
Spoiler

How it should work? It just reloads the page

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I spent 40 minutes on D and got TLE because I'm using native linked lists, there is no way you wanted me to implement an optimized liked list for this right?

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

    Nope, note that you can only change the relative order between two elements after sorting ($$$a_{n} \leftrightarrow a_{n - 1}, a_{n - 2} \leftrightarrow a_{n - 3}, ...$$$)

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

    you don't really need to do the operation.

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

      can you explain how to calculate it then please

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

        do some simulation and you will find you only can pairwisely revert elements from the right side.

      • »
        »
        »
        »
        3 weeks ago, # ^ |
        Rev. 5   Vote: I like it 0 Vote: I do not like it
        Problem D
»
3 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

vovuh rocks!!

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

anyone explain F pls

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

    remember the total number N of current icons on the screen, and the number of icons in the first N cells. The result is the difference between them. Use fenwick tree to find out the second value.

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

      Actually there is no need for a Fenwick tree. You can simply iterate through the columns for each query and sum the amount of operations needed

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

        Looks like with this time complexity it will work only for c++

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

    You can consider unraveling the matrix resulting in a vector (i.e. taking the first column, then second, then third, and stick them to make a new vector). Then, the apps need to be in a prefix of this vector. when adding a image, you extend the prefix, otherwise you need to shrink the prefix (where you need to move the icons). Then, to find how many images you need to move is to calculate the number of images you have in the prefix you currently are in. If this number is X, and you have Y images on the desktop, then $$$Y - X$$$ is the answer. To calculate X, you can do some if's when erasing/inserting images (to see if they spawn/despawn directly from your prefix)

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

    You had to count gaps in the icon arrangement using segment/fenwick trees.

    Video Solutions: A-F

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

      No need of segment tree or fenwick tree it can be done without any extra log factor just have a two variables currow curcol which will denote the position for last icon after rearrangement. And whenever a new * is added somewhere just change the curpos to next postion by curcol+=(currow+1)/n currow=(currow+1)%n; and calculate total stars and number of stars inside the consecutive region. Submission- https://codeforces.com/contest/1674/submission/155735790

»
3 weeks ago, # |
  Vote: I like it +78 Vote: I do not like it

Aight, guys. This comment may seem a bit toxic or something, but I still want to express how do I feel about this situation. Firstly, I want to say that the problem F is mine (I'm an author of the idea and I prepared this problem).

I get when people are confused about palindrome bracket sequence (as it was in some recent Educational Round), this thing can be really confusing when you see it. But I can't get how people are not familiar with the order of icons appearance on the desktop. Like, if you code from your phone or from fedora or some other OS without GUI, the desktop itself for you can be really confusing, but I don't think there are a lot of such people among Div.3 participants. So, I can't believe nobody saw that when you install some application and mark the field ''add the icon to the desktop'', this icon appears in the first column that is not full, and then in the first position from the top inside this column. Also, when you sort your icons, they're rearranging exactly as in this problem. I thought I created a very life-based problem and people will understand it easily, but I was wrong.

Moreover, the statement wasn't perfect, but was clear enough. There was the following sentence in the second paragraph: ''In other words, some amount of first columns will be filled with icons and, possibly, some amount of first cells of the next (after the last full column) column will be also filled with icons''. I agree that I could add some pictures or maybe highlight some words in the second paragraph, but I thought this is very-very life-based thing that anyone will understand without problems.

At last, I agree that I'm not completely right in this situation, because our task is to make statements as clear as possible for anyone. But, as I said before, this is just my personal opinion, so you can discuss it with me here or maybe just downvote this comment if you disagree.

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

    The statement is a bit hard to understand, but anyway it's still OK to me.

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

    Hey, thanks for the problem, and for the years of service!

    I think the statement was okay, but when reading it for the first time, I felt like an image with the statement would be perfect. Or maybe, explanation of one test case.

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

    Bringing statements back to reality is a good goal. I appreciate the effort.

    CP-english is unfortunately a low-trust highly-synthetic dialect that's really hard to get used to even as a native speaker of normal human english.

    Therefore, as a moron who had to ask in abject paranoia for the clarification 'is a palindrome a palindrome today, sir?' in that contest, it's maybe unsurprising that today's F was incomprehensible to me despite the real-world context... I'd reckon it's because we're routinely asked to ignore/overwrite it for synthetic predicates despite collisions ('alphabetical' to mean something besides sorted in the ordinary sense), distortions ('local maximum' when what was really meant was 'peak' or 'width-1 local maximum'), or sign-flips ('distance' and 'closeness' are opposites, but the problem happily defines one to be the sum of the other).

    For what it's worth, I was envisioning desks in a classroom (being lenient on 'desktop' as if it were just sloppy wording for 'desk') and just couldn't make any sense of why there'd be icons etc. Cp itself is 'command line' more than desk icons...? Any mention of 'computer', 'screen', or even 'resolution' might've helped pull me back out of that dead end, but it's still, as always, up to the reader to read. My mistake and certainly not the last...

    At least in the palindrome case, there was the option to code my way out '())(' as 'occo' etc. For today's F, I just bailed out of respect/fear of its position (plus I was still mulling over the nested 1538G in E and badly tempted by an ultimately incorrect thought on G).

    So... nothing especially toxic, just... something we can all keep working at (better than retreating to formalisms, imo)

    Otherwise, usual thanks and orz's, good stuff.

    edit: 'local maximum' matches 'peak' better... don't remember which the problem asked for whenever it was tho...

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

    As a tester, I agree with vovuh. I also thought everyone encountered desktop arranging at least once and would understand the problem perfectly. To me, it seems like a very nice life-based problem so I didn't suggest any changes to the statement. Will definitely keep such things in mind from now on though.

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

    For problem F, why did the question allow a time limit of 3 seconds? It'd be reasonable to make the participants to use a time limit of 1 second instead.

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

      Yeah, that's probably true. I was just scared that some python/java/(any other non-CP language) users couldn't solve this problem because there is too many IO. But I was completely wrong, so there are also some $$$O((n+m)q)$$$ solutions in C++, and this is a bit disappointing. I also discussed this with Ivan, and we decided that 3 seconds is okay, but turned out it wasn't.

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

    "But I can't get how people are not familiar with the order of icons appearance on the desktop."

    On mac, by default it is right to left:

»
3 weeks ago, # |
  Vote: I like it +28 Vote: I do not like it

Problem E's pretests are so weak!!!!!!! I have already hacked myself!!!!

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

    Educational rounds and div3s are meant to have weak pretest. Why do you think there is a 12 hour hacking period?

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

      But it is the responsibility of questions setters to have strong pretests that contains most situation of the problem,rather than called the competitors to successfully hack more than one thousand accepted answer.

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

    Dear contestant...

    Please don't worry if you had to hack yourself in order to see if your solution is good. In a programming competition, the tests used can be useless, you should have assured your code works. Sorry if this does not fit in your view.

    Author of xem sdod

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

      Imposter?

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

        Dear non-contestant,

        Please don't worry if someone else is a fan of EGOI and swapped two letters from your name. In a programming community thoughts as such are completly irrelevant. Apologies if this does not fit your view.

        So, can we please get back to programming ?

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

Thank you vovuh and the team for organizing this Div 3 contest. I love the questions and how they were being framed.

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

Amazed to see some red+ coders getting hacked on E. What is the hack case ?

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

thank you AHMADUL for solving A!!!

»
3 weeks ago, # |
  Vote: I like it +12 Vote: I do not like it

in D I thought that the operation from b to c was the same as from a to b. F :(

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

    I spent about 30 minutes thinking of a solution for this problem before I realize It was not the real problem

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

please someone hack this if you can :: you can't hack this E prblm — E

»
3 weeks ago, # |
Rev. 5   Vote: I like it +22 Vote: I do not like it

Testing data for problem E is far too weak.

We can hack a lot of solutions using this data.

2
1 5
»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

idea for d? and whats on pretest 32 in e?

»
3 weeks ago, # |
  Vote: I like it -17 Vote: I do not like it
import java.util.*;
import java.io.*;

public class D {
    private static Scanner s = new Scanner(System.in);

    private static void solve() {
        int n = s.nextInt();
        Integer[] arr = new Integer[n];

        for (int i = 0; i < n; i++) arr[i] = s.nextInt();

        List<Integer> list = new ArrayList<>();
        int start = 0;
        if (n % 2 == 1) {
            list.add(arr[0]);
            start = 1;
        }

        for (int i = start; i < n; i += 2) {
            if (arr[i] < arr[i + 1]) {
                list.add(arr[i]);
                list.add(arr[i + 1]);
            } else {
                list.add(arr[i + 1]);
                list.add(arr[i]);
            }
        }

        Arrays.sort(arr);
        for (int i = 0; i < n; i++) {
            if (list.get(i) != arr[i]) {
                System.out.println("NO");
                return;
            }
        }
        System.out.println("YES");
    }

    public static void main(String[] args) {
        int t = s.nextInt();
        while (t-- > 0) {
            solve();
        }
        s.close();
    }
}

Problem : D Can someone help me understand why my code is failing pls?

»
3 weeks ago, # |
  Vote: I like it +14 Vote: I do not like it

so many hacks to E...I have rised from 600+ to 400+.

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

;-; Got WA on C just because I wrote (1ll<<a.size()) as pow(2,a.length())

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

    me too!!!And I also used "#define int long long" which caused me to miss the problem until the last few minutes when I changed it to (int)pow(2,a.length())

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone explain to me, what's the point of the removing condition in G? Doesn't it allow us to remove any edge?

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

    The condition is that, after removing any number of edges, the final graph MUST have in-degree and out-degree of EVERY vertex to be strictly less than the original graph (except if the in/out degree was 0 for any vertex in original graph).

    For example, if there is a graph 1->2->3->4, then we can't just remove 1->2, because in the resulting graph (2->3->4), the in-degree and out-degree of 3 are the same as that in the original graph.

»
3 weeks ago, # |
  Vote: I like it +12 Vote: I do not like it

thanx for good and strong E test's!

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

any hint for E?

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

    I'm trying to explain my solution while my solution is hacked...so I deleted all my notes...

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

      One minute I was hacking my junior, the next I was being hacked by myself...

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

    The idea is to make any two element to zero by three ways.

    • If you shoot directly to two lowest valued position. You can get one of the answer.

    • If you shoot at two consecutive position. You can get one of the answer. If maximum of the two number is greater than or equal to the twice of smaller one then shooting larger one will give the answer, else you need to shoot both to get optimal answer.

        int a = max(v1[i], v1[i-1]);
        int b = min(v1[i], v1[i-1]);
        if(b*2<=a) {
             int x = a;
             int y = ceil((double)(x)/2.0);
             ans = min(ans, y);
        } else {
             int x = v1[i]+v1[i-1];
             int y = ceil((double)(x)/3.0);
             ans = min(ans, y);
        }
    
    • If you shoot at at one position and it's effect may be seen on both left and right side and can contribute to answer.
        int x = v1[i]+v1[i+2];
        int y = ceil((double)(x)/2.0);
        ans = min(ans, y);
    
    • Minimum of all above cases may give the correct answer. Till now this solution is not hacked.
    • Correct me if I am wrong.
    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Can you explain this line int y = ceil((double)(x)/3.0);, in point no. 2 , in else part. Why do we divide by 3, here?

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

        You need to take care of two consecutive positions. If you shoot at one position then a total of 3 values will be decreased 2 from the position where you shoot and 1 from the position adjacent to it. That's why you need to divide total from 3

»
3 weeks ago, # |
  Vote: I like it +31 Vote: I do not like it

I didn't noticed acyclic graph in G...

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

Wow tons of hacks on E. Accept number decreases in every second!

I forgot a corner case (1 10000 3), the answer is 2(shoot middle, then right). Weak sample and tests.

Upd: till now, about a half solutions hacked!

»
3 weeks ago, # |
  Vote: I like it +9 Vote: I do not like it

E's pretests are a joke

»
3 weeks ago, # |
  Vote: I like it +18 Vote: I do not like it

These hacks are crazy, I have gone from 170th to 89th in 45 minutes after the contest. Maybe I will be next...

»
3 weeks ago, # |
  Vote: I like it +134 Vote: I do not like it

Cursed spoiler:

open this spoiler
»
3 weeks ago, # |
  Vote: I like it +11 Vote: I do not like it
Only for Newbies
»
3 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

What does E's pretest mean...I wrote this chmin(ans, (mx + mx + 1) / 2); Then it's got AC????? Of course it's hacked...

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

I am a simple man, I solved 5, my rank was initially around 1800, then everyone started getting hacked and my rank became around 1200 :) , and then ( you guessed it right ) I myself got hacked! now my rank is 2200+

Please CF don't troll me XD

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

    Once my rank was about 200 higher than everyone else I knew I would get hacked. Luckily there were so many that they did not end up affecting my actual position all that much (before I was around 700, now I'm around 700)

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

      that's great! in middle, I thought I would shift to F because I was not too sure about the optimal decrement of 2 adjacent values but this problem got more ACs than others so I devoted my last whole hour to it to make it AC and it got successfully hacked :)

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

        I also considered shifting up to F and decided against it for the same reason. I was able to get some kind of idea for F in the last 20 mins too (even if I couldn't figure out implementation) so I probably would have solved it if I devoted that time to F instead. At least my pre-E penalty is fairly low (likely the reason my position didn't drop)

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem E: My solution

Whats wrong with this?

»
3 weeks ago, # |
  Vote: I like it +41 Vote: I do not like it

2000 participants: "I solved E!" Joury: "No You didn't)"

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

    There are more than 50 pages of successful hacking to E. Never imagined to this...

»
3 weeks ago, # |
  Vote: I like it +12 Vote: I do not like it

The pretests are weak — I solved E, then got hacked. I forgot about the case a[i] > a[i + 1] * 2(and vice versa) (then it's not (a[i] + a[i + 1] + 2) / 3 but (a[i] + 1) / 2)). Such a simple one, but pretests didn't cover that case..

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

    There are no pretests in div.3, div.4 or educational rounds. It's full feedback meaning submissions are judged on all tests. Although, the tests on E were weak no doubt. The solves went from ~3000 to ~550 after system testing was over.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

interesting in hacking problem E the real game

»
3 weeks ago, # |
  Vote: I like it +10 Vote: I do not like it

Enjoyed the few minutes when I thought I solved E

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I have been hacked :(

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

Too weak E pretests!!

»
3 weeks ago, # |
  Vote: I like it +7 Vote: I do not like it

proof by AC isn't working with problem E

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

This round is amazing ,Because some of my friends get higher ranking than one hour ago。

»
3 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it
Meme
»
3 weeks ago, # |
  Vote: I like it +28 Vote: I do not like it

If everyone is hacked, it means everyone is not hacked.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I might be making a rude comment but the number of hacks makes me wonder that is the Jury's solution completely correct? Is it not possible for some really correct solutions to get hacked just because the jury's solution happens to be not perfect.

Just a thought.

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

    My dear friend, you are absolutely wrong jury always have a proof to defend their solutions

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

    The hacks are tested against jury's solution, that means the jury solution gives different output from the hacked solutions. Which means it's correct.

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

      Moreover, there is not just ONE jury solution, usually there are at least 5 to 10 different valid solutions (written in different languages)

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

"You should always prove your solutions before submitting" — Tourist

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

Alright, for those that had wrong answer on pretest 32 in problem E like me, maybe this one will help you:
2
3 6
Answer is 3. I had 4 because I was trying to reduce by 3 both numbers while possible (applying two operations, subtracting 1 2 and 2 1) but this is not optimal, as you can just shoot number 6 three times.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone explain how to solve problem E?

Thanks in advance.

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

    There are 3 ways to locate two broken sections:
    Case 1. Adjacent
    Case 2. Through one
    Case 3. Different locations
    We need calculate 3 minimums independently and take a total minimum. Let section's durabilities are x, y. Without reducing generality x<=y.
    Case 1. The number of onager's shots is:
    - if 2*x<y then (y+1)/2
    while Monocarp shoots more durable section, the adjacent section will be broken
    - else (x+y+2)/3
    Monocarp can decrease total durability of both sections by 3 every shot may be except the last one
    Case 2. The number of onager's shots is:
    x+(y-x+1)/2
    At first Monocarp shoots x times right between the sections. Then Monocarp shoots second section as target (y-x+1)/2 times.
    Case 3. The number of onager's shots is calculated independently for x and y:
    (x+1)/2+(y+1)/2

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

Is it May's fool? :')

»
3 weeks ago, # |
  Vote: I like it +2 Vote: I do not like it

Problem E: failing just like the question name : Breaking the Wall (of pretests)

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

If you prefer command line, checkout CF Doctor for more flexibility and faster feedback.

If you are/were getting a WA/RE verdict on problems from this contest, you can get the smallest possible counter example for your submission on cfstress.com. To do that, click on the relevant problem's link below, add your submission ID, and edit the table (or edit compressed parameters) to increase/decrease the constraints.

If you are not able to find a counter example even after changing the parameters, reply to this thread (only till the next 7 days), with links to your submission and ticket(s).

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

A B C D E-Hacked

»
3 weeks ago, # |
Rev. 3   Vote: I like it +6 Vote: I do not like it

I have just refreshed the page and 620 accepted solutions for E became 570(during 2min). I am sure till tomorrow there will not be correct solutions

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

    In my dream today there were 8 correct solutions/ When I woke up, I was like "Was it real or a dream")

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

What does "the prefix of the next column" in F means? Does it mean that I need to put all remaining icons to the upper side?

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

    Yes

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

    Yes. Effectively it means that if you took all the icons out, you would fill the columns greedily left to right, and within each column greedily top to bottom.

    Correct configuration:

    ***..
    ***..
    **...
    **...
    

    Incorrect configuration:

    ***..
    **...
    ***..
    **...
    
»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone help me know why i am not included in common standing. I do not have a rating of 1900 ever. Am I not trusted participant ?

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

do successful hacks give extra points for this round?

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

    nope!

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

      really? Damn! I hacked 10 submissions. I guess it was a waste of my time... So why do problem setters provide 12 hours of hacking phase for participants? Do they want us to make strong pretests for them?

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

        It was a waste of your time if you didn't learn anything from it. Otherwise it wasn't.

        Div 3 (and 4) rounds are run according to Educational Round rules. The purpose of the 12 hour hacking phase is to encourage the studying of others' code and learning how to stress test, debug, and spot holes in algorithms. Often the tests deliberately leave out certain cases to make hacks more likely (though rarely as extreme as problem E today).

        If you only did it for points then yes I suppose you did waste your time; otherwise you did exactly what the round is designed for.

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

          I meant to say that doing 10 hacks was a waste of my time since nearly all of them failed on same test case, and obviously I learned why those submissions failed

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

        it's not a waste of time if you hacked people with better ranking than yours

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

        Anyways, You don't get points for hacking in Div 3

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

hacks ;-;

»
3 weeks ago, # |
  Vote: I like it +21 Vote: I do not like it

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Was hacked in E because of the case for (i,i+1) we have equations

2*k1+k2>=a[i] 2*k2+k1>=a[i+1]

when k1<0 or k2<0 my solution was not working. This case should be in pretests!

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

where we can find the editorial for this contest ??

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

E: WA on pretest 14 and 32 -> could not even enjoy the temporary happiness

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Please hack 155725210 this

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

rating update when??

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

and if you had no participation and zero rating, then the rating will not rise?

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Could someone please try and hack 155731727

I want to see if I have written the correct solution. Thanks,

»
3 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

I have a question when this contest is rated.

»
3 weeks ago, # |
  Vote: I like it +7 Vote: I do not like it

Here are video Solutions to all problems in case people are interested.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

The pretest of E is trash

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Why I haven't get any rating after participating in the contest and solving 3 questions there?

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

    Rating is not yet updated ig, only hacking phase is completed.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can you explain me why I haven't got any rating after participating in the contest and solving 3 problems there?

»
3 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

This F problem is not as difficult as F problem. Original two-dimensional problem can be very very easy converted to one-dimensional.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

In the Problem D. 786D - Rap God

Spoiler
»
3 weeks ago, # |
Rev. 4   Vote: I like it +1 Vote: I do not like it

Hello MikeMirzayanov,BledDest,vovuh,adedalic.System

I find out some plagiarism activity in Codeforces Round #786 (Div. 3).

Please check out submissions of problem 1674B - Dictionary,submissions are 155621247 and 155678427 They both have same function with same variable but just comment down it and wrote it again with some variable change. Please look out at it.

Proofs given below and also you can check submissions...

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

Hello MikeMirzayanov, vovuh, System

Recently, I(Shrink) got a mail that my codes (1674A - Number Transformation155603503, 1674B - Dictionary155612690) concides with the codes (1674A - Number Transformation155599121, 1674B - Dictionary155608233) of user Yinch. The problems are basic implementations and this is a very rare case the solutions are matched, These problems are completely hard coded by me.

I am very sure that i did not shared my code or had any kind of communication or relation with the other user.

PS: I've made my submissions late , If i had submitted faster than Yinch then he/she would face this issue.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Hi, my solution 155678478 for problem 1674D accidentally coincided with 155656667, the reason lies in using my default code that I use. I'd want to request you to kindly ignore this, since it is accidental. I'll make sure that I'll not violate Codeforces rules intentionally or unintentionally. Thank you.