I tried so many time until I change `#include<bits/stdc++.h>` to `#include<stdio.h>`.

And then I did a small experience: for the same code,
Visual C++ 2017 -- 612 KB
Visual C 2017 -- 620 KB
GCC 7.1 / Clang++ 4.0.1 -- 652 KB
G++ 7.1 -- 700 KB

Hope it helps~

#include <iostream>
int main(void){

char nameOfKid[8];

int noOfLetters;
std::cin >> noOfLetters;
std::cin.ignore( 256, '\n') ;
int cur, temp, steps, newcur;
newcur = 0; cur = 0; steps= 0 ;
for (int i = 0 ; i < noOfLetters; ++i){

        std::cin.getline(nameOfKid, 8);

        temp = static_cast<int>(nameOfKid[0]);

        switch(temp){
            case 65:
            case 80:
            case 79:
            case 82: newcur = 1;
                   break;
            case 66:
            case 77:
            case 83: newcur = 2;
                   break;
            case 68:
            case 71:
            case 74:
            case 75:
            case 84: newcur = 3;
                   break;

        }
        if ((newcur!=cur) && (i!=0)){
        steps = steps + ((newcur>cur) ? (newcur-cur): (cur-newcur));

        }
        cur = newcur;

    }

std::cout << steps;
return 0;
}

Solving the problem using the merge sort approach (counting inversions while merging subsequences - plus one inversion in a case of element from the left subseq greater than the element from the right) looks feasible (and maybe evident) to implement. But there is one caveat: it is crucial to count not only the one inversion in a case *cur_left > *cur_right, but count elements in a range [cur_left + 1, right_begin) as "inverted" too. That follows from the fact that merged subarrays are sorted in ascending order, so if we encountered the (*cur_left > *cur_right) case, then elements in a range [cur_left + 1, right_begin) satisfies that too and could be counted as inversions.
Hope I stated that clearly.

Edited by author 04.05.2019 18:59

Edited by author 06.05.2019 06:44

You need to remember that string "no more than 6 sec". It means that you need ignoring all calls with 0 min and 0-6 sec including 6 sec. It's important for tests.

my cpp code is following:

#include <cstdio>
#include <algorithm>
#include <cstring>
#define fi first
#define se second
using namespace std;
typedef long long LL;
typedef pair<int, int> P;
const int N = 5010, INF = 0x3f3f3f3f;

int c[N], sa[N], x[N], y[N];

void GetSA(int *r, int *sa, int n, int m)
{
    for (int i = 1; i <= m; i++) c[i] = 0;
    for (int i = 1; i <= n; i++) c[x[i] = r[i]]++;
    for (int i = 2; i <= m; i++) c[i] += c[i - 1];
    for (int i = n; i >= 1; i--) if (c[x[i]]) sa[c[x[i]]--] = i;
    for (int k = 1, p = 0; k <= n; k <<= 1, p = 0)
    {
        for (int i = n - k + 1; i <= n; i++) y[++p] = i;
        for (int i = 1; i <= n; i++) if (sa[i] > k) y[++p] = sa[i] - k;
        for (int i = 1; i <= m; i++) c[i] = 0;
        for (int i = 1; i <= n; i++) c[x[i]]++;
        for (int i = 2; i <= m; i++) c[i] += c[i - 1];
        for (int i = n; i >= 1; i--) sa[c[x[y[i]]]--] = y[i], y[i] = 0;
        swap(x, y); x[sa[1]] = p = 1;
        for (int i = 2; i <= n; i++) x[sa[i]] = (y[sa[i]] == y[sa[i - 1]] && y[sa[i] + k] == y[sa[i - 1] + k]) ? p : ++p;
        if (p == n) break; m = p;
    }
}

int hei[N], rnk[N];

void GetH(int *r, int *sa, int n)
{
    for (int i = 1; i <= n; i++) rnk[sa[i]] = i;
    for (int i = 1, k = 0, j; i <= n; hei[rnk[i++]] = k)
        for (k ? k-- : 0, j = sa[rnk[i] - 1]; r[i + k] == r[j + k]; k++);
}

int n;

int s[N];
char str[N];

bool check(int a, int b, int len)
{
    return n - a + 2 == b + len;
}

int main()
{
    int mx = 0;
    scanf("%s", str + 1);
    int len = strlen(str + 1);
    for (int i = 1; i <= len; i++) s[i] = str[i], mx = max(mx, s[i]);
    s[len + 1] = '$';
    for (int i = len; i >= 1; i--) s[len * 2 - i + 2] = str[i];
    n = (len << 1) + 1;
    GetSA(s, sa, n, 1000);
    GetH(s, sa, n);
    P ans = P(1, -1);
    for (int i = 3; i <= n; i++)
    {
        int a = max(sa[i - 1], sa[i]), b = min(sa[i - 1], sa[i]);
        if (!(a > len + 1 && b <= len)) continue;
        if (check(a, b, hei[i]) && P(hei[i], -b) > ans) ans = P(hei[i], -b);
    }
    int pos = -ans.se;
    for (int i = pos; i < pos + ans.fi; i++) printf("%c", str[i]); puts("");
    return 0;
}

