EJIC_B_KEDAX's blog

Codeforces Round #881 (Div. 3)
By EJIC_B_KEDAX, history, 10 months ago, translation, In English

Hello, Codeforces!

On Jun/20/2023 17:35 (Moscow time) Codeforces Round 881 (Div. 3) will start.

You will be offered 7 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 7 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.

Problems have been created and written by: zwezdinv, EJIC_B_KEDAX, molney, Sokol080808, meowcneil, Vladosiya.

We would like to thank:

  1. Vladosiya for coordinating the round.

  2. MikeMirzayanov for Polygon and Codeforces platforms and testing.

  3. tute7627 for red-black testing.

  4. ace5, sevlll777, oursaco, lightseba, gmusya, pavlekn, vrintle, tolbi for yellow testing.

  5. diskoteka, moonpie24, SashaT9, shell_wataru, MGod, Phantom_Performer, tarattata1, alex.kudryashov, Restricted, sdyakonov for purple testing.

  6. Alex239, MrEssiorx, olyazyryanova, marzipan, Pa_sha, Rudro25, azureglow, IHateGeometry, ivan.alexeev, krigare for blue testing.

  7. Guevara74, ctraxxd for cyan testing.

  8. sahal, exhausted, viteli, prohamer80 for green testing.

Good luck!

UPD: Editorial.

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

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

As an author, I recommend you to participate in it.

→ Reply
  • »
    »
    10 months ago, # ^ |
    ← Rev. 2   Vote: I like it +9 Vote: I do not like it

    thanks. I wish all participants get + rating and enjoy

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

    As a tester, this is my first contest. Thanks to the authors and coordinators.

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

    Matching profile pictures with molney when? :wink:

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

    Thanks.. I wish everyone will participate..

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

    Hey , I have been flagged by system even though I wrote the entire code .Please look into this . Sol ing till d gave me negative rating i don't get it :(

    → Reply
»
10 months ago, # |
← Rev. 3   Vote: I like it +12 Vote: I do not like it

wow !! Vladosiya is back :)

→ Reply
»
10 months ago, # |
  Vote: I like it +4 Vote: I do not like it

Hope so it would not be like the CF round 880

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

Wish this contest is not bad like Round 880.

→ Reply
»
10 months ago, # |
  Vote: I like it +69 Vote: I do not like it

As a tester, this round is bombastic.

→ Reply
»
10 months ago, # |
  Vote: I like it +51 Vote: I do not like it

As a tester,

I tasted some apples I tested some cool problems.

→ Reply
»
10 months ago, # |
  Vote: I like it +7 Vote: I do not like it

first unrate div3,GL&&HF for everyone:)

→ Reply
»
10 months ago, # |
  Vote: I like it +4 Vote: I do not like it

and one more thing,how can i become a tester

→ Reply
»
10 months ago, # |
  Vote: I like it -7 Vote: I do not like it

If you have time you should write this round! Because it give you a lot of rate if you are good in programming. Please like it!

→ Reply
»
10 months ago, # |
  Vote: I like it +4 Vote: I do not like it

As a Tester,

Spoiler
→ Reply
»
10 months ago, # |
  Vote: I like it +16 Vote: I do not like it

As a tester, you must participate! Problems are interesting!

→ Reply
»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

hope to became pupil

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

Waiting for this round. Best of luck everyone

→ Reply
»
10 months ago, # |
  Vote: I like it +1 Vote: I do not like it

As a participant, I hope to become yellow one day.

→ Reply
»
10 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Div 2?????!

→ Reply
  • »
    »
    10 months ago, # ^ |
    ← Rev. 2   Vote: I like it -12 Vote: I do not like it

    I thought I was misremembering/misreading things! Sat down to write the Div. 2 -> It's a Div. 3 -> Wrote it anyway -> NO REGRETS, GREAT ROUND.

    → Reply
»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

As a tester, blablabla...

ahmet23 orz!..

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

    How you did it? The tag is showing lgm but he us expert..

    → Reply
»
10 months ago, # |
  Vote: I like it +29 Vote: I do not like it

I think there is a mistake in the typo, it should be Codeforces, not Codefoces, missing a "r" letter

→ Reply
»
10 months ago, # |
  Vote: I like it +11 Vote: I do not like it

As a friend of the tester, I don't know good this round, or not

→ Reply
»
10 months ago, # |
  Vote: I like it +6 Vote: I do not like it

As a tester, I recommend you to take the contest :)

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

Wish this isn't bad as 880 ;-;

→ Reply
»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

As a Participant looking forward for a good round.

→ Reply
»
10 months ago, # |
  Vote: I like it +29 Vote: I do not like it

As a blue tester, I may say that I am a blue tester.

→ Reply
»
10 months ago, # |
  Vote: I like it +85 Vote: I do not like it

→ Reply
»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

hope the problems are well balanced

→ Reply
»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Best of luck to everyone .

→ Reply
»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I hope can solve four or five problems

→ Reply
»
10 months ago, # |
  Vote: I like it +5 Vote: I do not like it

hope to get CM today! :D

→ Reply
»
10 months ago, # |
  Vote: I like it +13 Vote: I do not like it

As a non-tester I will test this round during contest.

→ Reply
»
10 months ago, # |
  Vote: I like it +1 Vote: I do not like it

I'll test this round at 20:05 :-)

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

Grey Tester missing !!

→ Reply
»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

omg a div 3, I'm so glad!

→ Reply
»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

