Vladosiya's blog

By Vladosiya, history, 2 years ago, translation, In English

Hello! Codeforces Round 826 (Div. 3) will start at Oct/11/2022 17:35 (Moscow time). You will be offered 6-8 problems 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 a rating of 1600 or higher, can register for the round unofficially.

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

You will be given 6-8 problems and 2 hours and 15 minutes to solve them.

Note that the penalty for the wrong submission in this round 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 participant of the third division, you must:

  • take part in at least five 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.

Thanks to MikeMirzayanov for the platform, help with ideas for problems and for coordination of our work. Problems have been created and written by ITMO University team: MikeMirzayanov, myav, Gol_D, Aris, Gornak40, senjougaharin and Vladosiya.

We would like to thank: Mangooste, Ormlis, oversolver, Be_dos, IzhtskiyTimofey, Stefan2417, ace5, BledDest, AbsurdMan, toxabuk, Kniaz, goncharovmike, YTatarin, pashka and great_fortune for testing the contest and valuable feedback. List of testers will be updated.

Good luck!

UPD: Editorial

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

| Write comment?
»
2 years ago, # |
  Vote: I like it +67 Vote: I do not like it

As a tester, I will not participate in this round

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

    As a contestant, I will participate for sure.

»
2 years ago, # |
  Vote: I like it +4 Vote: I do not like it

As a non-tester,I invite everyone to participate in the contest. Good luck

»
2 years ago, # |
  Vote: I like it -6 Vote: I do not like it

You put Div.3 contest on Tuesday and then Div.4 contest on Thursday... unbelievable. But why?

  • »
    »
    2 years ago, # ^ |
    Rev. 2   Vote: I like it +4 Vote: I do not like it

    div. 4 especially for turquoise who will not be able to perform well at the div. 3 and will become green

»
2 years ago, # |
  Vote: I like it +30 Vote: I do not like it

When you see that one of the problem setter is MikeMirzayanov, the excitement goes on another level ;)

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

good contest!!

»
2 years ago, # |
  Vote: I like it +31 Vote: I do not like it

Mom, I am on TV!

»
2 years ago, # |
  Vote: I like it +10 Vote: I do not like it

Hopefully it’s fun!

»
2 years ago, # |
  Vote: I like it +42 Vote: I do not like it

As a toaster, I tasted this round

  • »
    »
    2 years ago, # ^ |
    Rev. 2   Vote: I like it +4 Vote: I do not like it

    tree!!

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

      If you are over 25 and own a computer, you must try this game

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

    sir can you give the hint for the third question of contest how to think for the problem and the basic apporoach should come in our mind it will be greatful if you give me some guidance. Hope for the reply sir thank you

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

BTW I like the cat in the profile picture of Vladosiya.(◠‿◠)

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

ismail-but-noob I hope we finally reach pupil

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Please put strong test cases, I hate to get hacked in div3/4 contests.

»
2 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Best of Luck everyone!Hoping for a positive delta

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Glad to see Div. 3 again after a month.

»
2 years ago, # |
  Vote: I like it +9 Vote: I do not like it

Thanks Vladosiya to arrange a lot of Div3 contest for beginner. Hopefully this contest will be more interesting);

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

According to the rating was rolled back, so I participate in this round will be rated or not?

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

As a pupil, I'm hoping for the Specialist in this round

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

hopefully,I'll become green in this round :)

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

Best of luck everyone

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

Me after solving E

Waiting for contest end
  • »
    »
    2 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Is E really that easy for 2700+ (I am sure it would go above 3000 by the end of the contest) people to solve?
    I can't think of anything at this point :')

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

      maybe memoization will help you

    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it -16 Vote: I do not like it

      Lol 😂 😂 its simple dp problem why r u so dumb

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

        for tourist all problems are easy but for most of people it isn't, i am also too dumb to not able to solve E

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

    Do I need to know dp to be able to solve E ?

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

      It would be much better to solve E with dp. I don't think greedy could solve this problem.

»
2 years ago, # |
  Vote: I like it +22 Vote: I do not like it

Great contest!Congrats to authors!

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

