Please subscribe to the official Codeforces channel in Telegram via the link https://t.me/codeforces_official. ×

Red0's blog

Looking for a list of good problems[2000-2500]....
By Red0, history, 3 weeks ago, In English

....that involve LCA, MST, Treap, Sparse Table, Binary Manipulations and other advanced techniques.

Trying to build a good foundation. Thanks!

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

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

I recently tried this interesting problem. Would surely recommend it.

https://codeforces.net/problemset/problem/1615/D

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

    Thank you!

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

    if u have an explination to the solution can you please provide it ? i wrote a blog once that the tutorial wasnt clear and also kept trying with it from time to time and never got it

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

      The important observation here is that we are only concerned with the parity of no. of bits on any path, as mentioned in the editorial. Thus, we need to only look at the no. of set bits in a number, and not which bits are set.

      Then we can impose some restrictions on the parity of bits on each path in the input. Any edge with non negative value can also be viewed as a path of size 1. Hence, we can try to impose all these restrictions and see if these give us a valid combination. Then, we will work with the negative weighted edges and obtain their values in the same way.

      To store the parity of bits in any path, we are using DSU (but it is probably not required if we root our tree beforehand). To obtain the parity between any two nodes, we can xor the parity of each path from the root of the tree. Since, if any edge occurs in both the paths, it will not be on the simple path between the two nodes and hence get cancelled. If at any point, the conditions are not satisfied or are contradictory, we know that the required tree is not possible. Finally to obtain the weights of the negative edges, we can check for the required parity between the two nodes, and set our answer as 0 or 1. Here is my solution, feel free to ask any queries.

      https://codeforces.net/contest/1615/submission/269522430

      The solution can also be viewed as a variant of bipartite matching. Each node is colored either 0 or 1, depending on the parity of path between the node and root.

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

https://codeforces.net/contest/809/problem/D

https://codeforces.net/contest/963/problem/D

https://codeforces.net/contest/911/problem/G

https://codeforces.net/contest/1977/problem/D

https://codeforces.net/contest/1975/problem/E

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

609E - Minimum spanning tree for each edge

using MST and LCA

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

i tried this interesting problem, although it might be a bit simple for the techniques you are talking about: 1305G - Kuroni and Antihype

UPDATE: CodingPokemon said that these problems are wayyyyyy to easy for your level

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

Here is another problem, taht uses treap: 4A - Watermelon

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

learn binary search

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

    .....good tip for newbies and pupils trying to reach specialist/expert

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

      are you not tryna reach expert lmao

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

        im trying to reach master :)

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

          believe it or not but masters still need to know binary search

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

suggest me some mst problems

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

    This one is nice: uses lca and mst -- [NOIP2013] — 货物运输

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

Why are you asking for more problems when you haven't finished the ones given to you by smax and RobeZH?

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

    I'm in China bru, and I got permission from RobeZH to stop doing the assigned problems

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

      then ask robezh for more problems smh

      surely he can offer you some 603 probs

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

        I forgot to specify I'm in Hangzhou

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

          no way you are at xyd camp wtf strong

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

            blud u think I would be solving 2100-2400 CF problems rn otherwise? (tho most are from luogu)

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

              ok but still

              learn binary search

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

                we did, in the first day + ternary search

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

                  surely learn adhoc

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

                  ummmm i believe chinese people aren't russian enough, therefore we aren't learning adhoc :D

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

                  usaco still has ad hoc fyi

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

                  yea i know :pray:

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

                  yes and that is precisely the reason you remain a specialist

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

                  at least im not afraid to comment on my main, and I don't cheat on cf just for rating.... reminds me of someone i know...

                  → Reply
»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I've been solving problems from this list, it's a very good list!

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

→ Reply
»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

It would be great if you could recommend the problems recommended to you during your training camp :)

→ Reply
»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply