By awoo, history, 20 months ago, translation, In English

Hello Codeforces!

On Jul/21/2022 17:35 (Moscow time) Educational Codeforces Round 132 (Rated for Div. 2) will start.

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

This round will be rated for the participants with rating lower than 2100. It will be held on extended ICPC rules. The penalty for each incorrect submission until the submission with a full solution is 10 minutes. After the end of the contest you will have 12 hours to hack any solution you want. You will have access to copy any solution and test it locally.

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

The problems were invented and prepared by Adilbek adedalic Dalabaev, Vladimir vovuh Petrov, Ivan BledDest Androsov, Maksim Neon Mescheryakov and me. Also huge thanks to Mike MikeMirzayanov Mirzayanov for great systems Polygon and Codeforces.

Good luck to all the participants!

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

WORK & STUDY OPPORTUNITY IN BANGKOK — B.GRIMM POWER x HARBOUR.SPACE UNIVERSITY

B.GRIMM POWER has partnered with Harbour.Space University to offer Bachelor's and Master’s degree scholarships in Data Science as well as work experience in one of the main infrastructure developers in Thailand.

B.Grimm Power PCL (B.Grimm Power), is a Thailand-based electricity generating and distribution energy company. B.Grimm Power is involved in the development, financing, construction and operation of power plants. Its product portfolio includes solar, hydro, wind power, and Diesel.

We are looking for various junior to mid-level candidates to work on solving tasks in the following fields:

  • Data analysis
  • System integration
  • AI
  • Forecasting Modeling

All successful applicants will be eligible for a 100% tuition fee scholarship (22.900 €/year) provided by the B.GRIMM POWER.

CANDIDATE’S COMMITMENT

Study Commitment: 3 hours/day

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

Work Commitment: 4+ hours/day

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

REQUIREMENTS:

  • Industry experience
  • International exposure
  • Eager to learn
  • Entrepreneurial mindset
  • (Thai Language is a plus, not a must)
Apply Now

UPD: Editorial is out

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

| Write comment?
»
20 months ago, # |
  Vote: I like it -45 Vote: I do not like it

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

I hope that the round will be interesting not only in words, but also in deeds)

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

codeforces is life Changer

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

Super excited! I love edu rounds

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

Hopefully this one can break through and get a satisfactory placing

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

Where should I put my heart on a night alone

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

.

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

    When you use n<<1 instead of n*2

    int n=1;
    n=n+n*2;
    cout<<n; // 3
    
    int n=1;
    n=n+n<<1;
    cout<<n; // 4
    

    warning. and wrong answer

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

      put paranthesis

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

      but if you do like this

      int n = 1;
          n = n + n * 2;
          cout << n; // 3
          cout << endl;
      
      
          int n = 1;
          n = n + (n << 1);
          cout << n; // 3

      then there is no problem-----

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

        But this will cause more troubles than n*2.

        • »
          »
          »
          »
          »
          20 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it
          n |= n << 1  
          
          • »
            »
            »
            »
            »
            »
            20 months ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            This will also bring wrong answer, for example:

            int n=7; // (111)2
            n+=n*2; // (111)2 + (1110)2 = (10101)2
            cout<<n; // 21
            
            int n=7; // (111)2
            n|=n<<1; // (111)2 | (1110)2 = (1111)2
            cout<<n; // 15
            

            So bitwise operations are dangerous.

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

hoping for a nice round

»
20 months ago, # |
  Vote: I like it -27 Vote: I do not like it

gimme CM pls xD

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

 The Method of Four Russians?

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

Today problems difficulty gap visualization:

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