Problem E can be solved with DFS.
my solution: 175655607

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Am I the only stupid one who was trying to solve C without considering the elements should be next together and wasted half of them time on that

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve the problem C?

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

    Brute Force O(n*n*logn)

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

    Note that the sum of each segment needs to be same. So given the total sum as $$$S$$$, we must partition the array into $$$P$$$ segments with sum $$$\frac{S}{P}$$$. Now we can bruteforce by iterating $$$P$$$ from $$$1$$$ to $$$N$$$. (remember to skip when $$$P$$$ cannot divide $$$S$$$)

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

      i did same but still failing, could you please let me know where i was wrong update:- https://codeforces.net/contest/1741/submission/175632745

      int main() { int t=1,i,j,k,n,m,q; cin>>t; while(t--) { cin>>n; int mx=0,ans=0,count=0,ans1=INT_MAX; long long totalsum=0; vector v(n); for(i=0;i<n;i++){ cin>>v[i]; totalsum+=v[i]; mx=max(mx,v[i]); } j=n; long long ch,sum=0; while(j>0){ ans=-1; sum=0; if(totalsum%j==0){ ch=totalsum/j; if(mx<=ch){ for(i=0;i<n;i++){ count++; sum+=v[i]; if(sum==ch){ ans=max(ans,count); sum=count=0; } else if(sum>ch){ ans=-1; break; } } if(sum!=0){ ans=-1; } } } if(ans!=-1) ans1=min(ans,ans1); j--; } cout<<ans1<<endl; }

      return 0;
      

      }

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

    Dichotomous answer and O(n^2)check. So it is O(n*n*log(n))

»
2 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Perfect Div.3 round. Congrats.

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Great problems! enjoyed D and F the most!

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

how to solve E ?

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

    You can use DP.
    Video Solution explaining the DP Solution.

    Hint:
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

My God ,solved E in the last minute

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

    how to solve E?

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

    Same for me here, but with F. Got my submission accepted after the contest had already finished. It was tense.

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

      How to solve F can you please explain. Thanks

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

        Not sure I'm gonna be capable of providing a better explanation or solution than the editorial, but here is what I did:

        1) I sorted all the segments by their left coordinates (their starts)

        2) On the sorted sequence, I grouped all the consecutive segments of the same color

        So using this as an example, after my grouping we would have the following array: {{1,3}, {2}, {5}, {4}}

        3) I looped through every group of segments and for each segment calculated the smallest distance from it to another segment of a different color, for this I checked two things:

        First: The distance of the end of the segment to the start of the first segment on the next group (the segment of a different color with the closest start)

        Second: The distance of the start of the segment to the end of the segment of a different color of a previous group (previous group = starts before the current one) with the furthest end

        To do the second part you have to always keep track of the furthest end so far, which is easy, but for each segment you want to compare it with another segment of a different color, so you have to keep track of the segment with furthest end so far and the segment with the furthest end that doesn't have the same color as that one, doing that you are good and can always apply the method above to calculate the answer for any segment.

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

Missed my first Div3 Ak by 30seconds T_T

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to write question E? I have no idea

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

    look carefully , every element of array may/maynot have the potential of being the right/left endpoint indicating the length of a segment so from each element we can have at most 2 probable segments, so we can get highest 2*n segments ,then the problem comes down to figure out whether you can build an array of n elements using some of these segments which are non-intersecting ; you can do that through dfs which I did

  • »
    »
    2 years ago, # ^ |
    Rev. 2   Vote: I like it +1 Vote: I do not like it

    For every element just check if it can cover the area to it's left and right. If it covers the area to it's left then update the value of that position (dp[i]) with dp[i-left-1] and if it covers the area to it's right then update the value of dp[i+arr[i]] with dp[i-1]. And check for dp[n] at the end. Here is my submission 175628640

»
2 years ago, # |
  Vote: I like it +6 Vote: I do not like it

Loved problem G, but failed to implement during contest.

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Difficulty-wise, which Div3 problem is equivalent to Div2 D?

»
2 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Was thinking dp for E but each state of my dp has a loop so thought time complexity will be n * n. Saw some solution has passed which have done the same.

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

    you have miscalculated the complexity, it's not n * n

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

    Two nested loops is a naive approach and yeah too slow at O(n^2). But if you think about how updates to your dp table are happening there, you can massage inner loop's updates into the outer loop and have just a single loop for O(n) runtime.

    Alternatively think of it as a graph problem, two edges at each index going back/forward, determine if start is connected to the end.

    Really cute problem btw with cute simple solution.

»
2 years ago, # |
  Vote: I like it +11 Vote: I do not like it

problems were cool! thanks to the authors!

