Little09's blog

Codeforces Global Round 28
By Little09, 2 months ago, In English

Hello, Codeforces!

We are pleased to announce the resumption of the Global Rounds. Thanks to XTX Markets for supporting the initiative! In 2024, we will hold 4 such rounds. The series results will take into account the best 3 participations out of 4.

On Dec/19/2024 17:35 (Moscow time) we will host Codeforces Global Round 28.

Codeforces Global Round 28 marks the fourth round in the 2024 series of Codeforces Global Rounds. These rounds are open and rated for everyone.

The prizes for this round are as follows:

  • The top 30 participants will receive a t-shirt.
  • 20 t-shirts will be randomly distributed among participants ranked between 31 and 500, inclusive.

The prizes for the 4-round series in 2024:

  • In each round, the top-100 participants get points according to the table.
  • A participant's final score will be the sum of the points they earned in their 3 highest-placing rounds.
  • The top 20 participants across the series will receive sweatshirts and placement certificates.

We extend our gratitude to XTX Markets for supporting the global rounds initiative in 2024!

The 9 problems were authored by our 4 authors: JoesSR, cmk666, NetSpeed1 and Little09.

We would also like to thank:

Round Information:

  • Duration: 180 minutes.
  • Number of problems: 9 problems with 1 subtask.
  • Score distribution: $$$ 250 - 500 - 1000 - 1250 - 1750 - 2000 - 2250 - 2750 - (3000 + 3000) $$$.

We eagerly anticipate your participation!

UPD:

Congrats to the winners!

  1. jiangly
  2. turmax
  3. dorijanlendvaj
  4. ksun48
  5. hos.lyric
  6. Nachia
  7. strapple
  8. Ormlis
  9. maroonrk
  10. dXqwq

First Solves:

A: dXqwq
B: dXqwq
C: Marcin_smu
D: jiangly
E: sevlll777
F: dXqwq
G: BlackLily
H: jiangly
I1: jiangly
I2: nobody solved

UPD2: Editorial.

Announcement of Codeforces Global Round 28
  • Vote: I like it
  • +563
  • Vote: I do not like it

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

As a tester, I enjoyed the problems a lot!

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

Super excited for Global Round 28! Big thanks to the authors, testers, and XTX Markets for bringing us these amazing rounds. Let’s have fun solving the problems—good luck to everyone competing

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

expecting increase

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

As an author, I hope you have fun & enjoy the problems!

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

    sir, how should i become a author or a tester.. because i love to do so

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

    Score distribution looks so excited! I guess It will be a great contest and wintevening.

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

As a tester, I tested.

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

(3000+3000). it seems a quite hard problem

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

Little unlucky it is during Saint Nicholas

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

As a discussant, I am glad with friends' problems.

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

December 19 is my birthday.

But will do a contest that day.

Edit: Thanks to everyone!

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

As one of the authors, I hope you enjoy our problems!

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

As a tester, I won't get negative delta :)

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

As a tester, I wish everyone good luck! :)

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

As a tester, I want to gain Contribution.

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

Which topics shall I prepare for global round?

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

As a tester, I can confirm that this round does indeed have problems.

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

Hoping to finally hit Pupil with this one, Good Luck to Everyone taking part!

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

as a participant, i registered

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

As one of the authors, I hope you enjoy our problems!

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

As a, I can

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

practice a lot for this round , hoping for increase

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

I’m close to reaching Pupil and only need six more rating points. Should I participate in this contest or focus on practicing more before competing again? Experienced people, give me suggestions. Do you think I have a good chance of reaching Pupil if I participate in this contest?

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

    Don't think about such stuff and just participate for the thrill of it. Anyways Pupil is very early to even think about such stuff anyways.

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

    Competing in live contests is a skill you should practice. Also, you will improve faster if you worry less about rating.

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

    go for VCs (virtual participate) if you're not so sure about your performance.

    Of course it's only available after the contest and the thrill of live contest is not there... But hey it's good practice and doesn't affect your rating if you scare about negative delta.

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