I hate this round. C is harder than D, that's really not good :)

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

    I just can't find my mistake in C. Also having invested too much time in C, I don't want to try D.

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

    Nice round. But C was definitely harder than D.

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

    Yeah. I'm curious to see the editorial for problem C.

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

      What I did is, if we have to place a number of '(' and b number of ')' in place of the question marks, then it will certainly work to first place a '(' and then place all b closing brackets. (We need to always maintain that count( '(' ) > count( ')' ). The method that is second best to follow the criteria, is we instead place '(' on question marks 1 to a-1, and a+1. If this produces a valid sequence different from the previous one, then the first answer is not unique. Else, there is only a single solution to the problem.

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

No more hard C please! (As a specialist)

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

How to solve F?

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

    I imagine the problem as a trie of height $$$n$$$. A multiset of strings is then an assignment, assigning a weight to each leaf of the trie (the number of strings in the multiset corresponding to that path in the trie). You get to set a limit $$$c[s]$$$ to each non-root vertex denoting the maximum sum of weights in that subtree. However, the actual limit of maximum sum of weights in that subtree is smaller, namely $$$d[s] = \min(c[s], d[u] + d[v])$$$, where $$$u$$$ and $$$v$$$ are the children of that vertex.

    Let $$$\mathrm{dp}[i][x]$$$ be the number of ways to assign $$$c$$$-s in a subtree of height $$$i$$$ such that the true limit is exactly $$$x$$$. Clearly $$$\mathrm{dp}[0][x] = 1$$$ for $$$1 \le x \le k$$$ and $$$0$$$ otherwise. In the general case, for $$$1 \le i < n$$$ and $$$1 \le x \le k$$$:

    $$$ \mathrm{dp}[i][x] = (k - x) \displaystyle \sum_{y + z = x} \mathrm{dp}[i - 1][y]\, \mathrm{dp}[i - 1][z] + \sum_{y + z \ge x} \mathrm{dp}[i - 1][y] \, \mathrm{dp}[i - 1][z]. $$$

    The first term corresponds to the case where the sum of limits in the children is $$$x$$$ and we pick a higher limit at the vertex; the second term corresponds to the case where the sum of limits in the children is at least $$$x$$$ and we pick $$$x$$$ as the limit at the vertex. For $$$i = n$$$ it is a bit different because you don't get to pick a $$$c$$$ there.

    The convolutions in the formula above can be calculated using FFT: you calculate a layer of the DP, then use FFT to "square" it and calculate the new one, and so on. The answer is $$$\mathrm{dp}[n][f]$$$.

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

      Why are the no collisions in the dp formula in each term?

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

      "the second term corresponds to the case where the sum of limits in the children is at least x and we pick x as the limit at the vertex."

      I do not understand this idea, how can we choose a smaller limit than the sum of the children? Do the children sum equal the number of strings that have the prefix at node v?

      Could you help me with that?

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

It is too hard to find out what's wrong with my solution in F with only 1 small example. Shouldn't it be more?

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

I always seem to screw edu rounds :(

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

what is wrong with my code for D? link : https://codeforces.com/contest/1709/submission/165206888

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

    y1 can be bigger than y2

    Got the same bug during contest:(

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

    You need to notice that y1 is no need smaller than y2, and you should query the segment tree from min(y1,y2) to max(y1,y2) instead of y1 to y2.

    This bug just delay me 30 mintues from getting accepted.

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

    y1 can be greater than y2. One small change and you would've got AC :_) 165216733

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

yes_no_forces :)

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

I know C's solution will be super cool. Not able to code the solution on time but it's a great problem.

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

Anyone getting RTE out of nowhere? Or its just me ?

Anyone tell me what tf is wrong with this simple code that its throwing RTE

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

    cin >> n; vll a(3); for (int i = 0; i < n; i++) { cin >> a[i]; }

    in this part n is not the size of array.

    the size is always 3.

    n is the number on the key in your hands.

    it's called x in the problem statement.

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

i hated c

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

    I couldn't even get that far lol.
    Just totally baffled me.

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

got tle on D becouse i used standard cin instead of

ios_base::sync_with_stdio(false); cin.tie(NULL);

:(

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

    Arrrrggggghhhh — same for me....

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

    In this problem we have $$$m + 5q = 2 \cdot 10^5 + 10^6$$$ input numbers, pretty big input.

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

The sample test case of D was frankly useless.
I spent 40 minutes thinking there was a bug in my Sparse Table, only to notice later that the x coordinates were being given from the bottom instead of from the top as usual.
Even in the problem statement this was not mentioned in bold.
Imho, if there's only one sample test case, it should be at least robust enough to not work for inverted coordinates.

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

    Exactly this is ridiculous my wrong submission was because of this thing. Even the second test does not include hacks for that bug.

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

    today's B and D did feel weirdly lazy/obfuscated...

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

How to solve E?

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

    Root tree from any node. Let val[v] = XOR of values from root to v. XOR of path (x, y) will be val[x] XOR val[y] XOR a[lca(x, y)]. Now if XOR of path is zero you need to change value at lca(x, y). Doing dfs if there is a path in subtree with XOR 0 you can just delete it. Answer is number of deleted subtrees.

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

      I'm a little confused — how to find if there is path in subtree with xor 0 efficiently?

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

        Small to large trick, you can read editorial of problem E here.

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

    There are few observations. The first one was that if we change a value for a vertex, we can ensure that any paths going through that vertex is never zero as there are only $$$n^2$$$ possible different xorpath values versus infinite choices for the value. The second observation was that let's say we know the optimal connected subset of vertices in subtree of root $$$t$$$ that are good, let $$$S_t$$$ denote this set. If we iterate over the children of vertex u and merge all $$$S_{c_i}$$$, where $$$c_i$$$ is the ith children of $$$u$$$ and if there is a bad path in the resulting set, we remove u. We can simulate this via small-to-large with sets which gives us $$$O(nlog^2(n))$$$.

    EDIT: Oops, I messed up the details for the first observation.

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

      Isn't $$$n^2=1e10>2^{31}$$$ ?

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

        You can ignore that because in this problem you can replace the value by any positive integer.

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

misunderstood D -> Wrong Answer*6 -> rank 1000+ -> absolutely rating fall :(

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

In C, first I greedily create a valid sequence changing the '?' to '(' while possible, then changing the others to ')'. From these that previously were '?', I swap the last '(' and the first ')'. If this is a correct sequence, then the sequence is not unique. Otherwise, it is. Why does this work, i.e., why could there not be any other choice except the swap I tried?

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

    Swapping same type of bracket makes no difference.

    If you try to swap any two brackets of different types, the prefix sum over all these must be >= 2 at all points.

    Swapping the last '(' and the first ')' is equivalent to checking if min_range(last '(', first ')') is greater than 2. For all other swaps, they all include this subsequence in this swap, so you only need to check this subsequence.

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

    Like if any other swap work then this will work for example for checking whether a string of parenthesis is correct or not we create a array and do +1 for ( and -1 for ) if we find negative anywhere then it is not allowed string so you already know one solution exist and now what can you try to avoid negative number in array you keep on delaying ) so that the chances for negative number is least

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

    that swap is the most likely swap to be successfull except the ((()))) last ( comes before first ) sequence for a sequence to be valid a) the numbers of '(' and')' have to be equal b) counting from the first, the number of '(' has to be equal or greater than the number of ')' by b) that swap creates the sequence most likely to be valid

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

