Problem B can be easy solved using Binary search

Как можно решить задачу D не используя Бор? Слышал что можно решить деревом отрезков.

Заранее спасибо :D

Слишком короткий(унизительный) разбор.

После прочтения кажется, что ты тупой.

этот момент, когда разбор задачи Е длиннее только разбора задачи А

Don't understand the approach for E ! Can someone explain it better ?

why this submission: 19811194 gets memory limit exceeded?? It's memory complexity is O(q lg MAX_a) which is ok for this problem!

Thanks for a really awesome problem set. Really enjoyed the contest.

Isn't complexity of D just O(q)? That log factor is constant.

Btw, u can solve D without any data stucture, finding bits from most significant one with lowerbound on set. The main idea is the same, but u don't have to know trie. Here's my code — 19807490, complexity is O(q*log(q)).

У меня почему то в C WA 12 хотя все как в разборе

In the explanation of problem D, what does RRF mean?

i have problem with time complexity analysis of problem C. let us do worst time complexity analysis. for each case say we have to reverse . reverse function has linear time complexity and for each case we are reversing hence time complexity should be O(n^2) or 10^5 * 10^5 = 10^10.i think then this algorithm should get time limit exceeded verdict in test case where reverse permutation of a string of length close to 10^5 is used.

I have a solution for problem C that does not need DP 19812078:

It basically "tries" both the string and its reverse against all possible previous choices.

class Choice(String s, Long cost)

choices := List.of(new Choice("", 0))

for (cost <- costs) {
  s := readInput()
  r := s.reverse()
  current := List.of(new Choice(s, 0), new Choice(r, cost))
  next := new Map<String, Long>() withDefault Long.MAX

  for(c1 <- choices) {
    for(c2 <- current) {
      if (c1.s.isEmpty || c1.s <= c2.s) {
        next[c2.s] = min(next[c2.s], c1.cost + c2.cost)
      }
    }
  }
  choices = next.map((k, v) => new Choice(k, v))
}

if (choices.isEmpty) print(-1) else print(choices.values.min)

Hi, last night I misunderstood the problem C:

• they said "total length of the strings <= 100 000"

• but I thought "length of each string <= 100 000"

So I came up with the idea "how to compare 2 strings only in O(log(length(string)), and we also don't have to reverse it in O(length)", based on binary search. Thus, the general complexity is O(qlog(length))

So I wrote a "compare(string s1, string s2, int type)" function:

• type = 1: compare non-reverse s1 and non-reverse s2

• type = 2: compare non-reverse s1 and reverse s2

• type = 3: compare reverse s1 and non-reverse s2

• type = 4: compare reverse s1 and reverse s2

Then I submitted and got WA, so I hope somebody could take a look at my submission and point out what I was wrong. I'm sure I got wrong in my "compare" function because when I use standard "compare" and "reverse" functions of C++, I got AC ( of course the complexity now is O(length) ).

Ty in advance.

My submission: 19808155

How do we prove the solution to B is correct ?

I still dont understand prob C. Is the dp actually like brute force? wont it take O(2^n)?

also, in prob D I tried something like putting in integer form in list. I dont understand what the editorial says when it says to put in binary.

(I am new to codeforce!!)

I'm still learning DP, so confused about problem C.

We both know if we want apply DP to some problem, the problem must meet several conditions.One is that it must have optimal sub-structure. One is that the sub-problem has non-aftereffect property.

So here is my question, if we already solve the first i query, but the i+1 th string is smaller than the i th but the cost c[i+1] is too big, then we should not reverse the i+1 th but modify the first i string, how's that meet the optimal sub-structrue and non-aftereffect property? Because the i+1 th string has a big influence on the answer we've already calculated before.

I don't know where I get wrong, thanks for your help.(sorry for poor English

I have solve C using dp , but getting wrong answer. Can someone help me to debug.... I use dp1[] for reverse string and dp[] for simple string. ~~~~~ ..

#define For(i,st,ed) for(i=st;i<=ed;i++)

const ll mod=1000000007;

//Main

int main() { ios_base::sync_with_stdio(false);cin.tie(0); int test=1,i,j,n,tt;

//cin>>test;

For(tt,1,test){
    cin>>n;
    string st[n+1];
    ll dp[n+1],dp1[n+1],a[n+1];
    string s,s1;
    ScanA(a,n);
    dp[1]=0;
    dp1[1]=a[1];
    For(i,1,n)
       cin>>st[i];
    For(i,2,n){
       s.assign(st[i]);
       s1.assign(st[i-1]);
       reverse(s1.begin(),s1.end());
       dp[i]=dp1[i]=-1;
       ll x=-1;
       if(s.compare(st[i-1])>=0 && dp[i-1]!=-1)
         x=dp[i-1];
       if(s.compare(s1)>=0 && dp1[i-1]!=-1)
         if(x!=-1)
          x=min(x,dp1[i-1]);
         else
          x=dp1[i-1];
       dp[i]=x;
       x=-1;
       reverse(s.begin(),s.end());
       if(s.compare(st[i-1])>=0 && dp[i-1]!=-1)
         x=dp[i-1]+a[i];
       if(s.compare(s1)>=0 && dp1[i-1]!=-1)
         if(x!=-1)
          x=min(x,dp1[i-1]+a[i]);
         else
          x=dp1[i-1]+a[i];
       dp1[i]=x;
    }
    ll x=mod;
    if(dp[n]!=-1)
       x=dp[n];
    if(dp1[n]!=-1)
       x=min(x,dp1[n]);
    if(x==mod)
       x=-1;
    cout<<x<<endl;
}
//end of test

return 0;

}