i need to esceb from newbi rank

→ Reply
»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

As a participant, I hope to become blue one day.

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

    update：I have solved A~F1, so I can become a blue name.

    → Reply
»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can I become expert today?

→ Reply
»
10 months ago, # |
  Vote: I like it +4 Vote: I do not like it

→ Reply
»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Unfortunately, no gray testing!

→ Reply
»
10 months ago, # |
  Vote: I like it -6 Vote: I do not like it

It's a good one, nothing like 880 :)

→ Reply
»
10 months ago, # |
  Vote: I like it -9 Vote: I do not like it

is this a div4 round?

→ Reply
»
10 months ago, # |
  Vote: I like it +16 Vote: I do not like it

contest of trees

→ Reply
»
10 months ago, # |
  Vote: I like it +28 Vote: I do not like it

E and F are really good problems.

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

    How to solve E?

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

      binary search on the answer

      once one of the arrays is beautiful it will remain beautiful, so we can use binary search. to check the condition after some number of changes, build the array and check the segments with prefix sums.

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

      I used binary search to search whether I can get a beautiful array using the first m queries. Inside the binary search you can just maintain a prefix sum with the first m queries each time to calculate the number of 1's in a segment quickly, so you can know if there is a beautiful array if pre[r] — pre[l — 1] > (r — l + 1) / 2.

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

      E can be solved by binary search.Initialize lower and upper bound of binary search as 1 and q and find whether for a given 'id' is there any beautiful segment.Since each query element is between [1-n],store value of queries [1-q] in some data structure and check for each segment whether there are more than half the length of values present.

      Here's my submission- 210424751

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

    How to do E?

    → Reply
    • »
      »
      »
      10 months ago, # ^ |
      ← Rev. 3   Vote: I like it 0 Vote: I do not like it

      I solved it with binary search. For each iteration, maintain an ordered set of all the queries already processed. Then iterate over each segment and check how many numbers are processed using order_of_key. You can now check whether any of the segments contain more ones than zeroes. You don't have to use ordered set, but it was the first implementation that came to my mind.

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

    yes you are correct, I was able to solve F1 but couldn't solve E

    → Reply
»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Long Long anyone ?

→ Reply
»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

friendly contest (●'◡'●)

→ Reply
»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

friendly contest！！！！！！

→ Reply
»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone tell me why my solution for D gave wrong answer for testcase 4

`

def solve(num, graph, diction): if len(graph[num])==0: diction[num]= 1 return 1 if num in diction: return diction[num] ans=0 for item in graph[num]: ans+= solve(item, graph, diction)

diction[num]= ans
return ans

for _ in range(int(input())): 

n= int(input())
# a, b, c, k= map(int, input().split())
# arr= list(map(int, input().split()))
# arr2= list(map(int, input().split()))
# a, b, c, k= arr[0], arr[1], arr[2], arr[3]
graph = [[] for i in range(n+1)]

for i in range(n-1):
    a, b = map(int, input().split())
    graph[min(a, b)].append(max(a, b))
    # graph[b].append(a)

diction = {}
# ans= solve(1, graph, diction)
# print(graph, diction)
q= int(input())
for i in range(q):
    a, b = map(int, input().split())
    ansa= solve(a, graph, diction)
    ansb= solve(b, graph, diction)
    print(ansa*ansb)
# print(diction)

`

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

    1 4 1 3 3 2 4 3 3 1 1 3 3 2 2 Check this test case

    → Reply
    • »
      »
      »
      10 months ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      Did you mean this?

      1
4
1 4 
1 3 
3 2
4
3 3
1 1
3 3
2 2

      Result:

      1
4
1
1
      → Reply
      • »
        »
        »
        »
        10 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Same problem for me, wrong ans for test case 4. And I'm getting the same result at you (1 4 1 1) for the above test case. Did you find a solution for it yet?

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

          Yes i got the solution. I thought of this but for some reason i did not implement it during contest. I initially used the same logic as yours but it wont work. In the question is states If a vertex u has a child, the apple moves to it (if there are several such vertices, the apple can move to any of them).

          It wont follow the linear order.

          For example:

                                           1
                           2           6
                       3                   7
                    4      5

          In this example there are three leaf nodes, 4, 5 and 7

          if an assumption is at (4, 2), the pairs can be: (4, 4), (4, 5), (4, 7)

          From 2, it can go to any node, so it went 1 -> 6 -> 7. and also 3 -> 4 and 3 -> 5

          This is what i wrote the code for.

          I had to use c++ because with python i got stack overflow and runtime error.

          Hope I am right on this one

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

        No, the problem is that you are assuming that for every edge, the parent is the one whose value is the lowest, but it isn't. So when you try to traverse the graph, it doesn't work as planned, because it's disconnected.

        → Reply
    • »
      »
      »
      10 months ago, # ^ |
      ← Rev. 3   Vote: I like it 0 Vote: I do not like it

      Sorry for the bad test case, check this:

      1 
4 
1 4 
4 2 
4 3 
2
1 1 
4 4

      The output must be: 4 4

      If we change the position of the node 4 with the node 2, it will give us the right answer:

      1 
4 
1 2 
4 2 
2 3 
2
1 1 
2 2
      → Reply
      • »
        »
        »
        »
        10 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I kinda improvised from your previous testcase, and found the solution. THANKS! Feeling terrible for not implementing an easy logic

        → Reply
»
10 months ago, # |
  Vote: I like it +2 Vote: I do not like it

