You guys getting lives?

.

So you're going to say the opposite thing when there is no contest in 3 consecutive days?

Actually, while this is generous of CodeForces, I think it would be ideal if contests were spread out a little more evenly. I had prior commitments for the weekend and Monday and will miss 3 contests (that would typically be spread over 2-3 weeks instead of 3 days).

same here

You are giving the contest that's the best thing.

Yes, it was a typo in the notes, but it was fixed just about 5 minutes into the contest. We are sorry for that issue, but sometimes typos happen, and we almost always fix them quickly.

Eulerean tour of the letters

a + ab + ac + ad .. + az + b + bc + bd + be + ...

if k = 7, we can concan strings below aabacadaeafag bbcbdbebfbg ccdcecfcg ddedfdg eefeg ffg g and then append strings repeat.

you want to minimize occurrence of each distinct pair of letters (adjacent letters) that appears in the string , add an edge between each pair of usable letters .Then our answer is minimized if we take euler cycle of this graph ,euler cycle always exists since its a directed complete graph, each letter has equal indegree and outdegree.

I did brute force over all pairs ,$$$"aa","ab","ac"\cdots\ "zz"$$$ and greedily selected the best pair with minimum occurence.

Compleixty; $$$O(n*26)$$$

https://codeforces.me/contest/1511/submission/112864604

Problem D: There can be $$$k*k$$$ possible pairs of characters. Now consider each of these pairs as a vertex of a graph. Then add a directed edge from $$$c_1c_2$$$ to $$$c_2c_3$$$ for all possible $$$c_1$$$, $$$c_2$$$ and $$$c_3$$$. Now do topological sorting to find a sequence of pairs. This sequence has each of the pairs exactly once, so the cost is $$$0$$$. So, you get the maximum lengthed string which has $$$0$$$ cost ($$$c_1c_2 \rightarrow c_2c_3$$$ will become $$$c_1c_2c_3$$$). Now just keep concatanating this string until its size becomes n.

Pay attention to the Example 1's output.

I have not given the contest. But just saw B. I think you can have many possible answers . One possible answer can be like this :

X = 100...000(a-1 zeroes) Y = 77...7000...00( (b-c+1) 7s & c-1 zeroes).

This will always give you gcd as 10..00(c-1 zeroes)

For B, I decided to assign a unique prime factor to each of a (2), b (3) and c (7).
As all the numbers (2, 3, 4) are lesser than 10, there will always be a power of {2, 3 and 7} whose decimal representation is of any given number of decimal digits.
First of all, I find c by multiplying it with 7 till I get the required number of digits.
Then, I multiply both a and b by c so that their GCD becomes c.
Finally, I multiply a and b with their respective prime factors till their representations reach the required number of digits.
Eg: 2, 2, 1
Output: 14 (2 * 7), 21 (3 * 7), 7
My Submission

OEIS

I just used dynamic programming (didn't even know there is such thing as OEIS) to find the sequence of the 1D o's and the equation I found was f(k) = f(k-1) + 2f(k-2)+ 2^(k-2) where f(k) denotes the total sum of the maximum tiling for a length k vertical or horizontal row of o's, and then multiplied that by 2^(nbtotal_white-k)

another way to solve for some n is to iterate on len of the consecutive blocks which have same color this solves for some n in O(N). my submission

This submission should also work for bigger C than 50.

D could be solved by the pattern like a+ab+ac+b+bc+c for k=3 , and then just repeat it until you reach n . Can you tell how to solve E

first of all given condition is nothing but checking substrings of length two which are repeated how many times.If you are able to observe it then your task is simply to minimize the Cost which can be minimized if two length substrings are repeated minimum times hence try to make all distinct possible two length substrings which wont be repeated if you add it to end your resulting string continue this and make your resulting string

This Video might help you. Video Explanation

Second solution is not straightforward $$$O(nq)$$$. It is auto-vectorized with GCC and has same logic as your. See assembly here. Click on cycle for and click on "reveal linked code".

I tried several variations of your code and only a few of them passed, you can check my submission history. I guess it's easy to miss that gcc might optimize this particular problem.

How can we do C problem if color of cards is of order 10^5(instead of 50)?

Fairly SImple way to do C.

cin>>n>>k;
    vector<ll> mp(51,-1),m1(51);
    for(ll i=0;i<n;i++) {
        cin>> a[i];
        if(mp[a[i]]==-1)
            mp[a[i]]=i;
    }
    ll tot=0;
    for(ll i=0;i<k;i++) {
        ll j;
        cin>>j;
        cout<<mp[j]+1<<" ";
        for(ll i=1;i<=50;i++) {
            if(mp[i]!=-1 && mp[i]<mp[j]) {
                mp[i]++;
            }
        }
        mp[j]=0;
    }
    cout<<endl;

The second one

Linked lists :)...Lol, these people are dumb!

