codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

1795D.md (2177B)


      1 Source: https://codeforces.com/problemset/problem/1795/D
      2 
      3 D. Triangle Coloring
      4 
      5 time limit per test
      6 
      7 3 seconds
      8 
      9 memory limit per test
     10 
     11 512 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 You are given an undirected graph consisting of $n$ vertices and $n$ edges, where $n$ is divisible by $6$. Each edge has a weight, which is a positive (greater than zero) integer.
     22 
     23 The graph has the following structure: it is split into $\frac{n}{3}$ triples of vertices, the first triple consisting of vertices $1, 2, 3$, the second triple consisting of vertices $4, 5, 6$, and so on. Every pair of vertices from the same triple is connected by an edge. There are no edges between vertices from different triples.
     24 
     25 You have to paint the vertices of this graph into two colors, red and blue. Each vertex should have exactly one color, there should be exactly $\frac{n}{2}$ red vertices and $\frac{n}{2}$ blue vertices. The coloring is called valid if it meets these constraints.
     26 
     27 The weight of the coloring is the sum of weights of edges connecting two vertices with different colors.
     28 
     29 Let $W$ be the maximum possible weight of a valid coloring. Calculate the number of valid colorings with weight $W$, and print it modulo $998244353$.
     30 
     31 Input
     32 
     33 The first line contains one integer $n$ ($6 \le n \le 3 \cdot 10^5$, $n$ is divisible by $6$).
     34 
     35 The second line contains $n$ integers $w_1, w_2, \dots, w_n$ ($1 \le w_i \le 1000$) — the weights of the edges. Edge $1$ connects vertices $1$ and $2$, edge $2$ connects vertices $1$ and $3$, edge $3$ connects vertices $2$ and $3$, edge $4$ connects vertices $4$ and $5$, edge $5$ connects vertices $4$ and $6$, edge $6$ connects vertices $5$ and $6$, and so on.
     36 
     37 Output
     38 
     39 Print one integer — the number of valid colorings with maximum possible weight, taken modulo $998244353$.
     40 
     41 Examples
     42 
     43 Input
     44 
     45 ```
     46 12
     47 1 3 3 7 8 5 2 2 2 2 4 2
     48 ```
     49 
     50 Output
     51 
     52 ```
     53 36
     54 ```
     55 
     56 Input
     57 
     58 ```
     59 6
     60 4 2 6 6 6 4
     61 ```
     62 
     63 Output
     64 
     65 ```
     66 2
     67 ```
     68 
     69 Note
     70 
     71 The following picture describes the graph from the first example test.
     72 
     73  ![](https://espresso.codeforces.com/e6e4005b0df87f33b3aafa20244614c906413b24.png) 
     74 
     75 The maximum possible weight of a valid coloring of this graph is $31$.