O--O's blog

INVITATION to TheForces Round #8 (ICPC-Forces) [MASHUP] [GYM]
By O--O, history, 20 months 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?
»
20 months ago, # |
  Vote: I like it +15 Vote: I do not like it

Wow, 11 problems

→ Reply
»
20 months 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
»
20 months 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
»
20 months 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
»
20 months 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
»
20 months ago, # |
  Vote: I like it +33 Vote: I do not like it

I will give this gym today!!!

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

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

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

Are the problems sorted to the difficulty?

→ Reply
  • »
    »
    20 months 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
»
20 months ago, # |
  Vote: I like it +27 Vote: I do not like it

Thanks for good work, can I contribute too ?

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

Did you like the contest?

YES!

→ Reply
»
20 months 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
  • »
    »
    20 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Hint:
    → Reply
  • »
    »
    20 months ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    Yep I did with that only.

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

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

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

Any hints for B and D ?

→ Reply
  • »
    »
    20 months ago, # ^ |
      Vote: I like it +5 Vote: I do not like it
    Hints For B
    → Reply
    • »
      »
      »
      20 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      How to modify the DP for C?

      → Reply
      • »
        »
        »
        »
        20 months 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
        • »
          »
          »
          »
          »
          20 months 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
          • »
            »
            »
            »
            »
            »
            20 months 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
  • »
    »
    20 months ago, # ^ |
      Vote: I like it +15 Vote: I do not like it

    Hint for D : DSU

    → Reply
  • »
    »
    20 months 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
»
20 months 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
»
20 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Great contest as usual !

→ Reply
»
20 months 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
»
20 months ago, # |
← Rev. 2   Vote: I like it +4 Vote: I do not like it
Problem F
→ Reply
»
20 months 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
»
20 months ago, # |
  Vote: I like it 0 Vote: I do not like it

problems were really amazing !! enjoyed the contest.

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

enjoyable contest

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

How to solve H??

→ Reply
»
20 months 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
»
20 months ago, # |
  Vote: I like it +6 Vote: I do not like it

How to solve J?

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

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

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

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

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

    Can you please explain your code in detail?

    → Reply
    • »
      »
      »
      20 months 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
      • »
        »
        »
        »
        20 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

        → Reply
        • »
          »
          »
          »
          »
          20 months 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
»
20 months ago, # |
  Vote: I like it +20 Vote: I do not like it

Problem I — 104120F - Fence Painting

→ Reply