Yes my submission is also similar to you https://codeforces.me/contest/1511/submission/112834762

yeah , i got the idea and implemented it. It shows wrong answer i spend approx 10 min to find that order matters.

Just put all the 1st and 3rd type no. in one server and 2nd type no.s in another server

Most likely undefined behaviour, like an array out of bound access or the like.

Probably just because python isn't very fast. A static array of size 50 for all the different cards would probably work.

Your exact code passes with Pypy 3 in 1153 ms. Worth a try next time.

it will give wrong ans on 4 6 1 case .

You just care about the minimum index for each number from 1 to 50

Create an array of size 51 (i call it idx), idx[i] = minimum index for i in the input

when he ask for t, you put idx[t] = 1 but before changing it shift all other elements in array "idx" by 1 in case they were less than idx[t].

if you know stl it will be easy for you

• at first you need to store your value in deque
• then for each query find the expected value
• print it's position
• erase that that position's value from deque
• push expected value in the front of the deque

you are all done ^_^

you can see my submission here

Check this video explanation

This Video Explanation Might Help you. Video Explanation

I think it is due to a bug in pypy's implementation of deque
https://stackoverflow.com/questions/13421326/why-is-pypys-deque-so-slow/13421804

It might be that a>b, then the 32 bit integers somewhere overflow and the loop terminates, but the ll do not overflow.

You can hack your own solutions

So the cost of the string is the sum over $$${occ[ij] \choose 2}$$$ where $$$i$$$ and $$$j$$$ are characters from $$$a$$$ to $$$z$$$ and $$$occ[t]$$$ is the number of substring $$$t$$$ in the given string $$$s$$$.

You can prove that if $$$x \geq y+2 $$$ then $$${x \choose 2} + {y \choose 2}$$$ is greater than $$${x -1 \choose 2}+{y+1 \choose 2}$$$. Then consider an optimal string. The difference in the occurrence of the maximum and minimum should not exceed $$$1$$$. With this information and the value of $$$n$$$, we can uniquely determine the maximum and the minimum number of occurrence over all substrings. This paves way for a simple cyclic construction.

Yes. It is. subash23, Look at this submission : https://codeforces.me/contest/1511/submission/112800822

Shouldn't it even pass unoptimized? Is the 2 seconds alloted to answer all of the queries or for each query individually? Because I think for each query O(N^2) should pass but who knows.

MikeMirzayanov please look into this .. My code is hacked by a test case that was already there in pre-tests as well and same code if I submit now is giving AC verdict :(

Yup did the same mistake during the contest.

Your Accepted solution can be hacked again. All submissions will be rejudged after the open hacking phase is finished.

Now it's hacked :)

I did this as well though no proof.

This Video Explanation Might help you. Check this

Or you could notice that $$$10^n$$$ and $$$10^m+1$$$ are coprime for all $$$n$$$ and $$$m$$$. So you could do:

$$$x = 10^{a-1}$$$

$$$y = (10^{b-c} + 1) \cdot 10^{c-1}$$$

And the expression for $$$y$$$ simplifies to:

$$$y = 10^{b-1} + 10^{c-1}$$$

Which I think is a pretty neat answer!

Your code is slow

some cases with high constraints and a specific way to arrange the elements will hack it

+

+

Quit using python if there is no bignum related problem. It is just a slow language.

1. Both solutions are bad.
2. C++ solution works because C++ is faster.

You should contact the problem setter for that

z