O--O's blog

INVITATION to TheForces Round #8 (ICPC-Forces) [MASHUP] [GYM]
By O--O, history, 21 month(s) ago, In English

Hello, Codeforces!

We are happy to invite you to TheForces Round #8 (ICPC-Forces), which will take place on [contest_time:433200]

As it's an Indian ICPC week we tried to prepare one good team-based contest which can help you for ICPC preliminary round.

You will have 3 hours to solve 11 problems. The problems are not sorted by difficulty.

The top places will be published after the contest.

Discord Group (500+ people)

Contests' archive

Did you like the contest?

UPD: Rejudged every submission.

UPD: TOP PERFORMERS ---

Rank Name
1 satyam343
2 simiao1986
3 K-423, acfinity, megurine
4 AhmetKaan, qwexd, early-morning-dreams
5 cuiaoxiang
6 achvanov
7 Adam_GS, Everule, Dominater069
8 kachhuaa, chiki_D, vrintle
9 sevlll777
10 vgtcross

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

Comments Comments (50)
| Write comment?
»
21 month(s) ago, # |
  Vote: I like it +15 Vote: I do not like it

Wow, 11 problems

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +41 Vote: I do not like it

Psychotic_D worked very hard for the contest, and came up with some really cool problems.

Please participate. I hope you enjoy the round.

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +11 Vote: I do not like it

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

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +24 Vote: I do not like it

I only tested Psychotic_D's question, his question has educational significance and short statements. The style is close to Codechef, and there is no heavily implementation.

I think it's fun to think about how to optimize complexity as much as possible for each of his problems.

→ Reply
»
21 month(s) ago, # |
← Rev. 3   Vote: I like it +54 Vote: I do not like it

Few Things I want to add as problem setter,

I would like to say thanks to the problem setter and testers.

  • dbtalaviya — For really cool problem ideas and python testing for some of the problems.

  • merlin_ — Tried his very best as a tester and be a JAVA tester. I have no words to appreciate him properly.

  • JUBHAI — testing some of the problems in python and a very first tester.

  • Khonshu08 — Discussing some other problems with me and testing.

  • _Prince — Testing problems and for proposing some ideas.

  • EndlessDreams — For special testing.

  • Little_Sheep_Yawn — for testing almost full contest in python.

  • O--O — For the community TheForces and background support.

Lastly, I hope you people will enjoy the contest as a team. I would love to hear any type of feedback after the contest. We tried to make it a good practice type contest.

UPD: Thanks for making the contest wonderful by taking part in it. I hope you guys enjoyed the problems. You can give me any kind of feedback for future improvements.

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +33 Vote: I do not like it

I will give this gym today!!!

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +9 Vote: I do not like it

Why name is changed from SHA-Forces to ICPC-Forces?

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +29 Vote: I do not like it

    maybe this looks better

    → Reply
»
21 month(s) ago, # |
  Vote: I like it +1 Vote: I do not like it

Are the problems sorted to the difficulty?

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    The blog clearly says that

    The problems are not sorted by difficulty

    → Reply
»
21 month(s) ago, # |
  Vote: I like it +27 Vote: I do not like it

Thanks for good work, can I contribute too ?

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +11 Vote: I do not like it

Did you like the contest?

YES!

→ Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

How to Solve Problem K — Equal subsequence My Idea was to use prefix sum and suffix sum but getting wrong answer on test 2

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Hint:
    → Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    Yep I did with that only.

    Code
    → Reply
»
21 month(s) ago, # |
  Vote: I like it +11 Vote: I do not like it

Amazing and a very balanced problemset, loved it. Psychotic_D orz!!

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +3 Vote: I do not like it

Any hints for B and D ?

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +5 Vote: I do not like it
    Hints For B
    → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      How to modify the DP for C?

      → Reply
      • »
        »
        »
        »
        21 month(s) ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        You can notice that type of DP you are able to easily maintain in segment tree. So you can calculate minimal answer for any substring in $$$O(\log n)$$$. Now you can solve it with two pointers or binary search

        → Reply
        • »
          »
          »
          »
          »
          21 month(s) ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          i did $$$dp[i][remOp][last_digit]$$$ to calculate states in B. where i is the current index remOp is remaining operations and last_digit is the previous digit in the string but i just don't know how to maintain the states in a segment tree.

          can you explain in detail please

          → Reply
          • »
            »
            »
            »
            »
            »
            21 month(s) ago, # ^ |
              Vote: I like it +1 Vote: I do not like it

            Let's change our dp a little bit and make number of changes $$$remOp$$$ what we calculate, not a dimension. $$$dp[l][r][x][y]$$$ will be minimal number of changes to make substring $$$s[l \ldots r]$$$ good with digit $$$x$$$ at the front and $$$y$$$ in the back. We can merge neighbour segments in $$$O(1)$$$ and segment tree only needs $$$O(n)$$$ such segments to store

            → Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +15 Vote: I do not like it

    Hint for D : DSU

    → Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    You can also use binary search on the length of substring that can be the answer and check for all possible substrings of that length. To check whether a given substring can be a good substring, (Longest non-decreasing subsequence)+k >= length of substring.

    PS : You can calculate Longest non-decreasing subsequence using segment tree in O(logn) with O(n) preprocessing as there are maximum 4 unique characters.

    → Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +3 Vote: I do not like it

Great contest as usual !

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +10 Vote: I do not like it

As a tester and laxy person, I hope I am not late to ask for upvotes.

→ Reply
»
21 month(s) ago, # |
← Rev. 2   Vote: I like it +4 Vote: I do not like it
Problem F
→ Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

problems were really amazing !! enjoyed the contest.

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +1 Vote: I do not like it

enjoyable contest

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +1 Vote: I do not like it

How to solve H??

→ Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

https://codeforces.net/gym/433200/submission/197820770

why this is giving Memory limit exceeded using queue whereas other datastructures similar to queue such as priority queue are passing the same test case can someone help?

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +6 Vote: I do not like it

How to solve J?

→ Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone explain problem H please, i couldn't get it !

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +1 Vote: I do not like it

Problem C was cool, just upsolved it. AC with 3572ms

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you please explain your code in detail?

    → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      If you know segment tree then it's a just a variant. First like problem B (easy version), assign some numbers to each character (i.e. '7' to 0, '4' to 1, '8' to 2 and '5' to 3).

      You need to create a node of segtree which will have the information about the cost of change of all combinations of endpoints possible of a good string (start number <= end number).

      Just merge each two node by their possible intermediates.

      Do a BS to find the max possible length starting from i which has cost less or equal to k for each starting i.

      Take max over all possible i and output it.

      → Reply
      • »
        »
        »
        »
        21 month(s) ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Can You please share your DSU based approach of Problem D?

        → Reply
        • »
          »
          »
          »
          »
          21 month(s) ago, # ^ |
            Vote: I like it +5 Vote: I do not like it

          Sure! so we need to connect the adjacent one by one in increasing order of numbers and by DSU we can easily find no of connected components (initially n * m). As two components concatenates one count decreases so we can simply check if we have connected all the cells which has number less ore equal to x has exactly n * m — x + 1 components or not.

          → Reply
»
21 month(s) ago, # |
  Vote: I like it +20 Vote: I do not like it

Problem I — 104120F - Fence Painting

→ Reply