What is intended solution for C?

I came up with: First substitute '?' by '(' from left side, from right side by ')'. Then swap the rightmost substituted '(' with the leftmost substituted ')'. If this results in a RBS then ans=NO, else YES.

But somehow not able to make it work until end, maybe some edgecase ?

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

    number of '?' can be less than 2

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

    I had the same idea. Here is my reasoning why it should work: let a be your first BS. Say we have constructed a greedily. a is an RBS. Say there is another RBS b and let i be the first index where it differs from a. Consider the BS c which is equal to b up to i and constructed greedily after. You can see that if b satisfies RBS conditions, then so does c, then so does your BS with the swap.

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

      We don't even need that. Say a is the first BS, b is the BS with the swap, and i is the first index where a and b differ. If b is not a RBS, then b[...i] has more closing than opening brackets. But for any other candidate BS c, c[...i] would have at least as many closing brackets as b[...i], so it wouldn't be a RBS either.

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

    Turned out simple bug: f[s[i]=='(']++; assuming f[0] is the number of open brackets :/

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

How to solve C

a) How to check if there is a substitution which gives correct paranthesis? First substitute only open parenthesis, then only closed. Example: ??(?))?)(? -> (((())))() there was 2 open parenthesis, hence first $$$n/2-2 = 3$$$ substituted will be open. Check, that this is a correct substitution.

b) How to check if there is another substitution? If there is another substitution, there has to also be a substitution as in a), but with swapped last open and first closed parenthesis. Example: ??(?))?)(? -> ((()))()() here first were substituted $$$3-1$$$ open, then $$$1$$$ closed, then $$$1$$$ open, then $$$2-1$$$ closed. Check, that this is a correct substitution. If yes, answer is NO, otherwise YES.

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

When i can see other test?

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

Somebody, please help me find mistake in my submission for D. 165211545 Edit: found it

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

    You can see the test cases(as yours is wrong at small test case) and run on your local to debug

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

D << C, D is much easy as compared To c

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

Anyone else who just assume y1 <= y2 in problem D and keep failing test case 4 ?

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

Can someone tell me what the fuck is this? Compiled file is too large [44391155 bytes]

I mean I just used NTT and voila.

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

    your global arrays are too large. it's basically an MLE for when you have statically allocated arrays

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

    probably templates generate too much code?

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

I think C can be done like this, Imagine replacing ? with $$$+1$$$ or $$$-1$$$. If I have $$$x$$$ question marks with $$$+1$$$ and $$$y$$$ question marks with $$$-1$$$, ($$$x,y$$$ can be easily found by forming simple equations). Then, note that it is always better to put question mark with $$$+1$$$ value behind the question mark with $$$-1$$$ value, So I only need to check for string in which replaced values of question marks looks like this: $$$(1, 1...1,-1, 1, -1, -1...-1)$$$ If this string turns out to be RBS, then answer is "NO", otherwise ans is "YES".

Note that the problem gurantees that at least one valid RBS is possible, so replaced question marks which looks like this should always form valid RBS: $$$(1, 1...1,-1...-1)$$$

PS: Why solutions come to my mind automatically after the contest which i mess up :(

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

Can anyone help me find mistake in 165181854 ? got TLE in 7th case maybe string error?

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

http://acm.hdu.edu.cn/showproblem.php?pid=4915 It is a big OJ in China. And this is a classical () problem.

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

Any idea about test case 7 of Problem E?

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

[submission:165213863]idk why is this submission wa

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

    Found it.Forgot that when all ? are left brackets the array goes to a point that is a undefined zero

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

No difficulty of thinking, but coding. A boring competition.

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

    as you are a red name, I think it's quite natural for you to have no difficulty of thinking in edu contest.

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

      I mean compare with other div2 contest, this one is quite boring.

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

        E and F, it is natural to think of dp. And one using data structure another using FFT to optimize the transition.

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

          Yeah, it is natural to think of a dp. But if a problem is solved by a thought "hey, this is dp", this does not mean it is a bad task. However, today's E was quite easy to code, so the only really challenging in implementation task is F.

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

          Was it like easy dp? idk really

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

        But need quite code capability.

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

    Also, edu contest is usually implementation based, not so much observation.

»
20 months ago, # |
  Vote: I like it -59 Vote: I do not like it

Nice problems. C requires a smart observation. D is basic segment tree usage. E is basic small-to-large problem.

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

    what's the smart observation for C?

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

      greedily fill the first several ? with ( and others with ). Then swap the last filled ( and first filled ).

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

        Could you please explain why swapping those two specific brackets works?
        Like what's wrong with swapping the first filled '(' and the first filled ')' ?

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

          Take the case ??()?? for example. The best case would be to fill all ( first and then all ), i.e. ((())). If you try swapping the "inner 2" brackets as how Aging1986 had mentioned, you'd get ()()(), which is a rbs so the answer is NO. If you swap any other two brackets you won't get an rbs.

          This is because when you swap the "inner 2" brackets, you've already placed all ( as much to the left as possible and all ) as much as to the right as possible, so this would always be the next best case in some ways if it is possible.

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

I am a little confused. The only difference between these two submissions is:

ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

Why it can speed up about 1s???

165215022

165212687

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

    The input if fairly big, up to 1e6 numbers, so reading input unoptimized takes relevant time.

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

      All right, thx! I will optimize the input in the following contests.

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

Who also had WA8 in E because you inserted not after checking for every vertex, but immediately after you checked for this vertex?

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

    I had WA8 for a different reason: I thought the problem only cares about leaf node.

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

      I just was shocked when 6 of my 7 friends who had a submission in E had the same problem.

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

        I found I actually WAed because of the sane reason once.

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

why did you number the rows from bottom to top ??!

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

    It is edu contest, that is usually implementation based. In this sense, reversing the usual orientation actually spices up the problem.

    Also they made statement of B stupid irritating to make it more thrilling.

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

      that is usually implementation based.

      Wait, are we talking about Educational Rounds or Extended ICPC Rounds in general

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

Can anyone explain to me why my solutions with sparse table and segment tree could not pass until I changed cin to scanf? Other contestants did not seem to have the same problem.
165180154
165184210

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

    Add this line: ios_base::sync_with_stdio(false); cin.tie(NULL);

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

      Yeah, I forgot this template part, makes sense now.
      My guess was that I messed up somewhere in the main part and had to compensate for it with fast input. No way 2000 div2 people would just casually submit scanf solutions first try LMAO

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

So hey, how do you decide whether to keep working on a problem or bailing/skipping?

Feel like I hit the worst of both worlds (again) today's C where I had a brute forcer to get lots of (negative, WA) feedback, and therefore spent juuuust enough time failing there to make sure my AC on D came after contest end (and after the same switched-column bug seemingly everyone else had, but then also some MLEs because I left in the simulated grid, woops).

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

    well, I have failed C and solved D on previous 2 contests, so I just move to D if I don't get the idea for C within 10 minutes. I think that D problems can be solved methodically, while C problems are a "you either know it or you don't" style.

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

In problem C, I thought of first balancing the brackets in the following way : if the number of '(' is more or less than its counterpart, make the number of '?' equal to the difference of number of '(' and ')' become whichever has the minimum count among '(' and ')' and the excess '?'s will be converted according to the one having the greatest count among '(' and ')', extreme ends will be dealt with accordingly with the greatest count among '(' and ')', as the extreme ends can only have one choice.

Now, we reach a case where all the '?'s are in the middle of some brackets and the brackets are balanced. Obviously, the number of '?'s will be even and each '?' can be paired as '()'. If the number of '?'s is zero, this is a unique RBS. Assume we have some positive number of '?'s. Now, if there is at least one '(' to the left of the leftmost '?' and at least one ')' to the right of the rightmost '?', then we can also do it in one other way, i.e. ')('.

I don't know where I'm going wrong, could someone point out what I'm doing wrong or missing ?

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

    Consider that logic, then prepend "()" to the input. Obviously that prefix does not change the answer, but you might get another answer with your algo.

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

Fuck n,m in D.

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

My stupid mistake in D was, I just assumed yf > ys for all cases(ik I am dumb) hence segtree quires were giving wrong answer

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

    Samee man, bro, same. Too sad, I realised this just after the contest

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

A < B < C (Because of observation that we need to make only two distinct valid string for answer "NO") > D

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

This contest had a decent amount of prefix sums lol.

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

unbalanced round makes contest boring

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

Excuse me if my question is stupid, but is this round not getting rated, or will there just be some delay?

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

How to solve E?

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

    Notice that changing the weight is equivalent to removing that vertex.

    One approach is to remove the centroid and solve the remaining trees recursively and then remove the centroid if there still exists a zero path going through the centroid.

    It can also be solved using dfs and small to large merging.

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

      what value should be on vertices which were removed before some other centroid?

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

        A unique power of two

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

          So when we changed some vertex we dont add its value to some xor value, right? UPD: got it thx

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

      How do you check if there still exists a zero path going through the centroid? Also, what will the recursive subproblem calls return? I kinda know only the basic idea of centroids, should definitely read up on that

      • »
        »
        »
        »
        20 months ago, # ^ |
        Rev. 6   Vote: I like it +18 Vote: I do not like it

        edit: apparently this is not the centroid solution. I didn't know that was thing, below I am describing the standard dfs solution.

        First of all notice that we just need to save the xor of all the values from root to a vertex $$$u$$$ (call that $$$f(u)$$$). Then the xor of the path between two vertices $$$u,v$$$ is $$$f(u)\oplus f(v) \oplus a[lca(u,v)]$$$.

        So now the problem is keeping the sets $$$S(x)$$$ with all values $$$f(u)$$$ for $$$u\in\text{Subtree}(x)$$$. That way you can check if there is a 0 xor path efficiently by going through all children $$$v$$$ of $$$x$$$ and checking if $$$f(x)\oplus a[x]\in S(v)$$$ because $$$f(x)\oplus f(v) \oplus a[x] \iff f(v) = f(x) \oplus a[x]$$$. In that case you "delete" the vertex, clearing it's corresponding set.

        To merge the sets fast enough you merge the smallest one with the bigger one. Doing this is fast enough since the number of times a vertex's value $$$f(x)$$$ will move to another set is $$$O(\log n)$$$ because each time you decide to move it to another set of length $$$L' \geq L$$$ ($$$L$$$ is the current length) the new set will be of length $$$L+L' \geq 2L$$$, this can happen at most $$$\log n$$$ times.

        Judging from the comments here, the last paragraph describes a well known technique usually referred to as "small to large" and it is specifically useful for problems with sets in trees.

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

          Small to large is not needed for the centroid solution.

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

          Thank you for the brilliant explanation! Finally got accepted:)

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

      how do you prove that centroid works out?

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

        Any vertex works out, centroid guarantees time complexity.

        Think about all paths with zero xor. All of them will get at least one vertex removed.

        If we remove a vertex, solve the subtrees recursively and don't need to remove the current vertex it's easy to see that it is optimal (because zero paths not containing this vertex would need to be removed).

        If we end up needing to remove this vertex, the recursive calls would have removed the same sets, because the zero paths containing the centroid would have been removed as we remove the vertex.

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

          I think that using just any optimal solution in each subtree of a vertex is not enough.

          (X)--(_)--(root)--(_)--(X)

          In the example above, we have a chain of 5 nodes, the root is the center, and nodes marked with X are removed. Each subtree of the root has a optimal solution, but they don't combine into an optimal solution for the entire tree (the root must be removed as well). You need some extra property for the optimal solution in each subtree: (maybe, for example, among all optimal solutions in a subtree, we select the one where the removed vertices are as close to the root (this is not precise, it's just an idea))

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

            Can you provide a counterexample with weights instead?

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

              Sample input 3.

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

                In this case second and fourth nodes woudl be removed...

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

              This is sample case 3 Sample case 3

              Root the tree at node 3. Both subtrees have optimal solution (one node removed). But they do not combine into an optimal solution for the entire tree (node 3 must be removed)

              Each subtree has two optimal solutions. In the left subtree you can either remove node 1 or node 2. If your recursive call returns the wrong optimal solution for the subtree, you can't use it to construct an optimal solution for the entire tree.

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

                Hmm, maybe the centroid solution does not work after all

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

