Codeforces and Polygon may be unavailable from December 6, 19:00 (UTC) to December 6, 21:00 (UTC) due to technical maintenance. ×

CodeNation OA Problem | Very Hard Problem on Combinatorics

Revision en1, by LovesProgramming, 2024-10-06 12:33:15

This problem was asked in recent CodeNation Online Test

Given A,B,C — Count the number of valid arrays of size "A" — such that each number of the array is in the range [1,C] — and no subarray of length > B exists in the valid array such that all elements of that subarray are equal

1<=A<=10^9

1<=B<=50

1<=C<=10^5

A = 3

B = 1

C = 3

O/P — 12

[121],[123],[131],[132],[213],[212],[231],[232],[312],[313],[321],[323] are all valid arrays.

Idea = Valid Arrays = Total — Invalid arrays = Counting of Invalid Arrays is easier than valid arrays as far as I can conclude.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English LovesProgramming 2024-10-06 12:35:49 46
en2 English LovesProgramming 2024-10-06 12:34:38 32
en1 English LovesProgramming 2024-10-06 12:33:15 696 Initial revision (published)