I've tried to enlarge the alphabet size, but there's no effect.

I also test lots of random test cases, all of them are correct.

I hope someone could give me a hack data.

Edited by author 21.02.2019 15:57

A problem asks to find longest path in Hyper cube graph that visits each vertex at most once.

If two numbers have odd amount of bits in common then there is always a Hamiltonian path (length 2^n). Parity of common bits is checked using xor.

If parity is even then one can build a path of length 2^n - 1. This path can be built by
successively building Hamiltonian paths on lower dimension cube. That is, build a path of length 2^(n - 1) and recurse to find path of length 2^(n - 1) - 1.

So, the solution is built around knowing how to construct Hamiltonian path.

There is, in fact, a very simple approach. My algorithm works in O(2^n) and doesn't use extra memory.

Let those two partial derivatives equal to zero.

Здравствуйте.
В настоящий момент ограничение по времени слишком жёсткое для решения на python (в этой, а также в ряде других задач с большим объёмом входных данных).

Мне видится разумным увеличить Time Limit для данной задачи.


ПС
Вижу, что в статистике есть 3 решения на python (но отсутствуют в таблице рейтинга решений).
Они проходят Time Limit на текущем наборе тестов (или они были сданы когда тестов было меньше)?

Try this tests:

5 2
9 66 15
83 112 26
41 109 16
56 78 18
66 158 18
Ans: 11100

6 1
87 120 37
42 124 36
27 108 18
17 56 13
97 149 29
61 84 27
Ans: 100101

#include<stdio.h>
#include<math.h>
#define PI acos(-1)
int main()
{
    int N,i;
    double r;
    scanf("%d%lf",&N,&r);
    double xx,yy,cx,cy,fx,fy,sum=0,tsum=0,y,x,z;
    y=2*r;
    x=PI*r/2.0;
    z=N*(y-x);
    scanf("%lf%lf",&xx,&yy);
    fx=xx;
    fy=yy;
    for(i=2;i<=N;i++)
    {
        scanf("%lf%lf",&cx,&cy);
        sum=y+sum+sqrt((xx-cx)*(xx-cx)+(yy-cy)*(yy-cy));
        xx=cx;
        yy=cy;
        if(i==N)
        {
            sum=y+sum+sqrt((xx-fx)*(xx-fx)+(yy-fy)*(yy-fy));
            break;
        }
    }
    tsum=sum-z;
    printf("%.2lf\n",tsum);
    return 0;
}

i had that problem and solved it.
2 nd test is n=2 and answer is 0;

wa 23?

hello all,

I am new to programming problems.. I have a doubt regarding the solution.. I got the answer accepted but i want to know how did this problem come under the category of sorting??
I tried thinking a lot but i could never even guess that we have to use sorting.. I only came to know after i saw the hints in this forum.

SO please can anyone explain how did this problem come under sorting??

char buf[41];

unsigned hash()
{
    unsigned h = 0;
    for (char* p = buf; *p; ++p)
    {
        h = h * 13 + *p;
    }
    return h & 511;
}

Edited by author 22.04.2019 21:30

If you are using Edmonds-Karp, chnage it to regular Ford-Fulkerson (do DFS instead of BFS), because the running time in this case is better that way, as the maximum flow can be 1000 at most, so the complexity will be O(V*|f|) <= 2000*1.000.000 and this umber fits in 0.5 seconds. However, in case of E-K, the worst case running time is O(V^2*E) <= 1.000.000 * 1.000.000, which is the case of 1000-1000 complete graph and this exceeds the given 0.5 seconds.

Test
;;
+*
;+*;
Sample module returns:
Expression 1 evaluates to: 111
Expression 2 evaluates to: 1
Expression 3 evaluates to: 11

My AC program returns different result for 3rd string: 111

It's very weird that more complex expression returns smaller result, it fully contradicts the problem statement "It may be assumed that logic of expression evaluation does not depend on context. It means, that each subexpression is always evaluated in the same way with no dependency on it's entrance into the whole expression."

Well, I guess my test can be incorrect though, but it doesn't follow from the problem description. Maybe, it should be updated a little to specify what kind of expressions is acceptable?

well the problem is pretty simple and straight forward but when I try to solve this in python I tried out all algos like adding them that is N iteration then carrying them another N iteration. then print... or store them in a array then add from last digit that is also 2N iterations.... but is there any iteration which is less than 2N iteration including reading the values please help me!!

This question doesn't deserve difficulty above even 100.

sentenсe "for which x0 ≤ x, y0 ≤ y (as in the game the southeast wind blows)" looks like x0 <= x <= y and x0 <= y0 <=y but in fact it should be x0 <= x and y0 <= y

Try C = 794569207093795778
Answer: 315152584