hey, I had a question:

I wasn't able to participate as I had a school assignment I needed to complete. I just noticed I can still take part in the open hacking... if I do, will it affect my rating?

»
20 months ago, # |
  Vote: I like it -17 Vote: I do not like it

How to solve E?

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

I couldn't solve C :sob:

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

https://codeforces.com/contest/1709/submission/165219365

I write this code but it gave WA in test case 2 in "?)?(??" sample.Can someone please explain what is wrong with my code?

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

    The code only seems to cover the simple YES-instances, where the number of ? is exactly equal to the number of ( needed, or the number of ) needed after ensuring the first and last characters are correct. However, there are other YES-instances that your code doesn't cover, like this example of ?)?(??. The only valid RBS here is ()(()). No other RBS fits, so the answer is YES.

    For the correct approach, I advise checking the editorial. Basically, you figure out how many hidden ( and hidden ) there are. Here, there are an equal number of visible ( and ), while there are four ?, so this means there are two hidden ( and two hidden ). Then we fill up the ?s, first with all ( until one, then one ), then one (, then the rest of the ). For the example of ?)?(??, the result is ())((). We then check if this is valid or not; in this case, it is not valid, because the prefix ()) has more ) than (. Therefore, the RBS must be unique, i.e., only valid choice is all (s, then all )s.

    Note that a valid RBS requires that the total number of ( and ) are equal, and that there is no prefix with more ) than (.

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

Me : don’t need to know segment tree to hit expert Edu Round 132: Hold my beer !

»
20 months ago, # |
  Vote: I like it -15 Vote: I do not like it

What a poisonous codeforces round. I used to believe in your codeforces educational round,thinking you have high-standard problems and rounds,but this time you make a big fault in problem C and let many participants down, hope you could learn form this failure and adjust the difficulty in future rounds!

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

    Prob D was such a good intro to segment tree though. But yes C was too much of an ad-hoc problem to be considered educational. (although bracket sequence problems are very standard)

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

I have a serious problem for a long time! If I use the segtree in Python, it must be TLE, so does it mean that segtree in python doesn't allow in the contest? if not, I think the tester of the contest should test some of the version to let it accepted, quiet confused~

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

    A lot of times I just translate the tutorial solution of C++ into Python, and then it TLE, so unfriendly to Python user

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

can somebody check my TLE submission for E my complexity is O(NlogN) and I also used bitset :)

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