»
2 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Pretty Nice Contest! Btw, what is the test that makes solutions for E fail?

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

    just try setting n to 2e5 and all values to 1.

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

      Yeah, I tried that. I think the only solutions that are hacked that way are the ones with no memorization.

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

Got WA in problem E using memorization during contest.
But just after the contest got AC with the same code only after removing the memorization part
why did it not exceed time limit??
submission
upd: hacked

»
2 years ago, # |
  Vote: I like it +4 Vote: I do not like it

Felt like was giving ABC, so yeah nice contest ^_^

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

The cheaters are gonna cheat. There were many videos on YT and many codes where shared among various groups on discord and telegram. This ruins the original rankings and rating of fair participants.

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

    That's Why No of Accepted Submission Increases for Problem C-D

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

can anybody hack my E ?

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

    your code editing is a little bit ugly

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

      my hand writing was ugly in school too , same goes for my code writing

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I use dfs to solve E.But it looks like can be hacked.Can anyone show me the way to hack these solutions?

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

cool F. Really disappointed about not solving it in time(

»
2 years ago, # |
  Vote: I like it -47 Vote: I do not like it

Problem Statement of problem C was bad. For literally around 2 hours and 15 minutes I tried to figure out whats wrong with me. To the author of this problem, you could have written subarray instead of segments. For around 2 hours and 15 minutes I just thought I thought about subsequence. I know it was not completely authors mistake. I should have been more careful. But still you should have avoided the confusing words. Rating goes rrrrrrb :(

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

    The statement is perfectly clear, and illustrated with examples. I have also failed to read questions properly in the past and paid the price, but that is not the fault of the author.

»
2 years ago, # |
  Vote: I like it -38 Vote: I do not like it

F is too easy for its position

»
2 years ago, # |
  Vote: I like it -22 Vote: I do not like it

Is the contest going to be unrated after this?

https://codeforces.net/blog/entry/107879

»
2 years ago, # |
  Vote: I like it +6 Vote: I do not like it

Kudos to authors for clear problem statements.

»
2 years ago, # |
  Vote: I like it +24 Vote: I do not like it

Problem E was a perfect 1D dynamic programming question and the best problem for div3 E.

Overall Great questions. Congrats to authors.

»
2 years ago, # |
  Vote: I like it +1 Vote: I do not like it

another great contest by these legends

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone can give a small hint for D I have enough time but still couldn't make it

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

    you can split the array in 2 parts every time. and you have to check that the elements in first part is always less than second part for every subtree. if not, increase the count and repeat the same process till the leaf of the tree.

    Use recursion for solving the problem.

    You can take reference from my code-> https://codeforces.net/contest/1741/submission/175603313

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

    In one way, if you know merge sort, you basically know the solution for this problem.
    Would recommend you to learn the idea of merge sort from GFG or someplace else and try it on your own.
    Just for reference 175631361

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

    Think of divide and conquer technique.

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

Did anyone else use min cost max flow on G? I think it works in $$$O(km\log m)$$$.

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

    That's insane, do you think you can describe your approach?(I only managed to solved it with bitmasks)

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

      For a vertex $$$v$$$ in the original graph, let there be an entrance node $$$2v-1$$$ and exit node $$$2v$$$ in the flow graph. The source is vertex $$$1$$$ (the entrance node for vertex $$$1$$$). Let $$$2n+1$$$ be the sink. The edges are:

      • $$$2v-1\to 2v$$$ with capacity $$$\infty$$$, cost $$$0$$$ for $$$1\leq v \leq n$$$.
      • $$$2u\to 2v-1$$$ with capacity $$$\infty$$$, cost $$$0$$$ for an edge $$$u, v$$$ in the original graph if $$$d(v) = d(u)+1$$$ (where $$$d$$$ is distance from $$$1$$$).
      • $$$2v-1 \to 2v$$$ with capacity $$$1$$$, cost $$$-x_v$$$ where $$$x$$$ is the number of friends without cars at vertex $$$v$$$, for $$$1\leq v\leq n$$$.
      • $$$2v\to 2n+1$$$ with capacity $$$y_v$$$, cost $$$0$$$ where $$$y_v$$$ is the number of friends with cars at vertex $$$v$$$, for $$$1\leq v\leq n$$$.

      The answer $$$k$$$ plus the minimum cost flow of this graph. (Or maybe I'm wrong and you can hack me.) Stop at $$$k$$$ units of flow instead of a maximum flow because the minimum cost will be reached within $$$k$$$ units. Otherwise, the time complexity is $$$O(nm\log m)$$$, I think.

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

        Sounds nice, if I got it right it is computing the "maximum cost maximum flow" to find out the maximum number of friends that can be driven and then subtract this from K to get the answer. The transitions are also pretty logical, I don't know if I can find any counter-example. Anyway, I would have never thought of modelling it with a flow chart, gg:)

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Hi, Can someone help with F? I saw some solutions with segtree, but they were difficult to understand.

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

    Try think this way: there is no colors in this problem, task is the same but without segment colors.

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

    let's assume that the segments are sorted in increasing $$$l$$$. You can split the problem into two parts -

    i) find the greatest $$$r[j]$$$ ($$$j$$$ < $$$i$$$) among all $$$l[j]$$$ which are less than $$$l[i]$$$ and with different color than $$$color[i]$$$

    ii) find the least $$$l[j]$$$ ($$$j$$$ > $$$i$$$) among all $$$l[j]$$$ greater than $$$l[i]$$$ and with different color than $$$color[i]$$$

    Let's see how we can solve the first part. We can store an array $$$mx$$$ where $$$mx[k]$$$ indicates the greatest $$$r$$$ value for a given color $$$k$$$. Store this $$$mx$$$ array in a segment tree so that we can retrieve the maximum value of $$$mx$$$ with updates. Now, for this case, you may wonder why you would actually require a segment tree and not just maintain a set or something similar. The thing is, if we are at the $$$ith$$$ segment, the maximum $$$r$$$ value of any segemnt $$$j$$$ ($$$j$$$ < $$$i$$$) might be of color similar to that of the $$$ith$$$ segment. In which case, we have to find the max $$$r$$$ value of a color which is not that of the $$$ith$$$ segment color. Say the color of the $$$ith$$$ segment is $$$k$$$. We can do this by updating $$$mx[k]$$$ in our segment tree to some very small number and then finding maximum in segment tree and later resetting $$$mx[k]$$$ to what it was initially. Ie make sure that $$$mx[k]$$$ is ignored in our max segment tree.

    Now, as we move through all $$$i$$$ in increasing order of $$$l$$$, we can easily figure out the maximum $$$r$$$ value of a different color using our segtree (explained above). Once we find this maximum $$$r$$$, we we can update the answer for this segment to $$$max(0,segment[i].l-max_r)$$$

    The second part of our problem can be solved in an almost similar way, except we would require a minimum segtree to find the minimum $$$l$$$ value of a segment $$$j$$$ ($$$j$$$ > $$$i$$$) of different color. Alternatively,we could use the same segment tree (max segment tree) except store values in the segment tree as (-(actual value)), now, the abs of the max value will be the least $$$l$$$ value. Once we find this minimum $$$l$$$, we can update the answer for this segment to $$$max(0,min_l-segment[i].r)$$$ We'd also have to make some minor changes like redefining $$$mx[k]$$$ to minimum $$$l$$$ value for a given color $$$k$$$

    submission

»
2 years ago, # |
  Vote: I like it +15 Vote: I do not like it

Awesome round!!! Keep it up creators! ^D

»
2 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Great round

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Someone please hack my submission for E. 175641835

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone explain DFS approach to solve problem E.

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

    I think DP solution much easier to understand

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

    But DP idea almost like DFS solution. So let me tell you the DP idea first and then DFS

    1) DP solution. Let $$$dp_i$$$ be the True, if the array $$$b[1..i]$$$ can be build by array $$$a$$$ and False otherwise. Our base is $$$dp_0 = True$$$. Then, if $$$dp_{i-1}$$$ is True that means we can build array $$$b[1..i-1]$$$, that we have to do with $$$b_i$$$? Let's say it's the count of numbers in next subarray, we set the $$$dp_i+b_i = 1$$$. And if $$$b_i$$$ was the counter in previous subarray we need to check if we can build array $$$b[1..i-b_i]$$$. The answer is in $$$dp_n$$$ now.

    2) DFS solution. Let's now say from index $$$i$$$ we can go to indexes $$$i+b_i$$$ and $$$i-b_i$$$. Because $$$b_i$$$ is count of numbers in next or previous segments. Let's call this edges and $$$i$$$ as nodes. We have to be able to move from node $$$1$$$ to node $$$n$$$. The answer is $$$dfs(1)$$$ or $$$dfs(n)$$$ now.

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

      We can use the visited array to our advantage in the DFS solution, we can simply start DFS from 0 and then check $$$vis[n]$$$ (basically right after the last cell). If the string is valid $$$vis[n]$$$ will be true, otherwise it will be false.

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