All the best everyone.

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

As a newbie, I would like some suggestions please. My first contest was Codeforces Round 993 (Div. 4) and I got the first 3 questions right only. Do you think I should try on this one too. Will it be too hard? Thanks! >(>-<)<❤️.

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

is this contest rated ?

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

As a tester, I tested the round in order not to lose rating on my birthday, but I'm afraid I was wrong.

If you would like to send me a birthday gift...
→ Reply
»
2 months ago, # |
  Vote: I like it +8 Vote: I do not like it

As a teter, I confirm this round has been tested

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

As a participant I've a

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

Please don't hack my solutuion

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

Why does mhq coordinate

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

how are the problems rated?

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

Kudos to the authors and testers for their efforts looking forward to the challenging problems and an amazing contest experience. Let’s go!

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

Can somebody elaborate on Placement Certificates part. Does that mean the Top 20 will get an placement offer from XTX MARKETS?

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

Hoping I could get into expert :D

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

As a participant, I am upset that cry is not a writer.

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

What kind of div is this contest?

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

    Actually they have similar problems as a Div1 + Div2 contest and are rated for all participants.

    Just the difference is that global rounds were designed as a series of combined rounds sponsored by a specific company (XTX Markets). So it may depend on them, just think of them as a category of combined rounds (Div1 + Div2) and register for it. Have a nice day!

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

As a newbie, I am gonna solve two problems and start crying after 30 minutes.

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

GL for U all!

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

Newbie question ,is this contest rated

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

297192033 I am not able to get the testcase which is wrong. How should I be able to get the 93rd testcase?

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

    wrong place :/

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

      1 -> how did you find this test case?

      2-> Is this the 93rd testcase?

      3-> Max diff will be wrong for cases like 5 4 3 1 2 as the max diff I will get for this will be 5 (according to my code). I guess I will have to come up with a better solution. Thank you <3

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

        i find this test case by just observing your wrong approach. But u can do stress test but for this type of ad-hoc problem stress test isn't effective, cause you idea is wrong actually.

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

is it rated??

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

Expecting Increase in rating

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

Sorry but it was a coincidence .. I published my code on ideone.com that's why the problem has occured. Please give my ratings back

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

Any tips how to maintain focus during the 3 hours of the contest?

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

    it's strange. in my whole day, I can't focus on anything properly.

    but when I am in a contest I have laser focus.

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

Contest ID: 2048

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

Nice

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

So ...

Notorious Coincidence : Problem B was a task coauthored with chromate00 , but unluckily it appeared in today's round (It was good to be top $$$90$$$) for $$$10$$$ minutes of the round.

My Editorial for the problem :

$$$\textbf{Hint 1}$$$ : The problem can be rephrased to :

$$$\displaystyle \min(\sum_{i=1}^n \min(p_i,p_{i+1},..,p_{i+k-1}))$$$

$$$\textbf{Hint 2}$$$ : Assume you want to evaluate the sum (without construction) thus the sum is :

$$$\underbrace{\underbrace{1+..+1}_{k \text{ times}}+\underbrace{2+..+2}_{k \text{ times}}+...}_{\text{until count =}n}$$$

Take a look at some examples , Let's take $$$(3,2),(5,3)$$$ , For first case we've

$$$[a_1,a_2,a_3] \rightarrow \begin{cases} (a_1,\color{blue}a_2\color{black}) \\ (\color{blue}a_2\color{black},a_3) \\ (a_3,a_1) \\ \end{cases}$$$
$$$[a_1,a_2,a_3,a_4,a_5] \rightarrow \begin{cases} (a_1,a_2,\color{blue}a_3\color{black}) \\ (a_2,\color{blue}a_3\color{black},a_4) \\ (\color{blue}a_3\color{black},a_4,a_5) \\ (a_4,a_5,a_1) \\ (a_5,a_1,a_2) \\ \end{cases}$$$

It's optimal to maximize contribution about sub-permutations of minimum elements

thus It's optimal to place first

$$$\displaystyle \left \lfloor \frac{n}{k} \right \rfloor$$$