How to solve problem F?

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

How to prove that C's approach is correct

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

    let '(' be 1, ')' be -1, then a parentheses sequence is regular iff the prefix sum off this sequence is nonnegtive at every position and the sum is zero.

    You can use this conclusion to proof the correctness.

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

    Use the typical exchange argument. Suppose you have adjacent $$$-1$$$ and $$$+1$$$. Is it good to swap them?

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

The test "?(" can hack many accepted submissions for Problem C. But I miss the hack time.

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

    No, Because it's written in the problem statement that the main string was an RBC before putting '?'s in it, So your test is invalid!

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

      Sorry,I didn't notice.Thanks for your reply.

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

        You're welcome, Could you please explain the proof of your solution for problem C? Thanks in advance.

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

          I'm sorry.I think about it carefully, and I find that I can't strictly prove it.

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

any hints for D??...like where should I start from :)...

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

Why is it unrated for me?

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

    Dude, the ratings will be published in a while... hacking phase was finished just few moments ago, they will update the ratings soon ::).. It happens in educational rounds , its normal...

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

I couldn't solve C, but looking at some submitted solutions, I could reverse engineer the logic (after getting rid of some vacuous code in those submissions). Let's make a simple observation. If we go over the input string character by character, the string becomes invalid if number of )'s becomes greater than number of ('s plus number of ?'s at any point. You cannot close more parenthesis than have been opened at any point. Now, maintain two values, surplus of )'s, i.e., number of )'s minus number of ('s, call it sp, and number of ?'s, call it q. Since there is always a way to substitute ?'s in the input (guaranteed by the problem statement) to get a valid RBS, we know that sp can never become greater than q. Also, we know for sure that if sp becomes equal to q, then all those question marks must be opening parenthesis. Notice that exactly one of sp and q changes in each iteration and by at most 1. Now, here comes the crucial observation that I believe made this problem hard for many people (including me). Actually, as soon as sp becomes equal to q-1, we know that none of those question marks can be a closing parenthesis, because otherwise the string becomes invalid (think why). So what we do is when sp == q-1, we set sp = -1 and q = 0. Then, in the end, range of sp is $$$[-q,q-2]$$$. If sp == -q, i.e., all question marks must be ), there is a unique way. We claim that in the end, sp cannot be equal to -q+1, because then the input is invalid (think why). Note that if q = 0, this must hold, otherwise the input is invalid. Otherwise sp != -q and we have maintained the invariant that sp has been at most q-2 after q last became 1. Also, since sp cannot be equal to -q+1 in the end, sp is at least -q+2. Which essentially means that we can change any of these question mark to either ( or ), while maintaining the invariant all along that sp <= q, keeping the string valid, so there are at least two ways. (I believe that there is a more elegant argument involving an invariant using parity of sp - q. If anyone knows, please let me know!)

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

    Every "(" gives you a credit and every ")" costs you a credit. Because a bracket sequence is valid iff you don't go out of credits when iterating through, you want to get the credits as early as possible and lose them as late a possible. Therefore the solution that always works is if you replace the first x "?" with "(" and the rest with ")", x denoting the number of missing "(". In the same greedy logic, if there is another possible solution, it will be the one with the last "(" you inserted swapped with the first ")" you inserted (second optimal solution for getting the credits as early as possible and losing as late as possible). I just constructed it and checked if it's valid.

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

