2147A - Shortest Increasing Path

I dont know if it is a good idea to use binary search to find if a valid break point can be set on x axis. although it passed all tests very fast. ~~~~~ left = 1 right = xi find = False while left <= right: mid = (left + right) // 2 if mid < yi and yi < xi — mid: find = True break else: right = mid — 1 if find: print(3) else: print(-1) ~~~~~

515C - Drazil and Factorial

import sys
from collections import defaultdict


def main():
    data = sys.stdin.read().split()
    # print(data)
    n = int(data[0])
    S = data[1]
    # print(S)
    code = {
        "2": "2",
        "3": "3",
        "4": "322",
        "5": "5",
        "6": "53",
        "7": "7",
        "8": "7222",
        "9": "7332",
    }
    ans = []
    for c in S:
        if c != "1" and c != "0":
            ans.append(code[c])
    # print(ans)
    ls = [c for c in "".join(ans)]
    # print(ls)
    ls.sort(reverse=True)
    print("".join(ls))


main()

2143C - Max Tree It is useful, and actually very easy to implement.

I tried to solve it with DFS, but not very obviously,that's not gonna work.

queue = deque()
      
for i in range(V):           
    if in_edge[i] == 0:
        queue.append(i)
 
while queue:
      process = queue.popleft()
      results[process] = cur 
      cur -= 1
      for v in edges[process]:
          in_edge[v] -= 1
          if in_edge[v] == 0:
             queue.append(v)

327B - Hungry Sequence

just guess that I can generate a wierd array with the bad numbers like 171.

so I construct this formula: x = (i+17)*71+177171 then it is accepted..

2178C - First or Second

we can iterate the fixed positon , the items after that fixed item can only contribute -1 * a[i] and for the items before that, two cases rise as:

a) the first item a[0] < 0:

eg> -A B -C -D E .... we can get the greedy sum: B+C+D+E-A cause negative items can be select as 'Second' first, but a[0] must be pick as 'First'.

b) the first item a[0] >= 0:

eg> A B -C -D E .... we can get the greedy sum: B+C+D+E+A cause negative items can be select as 'Second' first.

import sys

if __name__ == "__main__":
    all_cases = sys.stdin.readline()
    all_cases = int(all_cases)

    for i in range(all_cases):
        N = int(input())

        an = [int(x) for x in sys.stdin.readline().split(" ")]
        sumn = [0] * (N + 1)
        psumn = [0] * (N + 1)
        for i in range(0, N):
            sumn[i + 1] = an[i] + sumn[i]
            psumn[i + 1] = abs(an[i]) + psumn[i]

        # print("sumn = ", sumn)

        ans = -1e9
        for i in range(1, N + 1):
            if i - 1 == 0:
                positive_part = 0
            else:
                if an[0] >= 0:
                    positive_part = psumn[i - 1]
                else:
                    positive_part = psumn[i - 1] + 2 * an[0]
            neg_part = -1 * (sumn[N] - sumn[i])
            ans = max(ans, positive_part + neg_part)
        print(ans)