with minimum numbers in each index that is multiple of $k$ , and the rest indices can be filled in anyway (For example : fill missing elements in reverse order from larges to smallest).

Complexity is $$$\displaystyle \mathcal{O}(n+\frac{n}{k})=\mathcal{O}(n)$$$

Python
→ Reply
»
2 months ago, # |
  Vote: I like it -11 Vote: I do not like it

What's going on, why E fails on pretest 2, who had this issue?

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

    Wrong solution bro

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

      My solution is based on the observation that edges of a complete graph on 2n vertices can be distributed into n non-intersecting hamiltonian paths.

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

        In your solution, two adjacent vertices of the Hamiltonian path may be in the same fraction

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

Today I learned that stack size on CF is not unlimited.

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

ok so how do i solve F cuz i tunnel visioned so hard on it i spent 2 ENTIRE HOURS with PRACTIALLY 0 PROGRESS done

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

    Consider DP(L,R, t) = max ai in [L,R] after t operations within in. Notice that if I do operation on smallest bi, might as well do whole [L,R], so in essence you can break the DP into smaller ranges split up by the indices of bi, then compute for each smaller ranges and combine the DPs. Then compute DP for the big range. Notice t is at most 60. So time complexity is like n 60^2. (We have n ranges to do dp on) Also, to const opt if bi > 2, make t like 40 or smth.

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

how to solve E!

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

    I can at least explain why the answer is NO if m>=2*n:

    • there are 2*n+m nodes
    • so a spanning tree will have 2*n+m-1 edges.

    Now let's say each of the n colors forms a spanning tree, then it takes n*(2*n+m-1) edges total

    Now this number must be >=2*n*m=total number of edges. Solving this gives m<=2*n-1

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

      nice! I never even thought of it like that.

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

Does anyone solve D with square root decomposition? (Finding the sum of every kth element starting from position s)

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

    no of source can be at most n and jump(k) is 1 to m. do brute force. nlogn complexity. why need sqrt decomposition here?

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

How to solve D?

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

E is cancer.

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

In E, For n=3 and m=7, in the example, it says no pattern is possible.

Can someone please suggest why this is an invalid solution?

1 2 3 1 3 2 1
1 2 3 2 1 3 2
2 3 1 3 2 1 1
2 3 1 1 3 2 3
3 1 2 2 1 3 2
3 1 2 3 2 1 3

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

Problem E was very similar to AGC061B. I used the same pattern as a last hope and got AC. My disappointment is immeasurable, and my day is ruined.

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

This contest is exciting!

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

Really cool round, thanks! I had fun on all of Problems C-I. The statements are so natural and the solution is thinking-oriented. Also now that I got I1 right, it surprised me that I2 is doable...!

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

What's the reason for high constraints in F? Is there a solution better than $$$O(Nlog^2C)$$$ or $$$O(NlogCloglogC)$$$, or were there unintended solutions that passed with lower constraints?

P.S. The problems were good!

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

    You can use two-pointers to make it $$$O(N\log C)$$$

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

      I don't understand :( In contest I only thought of using min-plus convolution (which is two-pointer like maybe?), but I don't think the values are convex

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

        For two non-increasing array a[i], b[i], let c[i] = min(0<=j<=i)(max(a[j],b[i-j])), then the optimal j is non-decreasing when i increases. You can check this by drawing function image of a[j] and b[i-j] for different i.

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

This round makes me wishing to stop playing Identity V

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