Can anyone tell me what is wrong with my D solution 165201502 ?

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

    you should return -1 ( or anything below zero ) in max fuction instead of 0 ( when l > r )

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

      thank you very much) You realy helped me)

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

when will be the rating get updated

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

Thanks for interseting C&E, I learn a lot. But D is too obvious(maybe).

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

Editorial when?

Me waiting

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

I'm just stuck on 1300s since a year. Sometimes it feels to give up but I'm not like that, I don't want to give this up. I was a lot better when I first started, keep getting worse after each contest.

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

    look at my profile after I reached my max, I dropped down till newbie then got back. just don't give up and don't take long rest periods. finally.. keep practicing, up solving, and learning new data structures.

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

      Thanks for the motivation. I will try my best.

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

What's the idea to solve F?

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

I liked the contest

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

What is test 2 in C? I WA in 452nd

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

This comment is regarding the solution 165164219 for the problem 1709B which significantly coincides with the solution ForPracticeDude/165161762 (which is actually a temporary ID of mine for practice purpose) during the contest Educational Codeforces Round 132 (Rated for Div. 2). I unintentionally submitted the solution from that ID because it was logged-in in another browser of my PC. It was totally unintentional and I solved both of the problems A & B on my own and I am still trying to reach PUPIL very honestly and I have no intention of CHEATING. But due to this incident both of my solutions are marked SKIPPED.