Great problems but weak test cases for E killed me.

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

Nice contest, thanks! I think d and g are pretty nice.

I was originally kind of annoyed by F but i looked at some other people's submissions after contest and they're pretty cool, so that was mostly my fault for being an idiot.

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

How to approach D anyone?

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

    Its a MergeSort problem, you just have to keep track of the left and right part for each segment using a 2d array and then on each iteration see if you can merge i and i+1.

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

      Also you can track the first element of the left and right subsegment and swap them if left is greater than right. You don't have to swap the whole array, and this way you get an $$$O(n)$$$ time complexity due to $$$\Sigma_{k=0}^{n-1}{2^k} = 2^n-1$$$ and $$$n$$$ was in the form of $$$2^k$$$. If the absolute difference of the two elements are equal to the difference of the indices for each step, the tree is valid. otherwise the answer is $$$-1$$$

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Why E no was with so weak pretest? Forgot to use memorization.

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

    You can survive only by using dp.Memorization is also not enough if you use dfs.

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

      I think your dfs got TLE hacked because the time complexity was $$$O(V^2)$$$ due to scanning for segments on every index. You can enumerate segments beforehand, this will lead to a maximum of $$$2V$$$ edges, and worst time complexity is $$$O(V)$$$ if you do this

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

        Why for E, my dfs + memo got hacked as TLE? https://codeforces.net/contest/1741/submission/175640727 method is called getCanSent the memo map has at most 2n entries.

        • »
          »
          »
          »
          »
          2 years ago, # ^ |
          Rev. 3   Vote: I like it -11 Vote: I do not like it

          Well, I can't exactly know where the hack happened. But your code will (and did) work very slow, due to multiple reasons. Reasons may include hash tables being simply slow, and the recursion leading to a deep copy.

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

          Your transition can potentially take O(N) time. And you have N states, so it's actually a O(N^2) solution.

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