I HATE problem E, i'm pretty sure most of the AC just guessed it.

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

    i guessed that m>=2*n is sufficient for the check, but it kinda does make sense

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

      The proof of this is that the subgraph with edges of one color must form a forest. Thus each color must have at most $$$2n + m - 1$$$ edges of that color. So in total the number of edges should be at most $$$(2n + m - 1) \cdot n$$$. But there are $$$2mn$$$ edges. Thus

      $$$2mn \leq (2n + m - 1) \cdot n \implies mn \leq 2n^2 - n \implies m \leq 2n - 1.$$$
      → Reply
      • »
        »
        »
        »
        2 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Ahh i had the 2n+m-1 written down, but i did not write the inequality down, thank you very much!

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

      You can also think about it this way (which is basically the same proof). If $$$m = n$$$, then you have $$$4n^2$$$ edges and at least one color should use $$$4n$$$ edges. But a forest on $$$4n$$$ vertices can have at most $$$4n - 1$$$ edges, so there's definitely will be a cycle.

      Also if $$$m$$$ is strictly greater than $$$n$$$, you can always consider any part of this graph with $$$2n$$$ vertices on the left, and exactly $$$2n$$$ vertices on the right, since this subgraph will contain a cycle for the same reason.

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

Didn't solved F in contest, because 200000*61*8 bytes (=93.08MB) make stack overflowed... First time get so much negative delta because of stack overflow (error code 3221225725)

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

    Is it hard to rewrite your solution using stack to store dp states?

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

      It's not hard to do this but I realized that after contest ended.

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

what could be the possible rating of problem D ?

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

My general idea of F:

Assume we choose intervals [l, r] such that the minimum value in the range b[l..r], denoted as mn. We need to ensure that the selected intervals are local maxima. In other words, for an interval [l, r]:

  • (l == 1 || b[l-1] < mn) .
  • (r == n || b[r+1] < mn).

This leads to intervals forming a tree structure, where each node represents a valid interval [l, r] with the minimum value within it.

Consider the array b[] = [3, 2, 3, 4, 2, 3]. The tree structure of valid intervals and their corresponding minimum values is:

[1, 6] (min = 2)
 
├── [1, 1] (min = 3) ├── [3, 4] (min = 3) ├── [6, 6] (min = 3) 
                     └── [4, 4] (min = 4)

We can perform a greedy strategy on this tree, selecting the optimal ranges at each step:

  1. The root interval [1, 6] has a minimum value of 2. We choose this range until a[2] = a[5] = 1 (2 and 5 only appear in root node).
  2. Then, choose [1, 1] until a[1] = 1, [3, 4] until a[3] = 1, and [6, 6] until a[6] = 1.
  3. Finally, choose [4, 4] until a[4] = 1.

But I'm not sure whether the order of operations (specifically the sequence of selecting intervals) will change the result. Is my idea roughly correct?

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

    We can solve this problem by dp. Let dp(u, t) be the minimum value of (maximum value of a[i] on the subtree of u) if you do t operations on the subtree of u. Note that 2^60>=10^18 so t<=60. So when need to merge dp status from lc and rc: we have merged(i) = min (0<=j<=i) (max(dp(lc, j), dp(rc, i-j)). Note that the optimal j is non-decreasing when i increases, so we can merge them in O(log(A)). Then we need to used the merged value to calculate dp(u): We have dp(u, t) = min(0<=s<=t) (ceil(max(merged(s), a[u]) / b[u]^(t-s))), which means dp(u, t) = min(max(merged(s), a[u]), ceil(dp(u, t-1)/b[u])).

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

could not solve C, kms. + took too long to solve A and B. How do i even reach pupil. seems like itll take ages.

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

I overcooked so hard in C. Used a reduction to Z-functions. Probably wrong :)

Below is my solution. Counter-examples and hacks appreciated.

https://codeforces.me/contest/2048/submission/297300355

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

Funny, problem C seems a bit reminiscing towards 1743D - Problem with Random Tests (not really the same, XOR instead of OR there and only applying to the $$$n \le 1000$$$ subset). I guess just solving that one earlier today gave me a slight edge XD

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

    how long has it been since you solved it ? Do u tend to remember the problems which u practice or they just stay at the back of your mind ?

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

      Literally 6 hours before this contest, just coincidental. I don't remember much, if anything I remember the honed coding technique the most.

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

I changed E to Fill in a matrix with 2n rows and m columns so that the xor of the four corners of any submatrix are not equal to 0. But why this construction is not corret?

1 2 1 2

2 1 2 1