I can provide the Authorities with the ID and PASSWORD of both the IDs if they are willing to look into this. And I kindly request the Authorities to please Rate me in the contest Educational Codeforces Round 132 (Rated for Div. 2). As what happened was really unintentional and both of the solutions were mine.

ID Link : https://codeforces.com/profile/ForPracticeDude Solution 1 : https://codeforces.com/contest/1709/submission/165161762 Solution 2 : https://codeforces.com/contest/1709/submission/165164219

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

    You solved A first on that account then proceed to solve B on the other one, not solve A and B both on the practice account. Its unlikely to be accidental, that means you logged out after solving A, logged in to the other one to solve B, once its solved, transfer the answer back. You tested the solution with a fake account which is obviously cheating since its unfair for everyone else

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

    It doesn't work like this you need to share the password of both the accounts too.

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

How to understand question C?

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

    Let's look on sequence $$$s = (??)$$$ First of all, we know that there exist right sequence. Let's find it, $$$s = (())$$$.

    Two sequence $$$s$$$ and $$$t$$$ are different if there is a different $$$i$$$-th symbol, or $$$s[i] \neq t[i]$$$. Now let's try change some symbol from $$$s$$$. Try think this way.

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

can anyone help me find what's wrong in this? submission D

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

I'm not very good at using this feature and mistakenly sent this message the message I really want to send is below sorry please ignore this message

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