~~~~~

Explain prob D more properly plz . Whats RRF?

По моему разбор Е неполный и не отражает в действительности решения автора задачи. Можно попросить ссылку на код?

Can anyone please explain the D solution in more detail or from another perspective?

What does the announcement mean ? "The lexicographical order is not required to be strict, i.e. two equal strings nearby ARE ALLOWED."

Автор решений к задачам, а вам известно о наличии встроенных функций hypot, reverse и операторов <= , < и тд для строк?

Link for Solution of problem C gives error

Solution for D with std::multiset: just like in solution with trie, for the i^th bit, first we try to get 1, if it's not possible we will get 0. But we can check this using lower_bound.

Code: 19826426

The solution for problem E is just beautiful :)

These are the first few lines of Test #7
100
? 1
+ 1
+ 4
? 5
...
My code prints
1
4
But judge prints
1
5

Please explain how output is 5 for second line.
I got 4 by computing: max(5 XOR 1, 5 XOR 4) = max(4, 1) = 4
Thanks in anticipation.

Just use upper_bound for 2nd question

cout << (upper_bound(v.begin(),v.end(),m)-v.begin())<<endl;

If anyone is interested in practicing problems similar to problem D, here is a question I realized that the solution is quite similar to problem D.

282E — Sausage maximization

I just want to make something sure about problem E. a)Swapping two rectangles like the red and green one is not allowed, right?

b)And if such an operation were allowed, would there be an efficient method to solve this problem?

update: solved it. So, I am clear about (a). So if anyone could tell me about (b)...

Does anyone have an idea for problem E in O(qnlogn) ? With data structures like segment tree?

For the 1-dimensional version of Problem E, is there a solution with faster than linear time swaps?

So in the 1-dimensional version, instead of swapping rectangles in a matrix we're swapping ranges in an array: each task is (a, c, w) and we want to swap the values in [a, a + w) with the values in [c, c + w).

And with n items and q swap queries, we want an O(q * logn + n) algorithm, or just anything faster than O(qn).

With the linked list solution in the post (which is super cool to me!), in the 1-d case it takes O(n) to find the rectangles, even though it's an O(1) swap after finding

I was trying to do something with a binary search tree: each range corresponds to <= logn nodes in the tree, so maybe you could swap ranges by swapping only those logn nodes somehow, and their sub-trees would automatically come with them.

The problem is that the ranges don't "line up": I somehow managed to convinced myself this wasn't really a problem, but I was totally off, and it is a serious issue, as far as I can tell.

Anyway, yeah, is there a quicker solution to the range-swapping problem? I.e. like an O(n) size data structure on n items which supports fast range swaps?

EDIT: answer to question = yes treap

weaker guarantees than with treap i'd guess, but i think a skip-list would work too with high probability. You can find ranges quickly and then edit O(# lists) = O(log N) pointers.

Why this solution of problem D got RE? Help me, please.

edit : found my mistake

hey guys I'm getting WA on test 91 in problem D and i have no idea why. can anyone help me? this is my submission http://codeforces.net/contest/706/submission/20033141 i would really appreciate it

Hello everyone!

Can you help me why I get TLE for Problem D? Here is my submission : http://www.codeforces.com/contest/706/submission/20083814 I used binary search between lo and hi, which are iterators that contains maximum values. But it got TLE on test#2. I think it's because of case when lo > hi, but I can't find out when.

Thanks in advance

Please fix problem D solution!!

I wrote about Problem C in this post here. It's an enjoyable DP question.

Hello Everyone, For the Problem C, I was getting Wrong Answer on test case 18 when I was setting dp[i][0] and dp[i-1][1] to LONG_MAX but when I set it to (1LL<<62) then I was getting Accepted verdict. But (1LL<<62) is less than LONG_MAX. Can anyone explain me the reason for it. Thank You in Advance. WA with LONG_MAX https://codeforces.net/contest/706/submission/48478924 AC with (1LL<<62) https://codeforces.net/contest/706/submission/48479243

Update: I found out that on my system LONG_MAX is 2^63-1 and is equal to LONG_LONG_MAX but on online judge it is different and LONG_MAX is 2^32-1

Why am I getting this message when I click on the solution link in problem E.

404 Not Found

For question D:https://codeforces.net/contest/706/problem/D

Can someone explain logic behind this submission https://codeforces.net/contest/706/submission/19826426 ? It seems extremely simplistic and doesn't seem to use tries.

https://codeforces.net/contest/706/submission/84959926 Please help,I am trying to do with tree,and not able to understand why MLE is coming on last test case

Some Please help me why I am getting WA Thanks in advance submission Link https://codeforces.net/contest/706/submission/110031654

Please help Me I am getting WA on Problem C TC-8 link :https://codeforces.net/contest/706/submission/110875540 Update: Got AC by using a user defined string comparator insted of integer compairing operator

Solution links have broken down, kindly do the needful.

.