drexdelta's blog

By drexdelta, history, 18 months ago, In English

I am trying to solve Problem D from CF-823(div-2).

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

I have written my doubts here, if anyone has time, please help me understand...

1) DOUBT 1

The editorial says,

If you reflect the second string and see what happens, it is easy to see that the elements at the same positions in both strings after any action remain at the same positions relative to each other.

What does "reflect" mean here ? does the editorial mean that reverse the second string ?

2) Doubt 2 ,

If the word reflect means reverse, then, according to the editorial,

the elements at the same positions in both strings after any action remain at the same positions relative to each other.

What does this even mean ?

Considering the below example, Suppose we have n = 8, and instead of calling S1 and S2, I am calling then string S and string T,

s1  s2  s3  s4  s5  s6  s7  s8
 |  |   |   |   |   |   |   | 
t1  t2  t3  t4  t5  t6  t7  t8

There is mapping between each one of the position and relative order initially matching with each other. 

Action 1 , K = 3
t6  t7  t7  s4  s5  s6  s7  s8
 |  |   |   |   |   |   |   | 
t1  t2  t3  t4  t5  s1  s2  s3

Action 2, K = 6

t3  t4  t5  s1  s2  s3  s7  s8
 |  |   |   |   |   |   |   | 
t1  t2  t6  t7  t7  s4  s5  s6 

Now as we can see, that t3 character and s3 character are part of the same string, now what relative order are we talking about here ?

What exactly is happening here ?

It definitely is not EASY to see , """ that the elements at the same positions in both strings after any action remain at the same positions relative to each other""" .

can someone please help me here ?

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

»
18 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
18 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Since my contributions are negative, nobody can see my blog post in recent actions.

Since you are the author of the editorial, Can you please help me understand this interesting problem's solution ?

Brovko

Thank you in advance :) .