Appeal of Educational Codeforces Round 132

Dear Sir or Madam, We got a message from the system after “Educational Codeforces Round 132”:

“If you have conclusive evidence that a coincidence has occurred due to the use of a common source published before the competition, write a comment to post about the round with all the details. More information can be found at http://codeforces.com/blog/entry/8790. ”

So we followed the message to appeal. In fact, we did problem C last year and I did problem D this week coincidentally (The only difference of them is the way of input and output). That is why both of our code is similar to so many others. Some of them I don’t know before, they might have done the same problem before. Some of them are my friends, we have done these two problems together, and some of the code we use is the template we decided on together.

The rules in http://codeforces.com/blog/entry/8790 said this is allowed:

“Solutions and test generators can only use source code completely written by you, with the following two exceptions: 1.the code was written and published/distributed before the start of the round, 2.the code is generated using tools that were written and published/distributed before the start of the round.”

Here are the evidences. They all wrote before the contest 132! (If you need more evidence to judge, please contact me):

C: Your text to link here... (where we find C first)

Your text to link here... (where we learn C first)

D: Your text to link here... (the templates that we wrote and published)

We apologize for the extra work this has caused. But we did not break any rules. The same problems are what none of us want to see. Please correctly judge this special case and cancel the wrong punishment for us. We also want to know what to do next time we encounter the same situation. This is not the first time we meet the same problems in codeforces contest that we have done before. Since we are teammate, we need to make our code style same, use the same template, and work on the problem together (not in contest, when we learn). It always leads to the probability of being punished by mistake when we meet the same problem we have done before. We have already done the problem coincidentally before the contest, spending lots of time to learn how it work, But we still have to spend a lot of time modify code in contest to avoid being punished for mistakes. That sounds very unreasonable! Please judge correctly. Withdraw our wrongful punishment. And tell as what to do next time we meet such a situation. (We also don’t like this situation!). If there is anything else we can do for you, please let us know. Yours, AINgray and DeepLearning-

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

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

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

My use of the code on the blog was found to be a violation. The problem C of this competition is similar to the topic on the OJ of Hangzhou Dianzi University I used the blog https://blog.csdn.net/keshuai19940722/article/details/38391841 code on

Is this a violation or is it acceptable?

written in http://codeforces.com/blog/entry/8790 “Currently, the only reliable proof is the presence of code on the Internet and the presence of the used edition in the cache of well-known search engines. For example, this rule accepts the use of the code from the website http://e-maxx.ru/ if the code was written and published/distributed before the start of the round. With the help of search engine caches, it can be easily shown that such code doesn't violate the rules.”

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

I am getting Tle on problem d on test 11 even after using segment tree. Anyone who can help me

https://codeforces.com/contest/1709/submission/165384286

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

    always remember to add these lines.

    int __FAST_IO__ = []() {
    	std::ios::sync_with_stdio(0);
    	std::cin.tie(0);
    	std::cout.tie(0);
    	return 0;
    }();