I find G easier than F and I've hacked my friend DitaMirika and another participant ha___il for their carelessness.

detail: Their time complexity can be as large as $$$O(2^n)$$$

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Why for E, my dfs + memo got hacked as TLE? https://codeforces.net/contest/1741/submission/175640727

method is called getCanSent

the memo map has at most 2n entries.

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

F is too hard for me :(

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

why this 175643343 n^2 solution is passing for problem E?

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

    I tried to submit it again and it is giving TLE now but in standings it is an accepted solution even after system testing :(

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

      SysTests aren't done yet as far as I know. Been looking for hacks and Systests didn't go off since hacking phase ended, it probably will start soon.

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

        Oh yes, my bad. That solution will get caught in system tests then.

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

      when will system test start?

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

        Most likely soon, maybe an hour or two later at most. As far as I have seen, it doesn't take much longer usually.

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

          Usually its written there that "system test pending". but its not the case for now.

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

            I have noticed it in previous rounds with hacking phases as well. In Div2/1/Global rounds it gets 'Pending' status but not in the Div3/4/edu as far as I have noticed. It might change a minute or two before the SysTests start, but it's marked as completed mostly.

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

              Hey i can only message 1 time in 10 minutes. but it looks like this is not the case for you why?? and i think some things should be common in all the contest not like this happens in this that happens in that

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

                I guess because you got -73 contribution, so CF is trying to revoke your 'privileges'.

                Well, it def should be, but I guess there are some technical difficulties, like this one isn't pending in SysTests yet, but analyzing hacks to add in SysTests. Once it's analyzed, it will be SysTested. I definitely am not the best person to ask this to, but this might be the case.

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

                  If my interpretation of this experience is correct, it's definitely not a direct correspondence to contribution. I believe it is some "rate limit" happening, sometimes it goes to 4 messages every 60 minutes. Getting it down to 4/60 had nothing to do with contribution for me though.

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

May I ask whether I would be rated for this round or not? By the rules stated in the announcement, I am not a trusted participant yet(since I took < 5 rated rounds). But according to this line "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.", I assume I should be rated for this round. Thanks in advance to your answers

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

    As far as I know, it should be rated for you.

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

      But it appears in the unrated contests in my profile page haha

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

        It's because the rating changes isn't out yet, so it's marked as unrated for everyone yet. It probably will take a few more hours to update.

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Does hacks improve delta in div3/div4/educational round ? if yes, how ?

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

    As far as I know, in Edu Div2 rounds you get +100 points for successful hack and -50 for unsuccessful. So yes, in Edu Div2 you improve your score.

    In Div3/4 I don't think that is the case, since it's not based on scores but amount of solved problems.

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

      EDIT:

      Well, I guess I messed up with Div2 edu and standard Div2 round, but downvoting instead of correcting and answering the question isn't really helping a lot.

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How do people target solutions for hacking? Is it random?(just look at people's solutions and try to find vulnerabilities) or it there some other way?

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

    I think they find a general case which might hack some of the approaches, then check for that specific problem if it's implemented via the approach you know how to hack. Not certainly sure tho.

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

Yesterdays contest was good Though I am going to get a negative But it was fun :) :) :) :)