Finally a nice and easy contest after a string of hard ones

→ Reply
»
10 months ago, # |
  Vote: I like it +9 Vote: I do not like it

Although E is binary search, technically an easy sqrt solution exists in n^1.5 by processing queries n^0.5 at a time.

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

    can you explain this solution? Thanks

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

      Just like binary search, the solution is based on using prefix sums to check if any segment has been satisfied.But we use up n^0.5 queries at a time instead of checking prefix sums every query like brute force. If we see any segment satisifes after the current bacth of n^0.5 queries we can just check all those individually. Otherwise we skip and start with the next batch.

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

        Is this a specific algorithm? If yes, can you provide me with a reference article or a similar problem?

        → Reply
»
10 months ago, # |
  Vote: I like it +17 Vote: I do not like it

How would F2 be solved? Initially I thought it was continuing the idea of max/min subarray sum but on arbitrary paths, and that we could use binary lifting to find the LCA, then to find max subarray sum on path from u to v, take best of the three cases: u to LCA, v to LCA and some path that crosses the LCA. But didn't find a good way of doing it. Am I on the right track or is it something completely different?

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

    You are right! That's how I tackled this problem, at least. You just need to come up with ways to merge the binary lifting answers.

    Calculating the total sum, best (max/min) sum, best prefix sum and suffix sum on the path will certainly be useful.

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

      Ah, I see. I keep forgetting that binary lifting can be used to store information other than the 2^k-th ancestor.

      → Reply
»
10 months ago, # |
  Vote: I like it +21 Vote: I do not like it