1 1 2 2

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

    You can go from L1, R3, L4, R4, L2, R2, L3, R1 and back to L1. Here L and R are the two sets of the bipartite graph.

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

      thanks, my thoughts was too naive :(

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

wasn't C solvable in O(n), why were the constraints n <= 5000??

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

    Do not think so.Solved with O(n2)

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

      for the first substring it is best to choose the whole string.

      for the second substring I observed that it is most beneficial to set the rightmost zero if at all there is. after that we can use a single for loop to check if any more zero consecutive to it can be set or not.

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

      Just choose indices for the second substring in such a way that the beginning of the string is aligned with the leftmost zero. And if there are consecutive zeros starting from the leftmost, then you go leftwards until you either meet the beginning of the string or the number of steps equals the number of consecutive zeros minus one.

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

    how?

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

      FFT 😂

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

      for the first substring it is best to choose the whole string.

      for the second substring I observed that it is most beneficial to set the rightmost zero if at all there is. after that we can use a single for loop to check if any more zero consecutive to it can be set or not.

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

    for the first substring it is best to choose the whole string.

    for the second substring I observed that it is most beneficial to set the rightmost zero if at all there is. after that we can use a single for loop to check if any more zero consecutive to it can be set or not.

    → Reply
  • »
    »
    2 months ago, # ^ |
      Vote: I like it -9 Vote: I do not like it 
    import java.util.*;

public class Main {
    public static void main(String __[]) {
        var sc = new Scanner(System.in);
        var t = sc.nextInt();
        sc.nextLine();
        while (t-- > 0) {
            var s = sc.nextLine();
            var n = s.length();
            var a2 = new ArrayList<ArrayList<Integer>>();

            for (var i = n - 1; i >= 0; i--) {
                var a1 = new ArrayList<Integer>();
                a1.add(i);
                a1.add(i);
                for (var j = i; j >= 0; j--) {

                    // MAIN LOGIC
                    if (s.charAt(n - 1 - i + j) != s.charAt(j)) {

                        a1.add(n - 1 - i + j);
                        a1.set(1, j);

                    }

                }
                if (a1.size() > 2) a2.add((ArrayList) a1.clone());
            }

            a2.sort((x, y) -> {
                var xs = x.size();
                var ys = y.size();

                for (var i = 1; i <= Math.min(xs, ys) - 2; i++) {
                    if (x.get(xs - i) != y.get(ys - i))
                        return x.get(xs - i) - y.get(ys - i);
                }

                return ys - xs;
            });

            if (a2.size() != 0)
                System.out.println("1 " + n + " " + (a2.get(0).get(1) + 1)
                                   + " " + (a2.get(0).get(0) + 1));
            else System.out.println("1 " + n + " 1 1");
        }
    }
}

    Can you please guess the error because of which my code is giving wrong answer on the 7th test case.

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

    Actually the original problem has $$$n \le 10^5$$$ (and it's div2 B), but we have to make it easier (and come up with an even easier 2B) to make the difficulty reasonable.

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

      haha I see. Just that I often look at the constraints as well to come up with solution. So when I solved in O(n) and passed the pretests, inwardly I was still thinking there has to be something about the constraints. My overthinking sometimes......

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

        Loose constraints can often appear in the first few problems in a contest, don't panic.

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

          I'll keep it in mind. Thanks.

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

A problem identical to C appeared in the Korean Informatics Olympiad. It can be solved in O(n) time complexity. https://www.acmicpc.net/problem/32073

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

I feel that problem "C" may have appeared before.

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

I didn't expect the Identity V references, pretty cool contest :)

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

Can someone please tell me if my logic for Problem C is incorrect? The first substring will be the complete string, since it is mentioned that the string will always start with 1. The XOR can be maximized if the more significant zeros are flipped. So I find out the position of the most significant 0 (suppose it is at index k), then I XOR all possible substrings of length (s.len() — k) and see where I get the maximum value? I would have understood if I was getting TLE, but I am getting an incorrect answer error. My submission

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

    i did the same thing as you, and got TLE, check my submission if you want. Maybe the repeated string to integer conversions I was doing contributed to TLE.

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

      I don't think string to integer conversion is feasible here, because the length of the string could go upto 5000 (that is, 2^5000 as an integer, which is too large to be stored even in long long int). Btw what does the "int start = max(index — ls, 0);" line of code mean?

      → Reply
»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it 
import java.util.*;

public class Main {
    public static void main(String __[]) {
        var sc = new Scanner(System.in);
        var t = sc.nextInt();
        sc.nextLine();
        while (t-- > 0) {
            var s = sc.nextLine();
            var n = s.length();
            var a2 = new ArrayList<ArrayList<Integer>>();

            for (var i = n - 1; i >= 0; i--) {
                var a1 = new ArrayList<Integer>();
                a1.add(i);
                a1.add(i);
                for (var j = i; j >= 0; j--) {

                    // MAIN LOGIC
                    if (s.charAt(n - 1 - i + j) != s.charAt(j)) {

                        a1.add(n - 1 - i + j);
                        a1.set(1, j);

                    }

                }
                if (a1.size() > 2) a2.add((ArrayList) a1.clone());
            }

            a2.sort((x, y) -> {
                var xs = x.size();
                var ys = y.size();

                for (var i = 1; i <= Math.min(xs, ys) - 2; i++) {
                    if (x.get(xs - i) != y.get(ys - i))
                        return x.get(xs - i) - y.get(ys - i);
                }

                return ys - xs;
            });

            if (a2.size() != 0)
                System.out.println("1 " + n + " " + (a2.get(0).get(1) + 1)
                                   + " " + (a2.get(0).get(0) + 1));
            else System.out.println("1 " + n + " 1 1");
        }
    }
}

Can anyone please guess the error because of which my code is giving wrong answer on the 7th test case.

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

Only after ~73 top 500 performances do you have the same chance of not winning a t-shirt as you have the chance of winning a t-shirt with one top 500 performance 😓

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

nice problems!

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

Codeforces Hot News!

Wow! Coder chenlinxuan0226 competed in Codeforces Global Round 28 and gained -55 rating points taking place 1293

Share it!

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

Problem C can be solved in O(n) time 298450724

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

My congratulations to the t-shirt winners:

List place Contest Rank Name
1 2048 1 jiangly
2 2048 2 turmax
3 2048 3 dorijanlendvaj
4 2048 4 ksun48
5 2048 5 hos.lyric
6 2048 6 Nachia
7 2048 7 strapple
8 2048 8 Ormlis
9 2048 9 maroonrk
10 2048 10 dXqwq
11 2048 11 _lbw_
12 2048 12 StarSilk
13 2048 13 xuanxuan001
14 2048 14 arvindf232
15 2048 15 Endagorion
16 2048 16 le0n
17 2048 17 GroupMatrix
18 2048 18 grass8sheep
19 2048 19 HIR180
20 2048 20 Radewoosh
21 2048 21 Kevin114514
22 2048 22 ORzyzRO
23 2048 23 Fido_Puppy
24 2048 24 noimi
25 2048 25 maspy
26 2048 26 chinerist
27 2048 27 Thienu
28 2048 28 Flamire
29 2048 29 Karuna
30 2048 30 fengqiyuka
62 2048 62 Forested
94 2048 94 dog_of_Nesraychan
100 2048 100 chaeyihwan
138 2048 138 huangallen
152 2048 152 Midnights
233 2048 233 Saquariu
253 2048 253 tem_shett
259 2048 259 PaHbLLle_91_6blJl_6blcTp
288 2048 288 wanggiaoxing
290 2048 290 Celebrate
292 2048 292 TheSahib
313 2048 313 dmraykhan
317 2048 317 thocon6969
341 2048 340 sadness
371 2048 371 -is-this-fft-
382 2048 382 HpSuda
394 2048 394 ProjectCF
409 2048 409 codicon
411 2048 411 LMeyling
472 2048 471 sunkuangzheng
→ Reply