100000000
10
1 5 even
6 10 even
11 18 even
19 25 even
1 8 even
16 25 even
16 40 even
9 40 odd
1000 5000 odd
1000 6000 odd
-1

answer: 7

I had runtime error 25, but when i surrounded sorting with try catch it accepted
Any ideas why?

#solution 1068
x=int(input("enter your number:  "))
def factorial(x):
    if x>0:
        return x + factorial(x - 1)
    elif x<0:
        return x + factorial(x+1)
    if x==0:
        return 0
y=factorial(x)
if x<0:
    print(y+1)
else:
    print(y)

n = int(input())
if n > 0:
    print(int(n*(n+1)/2))
elif n == 0:
    print('1')
else:
    print(int(n*(n-1)/-2 + 1))

delete

Edited by author 04.10.2020 16:38

What's wrong with test #38? I got AC with sorting but failed on majority search?

input :
15 4
1 2 30 994 50 600 700 999 900 990 991 992 993 40 800
output :
   1  50 900 993
   2 600 990  40
  30 700 991 800
 994 999 992

If you have WA4, try a 100x100 matrix with all 1 or with all 0.

Edited by author 12.05.2019 20:53

wa18 ...please

import java.util.Scanner;


public class task9 {


    public static void main(String[] args) {
          Scanner sc = new Scanner(System.in);
          int n = sc.nextInt();
          int m = sc.nextInt();
          int x = sc.nextInt();
          int y = sc.nextInt();
          int cl = 0;
          int stroka =1;
          int[][] mas = new int[n][m];
         for(int i=0;i<n;i++){
             if(stroka%2==1){
                 for(int j=0;j<m;j++){
                 mas[i][j]=cl;
                 cl++;

                 }
                 stroka++;
             }
             else{
                 for(int j=m-1;j>=0;j--){
                 mas[i][j]=cl;
                 cl++;
                 }
                 stroka++;
             }
         }
        System.out.println(mas[x-1][y-1]);

            }


}

The problem is to find how many l*1 or 1*l while rectangles that do not *included* by each others.

My solution is O(NlogN),but I thought there may be some solutions use only O(N) time, thank you for your sharing!

Question requirements are ordered without changing order

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;

const int maxn = 150005;
struct Node
{
    int index;
    int ID;
    int mount;
}node[maxn];

int N;

bool cmp(Node &a, Node &b)
{
    if (a.mount != b.mount)
    {
        return a.mount > b.mount;
    }
    else
    {
        return a.index < b.index;
    }
}

int main()
{
    scanf("%d", &N);
    for (int i=0; i<N; i++)
    {
        scanf("%d%d", &node[i].ID, &node[i].mount);
        node[i].index = i;
    }

    sort(node, node + N, cmp);

    for (int i=0; i<N; i++)
    {
        printf("%d %d\n", node[i].ID, node[i].mount);
    }
    return 0;
}

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.