As a participant, I enjoyed this contest a lot, especially the F2 problem! :D

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

    please explain your solution for problem F.

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

      F2 (and F1):

      First of all, we pre-build the tree and answer all the "?" queries later.

      Let's note that, if we know the min and max values between all the subsegments on the path, then all other in-between values are reachable. For example, if there are subsegments with cost -5 and 7, then there always is at least one subsegment with cost 3. Why? Because when we add a new node to the path, the cost always changes by 1, there are no jumps. We can't get from 0 to 3 without going through 1 and 2 first, for instance.

      All we need to do is to calculate these min and max values quickly, and then it's a simple check that minn <= k <= maxx.

      Now, when faced with a "?" query, let's find the LCA (Least Common Ancestor) of u and v. Where can the min be? Well, it can just be somewhere on the first path (u -> LCA), or on the right one (LCA -> v). But perhaps it touches both, meaning it's the best suffix of (u -> LCA) + x[LCA] + the best prefix of (LCA -> v) (OR the suffix of (v -> LCA), since it's the same thing, just reversed).

      All we need to find these values is some binary lifting. For each up[v][power], you'll need to precalc the total sum on the segment, the best subsegment sum, best prefix and suffix sum.

      I hope this makes sense. :')

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

        Oh my God! I wrote HLD on it...

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

          That's one of the first things that came to my mind, too! Gladly, I didn't think about it too hard and came up with a different idea, instead. ...mainly because I'm inexperienced with HLD.

          → Reply
          • »
            »
            »
            »
            »
            »
            10 months ago, # ^ |
            ← Rev. 2   Vote: I like it 0 Vote: I do not like it

            Usually, if I find a solution, I implement it, even if it is a treap in Div.2 C

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

              Oh, absolutely. But just thinking "HLD, maaaaybe?" wasn't exactly enough for me to start writing the solution. :)

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

                I think it is a good problem to implement HLD. And you can also speed up it using Disjoint Sparse Table instead of Segment tree

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

                  For me, the HLD solution gave TLE's despite my best attempts to optimize it. I later switched to the sparse tables approach.

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

                  I tried to find mistake for a while. You should use links to vector arr in init_tree and dfs_labels. But even after adding links, the solution gets TLE.

                  May be you have a problem on multiple test cases — I don`t know.

                  My solution passed without any problems: 210446339

                  May be, you should remove vectors and structs to improve the constant of solution.

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

                  I was using galen colins template, havent written my own template ever .. perhaps I should try doing it.

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

        I have exactly the same idea, but i was unable to implement the solution..very sad

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

        Can you guys please provide me some practice problems where one has to keep multiple factors as attributes of a node and has to figure out ways to merge them in binary lifting and HLD ? I have solved such problems in segment tree but somehow I could not figure it out for this problem, or for example in another problem where you had to find the longest arithmetic progression in a weighted tree.

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

    Really? F2 is just 2 standard well known techniques mashuped together. What part was nice?

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

      I liked the implementation. Also it's a great introduction for binary lifting in my opinion.

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

        belongs as a cses task not a codeforces problem (and max subarray sum exists as cses problem too just not on tree)

        0 thinking (i took ~2mins to come up with the solution) and then lots of implementation (if you are doing from scratch like me, ~20mins), when the problem itself is standard. [i have 2nd solve on the problem btw]

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

          International master for a reason

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

            i'm sorry, i didn't mean for it to be a flex, i just do not like putting standard problems in cf rounds

            → Reply
»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone tell me why memory limit exceeded on this submission https://codeforces.com/contest/1843/submission/210459020

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

    this is a mult-testcase problem, you need to clear the memory for your graph, you keep adding without deleting. graph[a].push_back(b); graph[b].push_back(a);

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

      Also need to use links to vectors instead of whole vectors in dfs

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

        dont know how to do that but i guess i should have used global vector and resized it later.

        → Reply
        • »
          »
          »
          »
          »
          10 months ago, # ^ |
          ← Rev. 2   Vote: I like it +9 Vote: I do not like it

          Yes, or static array. Or you can do this using & before vector's name:

          vector<bool> &used

          And do this for all vectors in dfs. You have already use link in one of vectors.

          → Reply
          • »
            »
            »
            »
            »
            »
            10 months ago, # ^ |
            ← Rev. 2   Vote: I like it 0 Vote: I do not like it

            yeah but i dont know how to pass vector int graph[] as a reference

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              10 months ago, # ^ |
              ← Rev. 3   Vote: I like it 0 Vote: I do not like it

              Possible way is to make graph vector<vector<int>>

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

                Yeah that makes sense.

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

    It is not necessary to pass large objects to the function, they are copied in each function call. Your function is called O(n) times and we get O(n *n) memory, which is not good.

    → Reply
»
10 months ago, # |
  Vote: I like it +8 Vote: I do not like it

Can you solve D by only using BFS? or would get TLE and have to use DFS?

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

    Why do you need BFS for D? Either way, both will work in O(n + m), so it doesn't really matter.

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

      For test case 6, it was getting maximum recursion depth exceeded in dfs.

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

        Huh. Uh, something-something, blame Python?

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

          Blaming no one, just learn the other way after checking the solution of others. Thankfully that i got error.

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

            Great mindset!

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

              But not of use, i am stuck at the rating. Any advice or guidance to improve my rating?

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

                did you implement bfs ?

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

                Learning good themes is always great, but lots of practice is at least as important, even more so for the first few rating groups, provided you know the basics. Just keep going and don't give up. Practicing keeping composure during contests is useful, too. Don't rush too much, don't worry about your rating, don't give up, even if the problem seems too tough, etc.

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

                  Thanks a lot !!

                  → Reply
»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can F2 be solved with persistent segment tree?

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

    I only know that E can: 210400778

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

      Didn't solve E but I suspect segment tree on it is an overkill.

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

        It is an overkill, but overkilling is often better than overthinking during contests. :)

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

          But that undermines the whole point of mathematicians coming up with efficient and (not always) beautiful solutions for problems =)

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

            Bu-u-uut that undermines having to write more bad code! :)

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

        Oh I didn't know binary lifting and merging range like segment tree was a thing, I guess that totally overkilled the problem lol

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

        If a person has written an algo many times, its implementation becomes simpler for him than thinking about easier solutions.

        → Reply
»
10 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

As far as I know , all of the sample tests don't cost any penalties when getting WA or RE and so forth , but why problem F has cost me a penalty when I got WA in test 2 although it's included in the sample test . IS it a problem with the system testing or anything else ? thanks in advance.

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

    Even if there are multiple sample tests only the first one counts.

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

      It seems strange that there are several separate samples in a task with multitest.

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

    Unfortunately, as far as I know, this has always been the case.

    → Reply
»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Tasks E and F1 are very interesting, and the condition is very incomprehensibly written in task D. It also seems to me that there is too big a gap between D and E. It was too difficult to guess the key idea in E for its place in div3.

→ Reply
»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Nice contest, problems were from various topics, and their difficulty and overall time to solve were adequate

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

I read A statement wrong. Then, 10 minutes later I read it wrong again. 40 more minutes later, I read it wrong yet again. Finally, 80 minutes after the beginning of the contest, I read it right.

→ Reply
»
10 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

in d i took the count of leaf nodes reachable from u and v . their product should have been the answer but what is wrong with this one which failed on test case 4

https://codeforces.com/contest/1843/submission/210448804

→ Reply
  • »
    »
    10 months ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    The result shows "Accepted"

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

      edited , my original implementation and logic gave wa on tc 4

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

    what was the problem? I am also getting wrong answer on test4.

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

    same with me. I am unable to understand why i am getting was on 4 You can check my code above

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

    To those who are failing on test case 4 on problem D, it's probably because you assumed that we only traverse from low to high. But, this is not correct. ONLY THE ROOT NODE IS 1. Every other node number can be arbitrary up to n.

    → Reply
»
10 months ago, # |
  Vote: I like it +23 Vote: I do not like it

treeforces

→ Reply
»
10 months ago, # |
  Vote: I like it +15 Vote: I do not like it

I loved question F1!

Don't know if it was intended, but running Kadane's algo on a tree was very satisfying.

→ Reply
»
10 months ago, # |
  Vote: I like it +8 Vote: I do not like it

Any ideas on E , I was really stuck there for a long time but couldn't think anything

→ Reply
»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

AH YES!!! THE OG div3 contest for newbie/beginner coders who are well versed with 'trees' right??? disappointed.

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

    Besides F, D was the only graph problem...

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

E: We let t[x]=inf initially, and if we a[x]=1 on the i-th query, we let t[x]=i. Then if the segment [L, R] become beautiful at the i-th query, i will be contained in t[L, R], and there will be at least floor((R-L+1)/2) elements smaller than i. so after we sort t[L, R] increasingly, the (1+floor((R-L+1)/2))-th element will be i. So we can solve the problem by range query for k-th minimum element on t[1, n]. We can answer the queries by Mo's algorithm, in which we need to maintain a subset of [1, q]. Using sqrt decomposition we can add/remove an element in O(1) and query k-th minimum in O(sqrt(q)), so we can solve the problem in O(n*sqrt(m)+m*sqrt(q)).

F1: Assume the minimum sum of weight over all subsegments of path (u, v) is m, and the maximum sum is M. Then if sum(L1, R1)=m, sum(L2, R2)=M, when we change the subsegment (L, R) from (L1, R1) to (L2, R2) by extending or reducing the length by 1 each time, the sum of weight will be increased by -1 or +1 each time, so the sum of weight can be any integer between m and M. Therefore, we only need to find m and M for path (u, v). When u=1, we only need to check for path (1, v). Let p be the parent of p, define M(v)=the maximum sum of weight over all subsegments of path (1, v), suf(v)=the maximum sum of weight over all suffixs of path (1, v), we have suf(v)=weight(v)+max(0, suf(u)), M(v)=max(M(p), suf(v)). Similarly we can calculate the minimum sum m(v).

F2: When u can be any nodes on the tree, we need to look for what if we concatenate 2 paths. Let M=the maximum sum of weight over all subsegments, suf=the maximum sum of weight over all suffixs, pre=the maximum sum of weight over all prefixs, sum=the sum of weight over all nodes on the path. Then if we denote (L, R) be the concatenation of path L and R, we have:

(L, R).sum=L.sum+R.sum

(L, R).M=max(L.M, R.M, L.suf+R.pre)

(L, R).pre=max(L.pre, L.sum+R.pre)

(L, R).suf=max(R.suf, R.sum+L.suf)

So we can merge information of any 2 paths. Therefore, we can solve the problem by binary lifting: Let infos[r][u] be the information of the path from u to the (2^r-1)-th ancestor of u, and parent[r][u] be the (2^r)-th ancestor of u, we can find LCA(u, v) and merge path from u to LCA(u, v) and the reverse of the path from v to the child of LCA(u, v).

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

    In F2, what if u and v are in the same subtree?

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

      We need to lift u to LCA(u, v), and lift v to the child of LCA(u, v).

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

    kth minimum can be solved by wavelet tree instead of Mo's, the complexity is O(m * logq)

    → Reply
  • »
    »
    10 months ago, # ^ |
    ← Rev. 2   Vote: I like it -13 Vote: I do not like it

    Here is a very elegant solution for E that I used:

    Maintain a fenwick tree of values. It need not be persistent, we will take care of that later. Of course we will binary search on queries (because of course, monotonicity). Let us define these three functions.

    • $$$go(i,j)$$$ : apply queries in the range $$$(i,j]$$$.
    • $$$rollback(i,j)$$$ : cancel queries in the range $$$(i,j]$$$.
    • $$$check()$$$ : on the current state, check if the array is beautiful.

    Trivially, $$$check()$$$ can be implemented in $$$O(M \log N)$$$. Also, $$$go(i,j)$$$ and $$$rollback(i,j)$$$ can be implemented in $$$O((j-i)\log N)$$$ similarly. Maybe with a PST it will be faster. but without it, we don't seem to find a better time complexity for these three functions. But this time complexity seems to be enough. Why?

    Let us look at the time complexity deeply. There will clearly be $$$O(\log Q)$$$ calls to $$$check()$$$. So that part is $$$O(M \log N \log Q)$$$. Now the issue is whether the other two functions will be fine. Look further. What will we find? Write down the recurrence formula. You will find this — $$$T(Q)=T(Q/2)+O(Q \log N)$$$.

    This recurrence seems very familiar, doesn't it? We can easily see that this recurrence is equivalent to $$$O(Q \log N)$$$. Now, everything seems so trivial.

    Time complexity at last — $$$O(N+Q \log N + M \log N \log Q)$$$.

    → Reply
»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

For D I was using DFS in python and it was having RTE on test 7, so I googled for decision and found the way to use threading, but for unknown reason now my code does not print anything help me please https://codeforces.com/contest/1843/submission/210454284

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

    i used BFS and got RTE on test 7 too, i feel like it's probably a key error or something but i can't find it

    https://codeforces.com/contest/1843/submission/210442051

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

    Because on each iteration on DFS you pass the graph to the function. It will be like 10^10 memory which gives MLE

    → Reply
  • »
    »
    10 months ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    The MLE is because pypy handles function calls differently, which means it handles setrecursion depth differently: so not only will pypy happily allocate enough RAM for the call depth you requested, the amount per level of depth might be surprisingly heavy.

    tl;dr setrecursiondepth on pypy gets you your MLE result before hitting any of your other bugs

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

      https://codeforces.com/contest/1843/submission/210468007 i stopped passing the graph to function and i use python 3 instead of pypy how can I conquer the runtime error?

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

        interpolation's comment above is an incorrect extrapolation of low-level concepts like pass-by-value vs. pass-by-reference... python's already skating on top of its own system of internal objects, so VERY LOOSELY SPEAKING, since you're already interacting via levels of indirection, everything you're passing in python code is already a reference (except when it's not, but for a mutable object/collection, this story fits here better than the low-level fear of a massive copy).

        If you only used setrecursionlevel to undo python's safety limit, you're probably running out of stack space (stack overflow, undefined behavior, etc.). In cpython, you can essentially set the limit to whatever you want (since there's no matching pre-allocation like in pypy), but that doesn't change how much stack space there is. That's why the bits with threading and setting a custom (large, multiple of target system page size) stack size happen. Other languages also need to do this too, just that it's conveniently handled in cpp compiler parameters and commonly pre-applied due to its popularity in competitive programming (and a source of angst for other contests where people go back to running code on their own systems).

        Personally, my habit is to simulate bfs/dfs iteratively rather than confronting python's recursion warts or dropping into lower-level (ie closer-to-hardware/system, less abstracted-away) concepts (otherwise might as well go back to cpp).

        You can also look up 'bootstrap recursion' but like the thread-parameters backflips, test it out before trying to use it in contest... I'd at least rank bootstrap above the thread-parameters idea as you can keep pypy's faster-worst-case speed.

        But before any of that, you should probably internalize python-y ideas of mutable/immutable so you feel more comfortable predicting behavior of things like a name passed as a function parameter. Try to avoid slapping 'global' onto things in reaction to errors without understanding the underlying causes etc... happy hunting!

        edit:

        A follow-up...! The biggest weakness of the thread-parameter approach is finding the right value for the thread's stack size. See 210486427 and how it consumes 450,528 KB by requesting 268,431,360 for its thread's stack. Weirdly, that seems to be a maximum on codeforces. I tried a smaller value ~160mb and reproduced the test 7 stack overflow. Maybe there are values in between that'll work, but it's not something I'd mess with mid-contest.

        Other approaches mentioned (sorry for sloppiness, was poking at this whenever I got a moment this afternoon):

        bootstrap recursion: note the use of yield 210485286

        iterative simulation: 210483619

        → Reply
»
10 months ago, # |
  Vote: I like it +4 Vote: I do not like it

Feels more like atcoder ABC__

→ Reply
»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

could some figure out what did i do wrong in f1

this is my submission : 210459296

for every x(1<=x<=n), i have stored the maximum continues ones and minus ones from 1 to x.

then while querying i just checked

if k==0 ans is always true

else ans is true if maximum length of ones or minus ones >= absolute(k)

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

    If there is a sequence like 1 1 1 1 -1 1 1 1, we can get sum 6.

    → Reply
»
10 months ago, # |
  Vote: I like it +5 Vote: I do not like it

any approach for E please explain??

→ Reply
  • »
    »
    10 months ago, # ^ |
    ← Rev. 2   Vote: I like it -17 Vote: I do not like it

    Binary search + any data structure for queries sums on segments and updates(Segment tree, Fenwick, Something like Mo heuristics)

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

      you can just use cumulative sum instead of O(log n) query data structure for range sum.

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

        Exactly! A cumulative sum would suffice for each search space from 0 to q-1 within the binary search to find the minimal change number so that at least there is one beautiful segment.

        210467548

        → Reply
»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Good round! The statements are very clear and I love it!

→ Reply
»
10 months ago, # |
  Vote: I like it +13 Vote: I do not like it

Tree forces !

→ Reply
»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I loved the round! I hope you all get your delta increases!

→ Reply
»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I don't understand why I got a TLE on F1. Here is my submission https://codeforces.com/contest/1843/submission/210465690

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

    Still don't understand why tle... Thanks if you can help me with F1

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

    You count space using sizeof(int) in memset() but your ans array is actually boolean type. If the required size is greater than the size of ans array, according to c++ standard of memset(), it's a undefined behaviour.

    → Reply
»
10 months ago, # |
  Vote: I like it +5 Vote: I do not like it

E can be solved using parallel binary search

→ Reply
»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone help me understand why I am getting TLE https://codeforces.com/contest/1843/submission/210409586?

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

    Passing the whole graph as an argument each time is costly. Try making it a global variable or passing the pointer to the vector, instead.

    → Reply
»
10 months ago, # |
  Vote: I like it +5 Vote: I do not like it

I have a question about problem D. It can be easily solved using recursive DFS, and (at least almost) participants used this solution. But how could you know in advance that it would be satisfactory? I mean, that we know that n <= 2*10^5. And the tree could be very long and thin. In this case a recursive solution would cause stack overflow. So whether almost anyone did a leap of faith that trees would not be so thin?

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

    In most contests of CF you don't need to worry about stack overflow when n<=2e5

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

      Is that's the case for python?

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

        Hi there fellow seal, it seems like we coincidentally share the same avatar

        → Reply
    • »
      »
      »
      10 months ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      That sounds a bit vague. Moreover, there exists correct data which would cause stack overflow for almost any solution. E.g. this code should generate such data, which would hack such solutions, isn't it? I tried to hack some solution but got "incorrect test". Could you please explain why it is incorrect?

      #include <iostream>
using namespace std;
int main()
{
    int t = 1;
    int n = 200000;

    cout << t << '\n';
    cout << n << '\n';
    for (int i = 1; i <= n - 1; ++i)
        cout << i << ' ' << i + 1 << '\n';

    int q = n;
    cout << q << '\n';
    for (int i = 1; i <= q; ++i)
        cout << i << '\n';
}
      → Reply
      • »
        »
        »
        »
        10 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        You only output one number per query instead of two.

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

          Oh, indeed. Thank you! I tried, and it seems that the test machine has bigger stack size than mine. Is that stack size known? Because it seems like another limit in addition to the time and memory limits.

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

            I believe the stack size depends on the selected programming language. For example, I've seen many comments stating that it's low enough on Python that you basically have to use BFS. The best way to know the limit here for sure is just plain testing.

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

              Yeah, sure. But if we consider a programming language that compiled to native code (C++), then a stack size could be a part of OS environment variables (e.g. I think it might be the case for Linux). What bothers me is that even if the program passed the pretests it still can fail on some tests. So trial and error during the contest is no guarantee of correctness. So we return to the leap of faith concept :(

              → Reply
          • »
            »
            »
            »
            »
            »
            10 months ago, # ^ |
            ← Rev. 2   Vote: I like it 0 Vote: I do not like it

            https://codeforces.com/blog/entry/57646 So, there are 256 MB for stack (on C++17). By default, you have probably something like 8MB.

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

              210441297 can you tell why mle and why i have to decrease no of ways for 1 by 1 szaranczuk

              → Reply
              • »
                »
                »
                »
                »
                »
                »
                »
                10 months ago, # ^ |
                ← Rev. 2   Vote: I like it 0 Vote: I do not like it

                vector<vector<int>> adj(n+1,vector<int>(n+1));

                You are allocating (n+1)*(n+1) memory at the beginning, thats why you got mle. I didn't test it, but im not convinced whether you actually need to decrease this value.

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

              Cool! Thanks a lot!

              → Reply
»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Div 3 A to D did not test binary search and since its a div3 binary search is usually tested => neuron activation => immediately starts coding binary search solution for E

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

    I also had the same thought initially, then I reverted, and then came back and solved it. The binary search was subtle. If you have not implemented a similar algorithm before, it is definitely tough to inspire. The idea is to check a prefix, and from there it takes linear time to check. Initially, I thought it would take NM time to check. Good to see you got the insight instantly!

    → Reply
    • »
      »
      »
      10 months ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      I tried to implement BS twice, deleted everything halfway through, tried to build a fenwick tree with an O(q * m * log(n)) time complexity instead, fuck me

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

        Lol. I thought of Binary Search for a minute but never dived into it. SegTree had taken over all my ideas. After the contest, it was so easy to solve with BS+SegTree.

        → Reply
»
10 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Very nice problemset (though more than expected tree problems) & perfectly balanced contest..Author should get ++.....+INF contribution.

→ Reply
»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

goodjob

→ Reply
»
10 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Can anyone tell me what is wrong in my python solution for problem D here? It gives Runtime error on 7th testcase. 210431759

→ Reply
  • »
    »
    10 months ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    recursive stack limit exceeded

    you cannot use recursive dfs for this question in python, you should convert to iterative or use other languages where recursion isnt so heavy

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

      how about resetting max recursion depth limit?

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

        Ya, I tried it too but it gives the still says STATUS_STACK_OVERFLOW.

        → Reply
  • »
    »
    10 months ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    same. the first thing I did was use BFS so that every vertex’s value in the graph only contained its children, not all neighbors.

    then I found the number of leaves each vertex has as descendants.

    but i get an RTE on test 7 and I’m not sure why.

    https://codeforces.com/contest/1843/submission/210442051

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

    210472002. I corrected your latest C++ submission which was getting WA. All you missed was typecasting your ans to long long.(I did it using 1LL).

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

    If you get a clean exit (error code 1) at later test case (7), you probably hit python's safety limit against deep recursion.

    If you get a weird result with garbage values, perhaps you used setrecursionlimit to alter that limit (python, not pypy) and overflowed the stack (thereby finding out why the limit exists in the first place).

    While it's possible to alter the stack size sufficiently for straightforward deep recursion to work (again, regular cpython, not pypy), that approach has some more system-specific pitfalls than other approaches, see my responses to olezhkavayn above.

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

      Should I stop using python for competitive coding?

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

        It would be a good idea to transition to C++. It has a larger userbase and better resources to improve in CP.

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

        Not really. Maybe practically all problems <= 2000 can be solved using python, and of couse it is very good for problems like div 2 A-C.

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

    some optimisations that i used to avoid TLE using recursive dfs (java) https://codeforces.com/contest/1843/submission/210402068

    → Reply
»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

For problem B, the problem name is the main hints. (Long Long)

→ Reply
»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

https://www.youtube.com/watch?v=U3xzNgUS0fk&feature=youtu.be My solution for F1

→ Reply
»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Great round! First time solving E feels great, sadly i got 5 WA's in D.

→ Reply
»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Is there any penalty for nonsuccesful hack on a div 3?

→ Reply
»
10 months ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

In problem D,I miscalculated subtree nodes of leaf. Life goes on!!

→ Reply
»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Nice contest! I like problem F

→ Reply
»
10 months ago, # |
  Vote: I like it +24 Vote: I do not like it

F2 is 2 hard for div3 :(

→ Reply
»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

can i do grey testing?

→ Reply
»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Not a lot of people mentioning problem C. Albeit simple, very nice question. The observation that broke the problem was that the node u has children 2u and 2u+1 (obvious if you are grounded with binary trees).

→ Reply
»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

F2: Commutative law, I miss you...

→ Reply
»
10 months ago, # |
  Vote: I like it +1 Vote: I do not like it

That's a good contest and I got + rating. Thank you to EJIC_B_KEDAX and his friends.

→ Reply
»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Please do some works on servers. This is really annoying that site was going down frequently while doing contest.

→ Reply
»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

3 solve only >~<

→ Reply
»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

how to find out the turtorial of these exercise

→ Reply
»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

This is the best 3rd division of those that I have solved!

→ Reply
»
10 months ago, # |
← Rev. 4   Vote: I like it 0 Vote: I do not like it

https://codeforces.com/contest/1843/submission/210504578

Please see the above solution for problem D and tell me where i am going wrong :( spent so many hours to figure it out. but couldn't able to resolve it :(

→ Reply
  • »
    »
    10 months ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Tree is undirected, you should add adj[b].push_back(a) too in your solution. Since its not certain that node with a smaller value will lie above the node with higher value.

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

    And to check if a node is a leaf , you can just check if adj[node].size() == 1 && node != 1

    → Reply
»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

My solution to problem A is still in queue and when I submitted it was shown accepted and now its showing in queue.

→ Reply
»
10 months ago, # |
  Vote: I like it -12 Vote: I do not like it

My two questions are still in queue...why is it so?

→ Reply
»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

why my rating has not been improved even after solving three questions?

→ Reply
»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

can anyone tell me how to create tree from given edges in Problem D (apple Tree) ? because edges are not given consistent like higher level to lower level of tree....some edges given higher to lower and some are given lower to higher....that's the only issue I have in my approach..

My approach:

Once I have tree, I will apply BFS on the given x and y separately. BFS on x will return total possibilities(integer value) that are exist for an apple on node x (same for node y). int value return by BFS on node x will be stored in variable ans1 and int value return by BFS on node y will be stored in variable ans2.

and finally we will print ans1 × ans2 for each assumption...

so, can anyone tell me how to store tree in C++?

→ Reply
  • »
    »
    10 months ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    I think the problem is way more natural with DFS instead of BFS. Also your approach will TLE, you are not supposed to run whatever traversal for each query here. You need to preprocess the input once and store the number of leaves reachable from each node. This can be achieved with a single traversal.

    To be sure the adjacency list is correct you must put the second node in the neighbors of the first and also the first node in the neighibors of the second.

    While doing dfs just be sure you are not visiting the parent again. You can do this both with a visited array or by keeping track of the father of the current node, in this way if the next node is not the father you keep going with the dfs, otherwise you dont.

    While doing DFS you can compute on fly the number of leaves reachable from any root and store into an array, let say array "leaves". Ans for each query is leaves[i]*leaves[j]

    → Reply
»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

It was last rated div3 for me :)

→ Reply
»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Why hasn't the tutorial out? Crying ಥ_ಥ

→ Reply
»
10 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Why did my rating fell from 852 -> 796??? It shows accepted. I am really unable to understand this platform.

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

    Because you solve only 1 problem?

    → Reply
    • »
      »
      »
      10 months ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      And how is that a reason for rank to decrease ? In previous rounds too I have solved a single problem and got increase in ranking.

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

        Why do you think you rating must always go up? There are like more then 15k ppl solved A,B,C. So yours rating drops.

        → Reply
        • »
          »
          »
          »
          »
          10 months ago, # ^ |
          ← Rev. 2   Vote: I like it 0 Vote: I do not like it

          I saw the formula but it didn't go into my head. In one of the contests I solved 0 problems but had a leaderboard rank of 6275, which is the best amongst all(if you consider my other leaderboard ranks) but my rating decreased in that round.

          → Reply
»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

The name of the problem B may indicate that you should use long long.

→ Reply
»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

EJIC_B_KEDAX I'm surprised this passed pretests :/ :/ went from 200 to 1522 :/ https://codeforces.com/contest/1843/submission/210366483

→ Reply
»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hi, I received a penalty for q4 in this contest. However my approach was directly derived from a prior reference that i had studied, finding all the leaf nodes in an n-ary tree using dfs. https://www.geeksforgeeks.org/print-all-leaf-nodes-of-an-n-ary-tree-using-dfs/ is the link that can be checked for reference, Kindly look into the problem and perhaps give a more appropriate solution for the same? Thanks, yxjat

→ Reply
»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I am not able to understand why I received mail from codeforces (Attention!

Your solution 210439915 for the problem 1843D significantly coincides with solutions .....) I think because I used online gdb(https://www.onlinegdb.com/)compiler, they found plagiarism in my code,You can cheak my code too. Please I request you to resolve my issue because I didn't copy code from anyone.Please anyone helpe regarding this issue.

→ Reply
»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Author I have been flagged for having similar solutions but this is a standard problem and I have reused previously written code . Please look into this :(

→ Reply
»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hi, I got a notification of plagiarism in the last contest of Codeforces Round 881 div3. I have gone through both the submissions and both the codes seem to be different to me. It must be a coincidence that plagiarism was detected because if a question has a particular type of approach there is a good enough probability that it might match someone in a pool of about 30k participants, I think that same thing happened here. This was a normal dfs + dynamic programming question and I think the other person has done the question in the same way. There is no way I have cheated here. Please review it once.

→ Reply
»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hello, even I got a notification of plagiarism for 1843B. I have gone through others' submissions and my code is way different than the others. Could have been a coincidence that I was marked for plagiarism because in a pool of about 30k participants its pretty possible to get similar codes because of the same correct approach. This was a simple and normal arrays question and I think the others have done the question in the same way. I did it myself and it is the truth so you cant just conclude I have cheated here. Kindly, review it once. Thanks

→ Reply
»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I am writing to express my concern regarding the solution matching issue I encountered while solving Problem D on Codeforces. I solved the problem using the standard DFS (Depth-First Search) approach, I am surprised to see my code matching with a large number of other participants.

I want to clarify that my implementation is based on a well-established algorithm commonly used for efficient problem-solving in graph and tree traversal. I assure you that there has been no plagiarism or intentional copying involved. I developed and implemented the solution independently, relying solely on my understanding of the problem statement and established programming techniques.

I kindly request your support in ensuring a fair evaluation of my solution. I ask for your consideration in not penalizing participants, including myself, who utilize standard algorithms like DFS when there is code similarity due to the widespread usage of such approaches. ~~~~~ Your code here... ~~~~~

→ Reply