Little09's blog

Codeforces Global Round 28
By Little09, 5 weeks 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
  • +553
  • Vote: I do not like it

»
5 weeks ago, # |
  Vote: I like it +71 Vote: I do not like it

As a tester, I enjoyed the problems a lot!

→ Reply
»
5 weeks 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
»
5 weeks ago, # |
  Vote: I like it +14 Vote: I do not like it

expecting increase

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

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

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

As a tester, I tested.

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

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

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

Little unlucky it is during Saint Nicholas

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

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

→ Reply
»
5 weeks 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
»
5 weeks ago, # |
  Vote: I like it +89 Vote: I do not like it

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

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

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

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

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

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

As a tester, I want to gain Contribution.

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

Which topics shall I prepare for global round?

→ Reply
»
5 weeks 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
»
5 weeks 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
»
5 weeks ago, # |
  Vote: I like it -8 Vote: I do not like it

as a participant, i registered

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

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

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

As a, I can

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

practice a lot for this round , hoping for increase

→ Reply
»
5 weeks 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
  • »
    »
    5 weeks 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
  • »
    »
    5 weeks 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
  • »
    »
    5 weeks 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
»
5 weeks ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

All the best everyone.

→ Reply
»
5 weeks 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
»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

is this contest rated ?

→ Reply
»
5 weeks 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
»
5 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

As a teter, I confirm this round has been tested

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

As a participant I've a

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

Please don't hack my solutuion

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

Why does mhq coordinate

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

how are the problems rated?

→ Reply
»
5 weeks 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
»
5 weeks 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
»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Hoping I could get into expert :D

→ Reply
»
5 weeks 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
»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

What kind of div is this contest?

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

GL for U all!

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

Newbie question ,is this contest rated

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

    wrong place :/

    → Reply
  • »
    »
    5 weeks ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it
    Spoiler
    → Reply
    • »
      »
      »
      5 weeks 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
      • »
        »
        »
        »
        5 weeks 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
»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

is it rated??

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

Expecting Increase in rating

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

Contest ID: 2048

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

Nice

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

    Wrong solution bro

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

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

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

how to solve E!

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

      nice! I never even thought of it like that.

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

How to solve D?

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

E is cancer.

→ Reply
»
5 weeks 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
»
5 weeks 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
»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

This contest is exciting!

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

This round makes me wishing to stop playing Identity V

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

what could be the possible rating of problem D ?

→ Reply
»
5 weeks 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
  • »
    »
    5 weeks 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
»
5 weeks 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
»
5 weeks 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.net/contest/2048/submission/297300355

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

      thanks, my thoughts was too naive :(

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

    Do not think so.Solved with O(n2)

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

    how?

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

      FFT 😂

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

          I'll keep it in mind. Thanks.

          → Reply
»
5 weeks 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
»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

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

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

nice problems!

→ Reply
»
5 weeks 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
»
4 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

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

→ Reply
»
2 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