»
2 years ago, # |
  Vote: I like it +4 Vote: I do not like it

As a Competitor, I competed this round.

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

My rating is 935 and i participated in Codeforces Round #826 (Div. 3) but its showing unrated for me and i haven't got any ratings. Can anyone please help me out because in notice its also written that " 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."

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

    Ratings didn't update yet, so it's marked unrated until SysTests finishes. Once SysTests will be finished, ratings will be calculated, updated and then marked as rated.

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

    The ratings haven't changed yet, so it shows unrated for everyone.

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

My rating has still not changed yet, is it not updated for everyone or is it only me.

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

As a newbie, I tried to implement the bitmask idea in problem G but fail in test 3.

I am really desperate. Would you please debug it?

https://codeforces.net/contest/1741/submission/175747503

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Codeforces Language Picker -- chrome extension to fix codeforces language picker.

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

hi can anyone tell me what's wrong with my approach for the e problem, i have written a recursive dp code for that . https://codeforces.net/contest/1741/submission/175681998

»
2 years ago, # |
  Vote: I like it +1 Vote: I do not like it

When ratings will be updated?

»
2 years ago, # |
  Vote: I like it +1 Vote: I do not like it

When will the rating points will be added to our accounts? Thanks.

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

Why the rating not update yet ???

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Is it just me or you think it's taking more than usual for ratings to change ?

»
2 years ago, # |
  Vote: I like it +1 Vote: I do not like it

My rating has not changed after this contest . Any reason why ?

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

waiting for the updated rating

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

MikeMirzayanov Vladosiya senjougaharin

I am sorry for commenting this , but my solutions were skipped because I used a code that was published on geeksforgeeks from 2 months ago , and the code is found in my template , used it with some modification to solve C , and it wasn't the first time to use the same code to solve similar problems during practice

link of this code

link of my submission

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

    Using reference code for template and directly copy pasting solutions are different bro. I don't think your punishment should be rolled back. Even it is a common problem you are supposed to do at least the solve part by yourself.

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

      as i mentioned bro, these functions in my template are the ones that i learn during practice, i didnt say that i copy paste solutions, i only use functions from my template if i wrote it before, or i write a new one and add it to my template, i dont see that both functions(from the webstie and the one in my template) are the same 100%, i did the modification for this problem, but when i add it to my template i add the non-modified one

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

        I know you are not a cheater. Mike can consider your case specially if he has that much time. But in general most of the cheaters would give this excuse that code was already public on many sites bla bla... Plagiarism checker is only run over the codes that are submitted in contest time. So not in this contest but also in big contests like OI or others if you get caught for this reason I don't think you would be forgiven. So practise to code yourself even if the whole code for the problem already exists!!

»
2 years ago, # |
  Vote: I like it +1 Vote: I do not like it

When will the rating update?

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

    Cheaters are being caught now, so should be fairly soon, within the hour is my guess.

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

When will the ratings roll out? :(

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

why Div 3 unrated Until now

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Why it is taking to much time to update ratings?

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

    It is better if more time is needed to update the ratings. My rank for this contest has been steadily rising due to the removal of cheaters.

»
2 years ago, # |
  Vote: I like it +4 Vote: I do not like it

Rating is now updated! Congratulations to myself1
Screenshot-2022-10-12-215448

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

Why are Common Standing Seat and Rating Changes seat different? Example- Common standing 3600 Rating changes 4300

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

    Common Standings include only trusted participants, whereas there are more rated participants than that

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone tell me why this code Time limit exceeded on test 40? https://codeforces.net/contest/1741/submission/176144895