import { slug } from 'github-slugger' ; import * as defaultOrdering from '../../content/ordering' ; import PGS from '../components/markdown/PGS' ; import id_to_sol from '../components/markdown/ProblemsList/DivisionList/id_to_sol' ; import { books } from '../utils/books' ; export const contests = { CCC : [ 'DMOJ' , 'Canadian Computing Competition' ] , CCO : [ 'DMOJ' , 'Canadian Computing Olympiad' ] , APIO : [ 'oj.uz' , 'Asia-Pacific Informatics Olympiad' ] , 'Baltic OI' : [ 'oj.uz' , 'Baltic Olympiad in Informatics' ] , CEOI : [ 'oj.uz' , 'Central European Olympiad in Informatics' ] , COI : [ 'oj.uz' , 'Croatian Olympiad in Informatics' ] , COCI : [ 'oj.uz' , 'Croatian Open Contest in Informatics' ] , IOI : [ 'oj.uz' , 'International Olympiad in Informatics' ] , IZhO : [ 'oj.uz' , 'International Zhautykov Olympiad' ] , JOI : [ 'oj.uz' , 'Japanese Olympiad in Informatics' ] , LMiO : [ 'oj.uz' , 'Lithuanian Olympiad in Informatics' ] , RMI : [ 'oj.uz' , 'Romanian Master of Informatics' ] , 'NOI.sg' : [ 'oj.uz' , 'Singapore National Olympiad in Informatics' ] , } ; export const probSources = { Bronze : [ 'http://www.usaco.org/index.php?page=viewproblem2&cpid=' , 'USACO 2015-16 to present' , ] , Silver : [ 'http://www.usaco.org/index.php?page=viewproblem2&cpid=' , 'USACO 2015-16 to present' , ] , Gold : [ 'http://www.usaco.org/index.php?page=viewproblem2&cpid=' , 'USACO 2015-16 to present' , ] , Plat : [ 'http://www.usaco.org/index.php?page=viewproblem2&cpid=' , 'USACO 2015-16 to present' , ] , 'Old Bronze' : [ 'http://www.usaco.org/index.php?page=viewproblem2&cpid=' , 'USACO Platinum did not exist prior to 2015-16.' , ] , 'Old Silver' : [ 'http://www.usaco.org/index.php?page=viewproblem2&cpid=' , 'USACO Platinum did not exist prior to 2015-16.' , ] , 'Old Gold' : [ 'http://www.usaco.org/index.php?page=viewproblem2&cpid=' , 'USACO Platinum did not exist prior to 2015-16.' , ] , AC : [ 'https://atcoder.jp/' , 'AtCoder' , 'The editorial button is right next to the problem title. If "there is no editorial yet," check the "Overall Editorial" PDF below.' , ] , CC : [ 'https://www.codechef.com/problems/' , 'CodeChef' , 'There should be a link to the editorial at the bottom of the page.' , ] , CF : [ 'https://codeforces.com/contest/' , 'CodeForces' , 'Check contest materials, located to the right of the problem statement.' , ] , CSA : [ 'https://csacademy.com/contest/archive/task/' , 'CS Academy' , 'The editorial tab should be right next to the statement tab.' , ] , CSES : [ 'https://cses.fi/problemset/task/' , 'Code Submission Evaluation System (includes CPH problemset)' , ] , DMOJ : [ 'https://dmoj.ca/problem/' , 'DMOJ: Modern Online Judge' , 'There might be a "Read Editorial" button on the right side of the page.' , ] , FHC : [ 'https://www.facebook.com/codingcompetitions/hacker-cup/' , 'Facebook Hacker Cup' , 'There should be a "Solutions" tab on the left side of the page.' , ] , HR : [ 'https://www.hackerrank.com/' , 'HackerRank' , 'The editorial tab should be right next to the discussions tab.' , ] , Kattis : [ 'https://open.kattis.com/problems/' , 'open.kattis.com' ] , LC : [ 'https://leetcode.com/problems/' , 'LeetCode' ] , POI : [ 'https://szkopul.edu.pl/problemset/problem/' , 'Polish Olympiad in Informatics' , ] , SPOJ : [ 'https://www.spoj.com/problems/' , 'Sphere Online Judge' ] , TLX : [ 'https://tlx.toki.id/' , 'tlx.toki.id' , 'The editorial should be available in the announcements tab.' , ] , 'oj.uz' : [ 'https://oj.uz/problem/view/' , '' ] , YS : [ 'https://judge.yosupo.jp/problem/' , 'Library Checker' ] , } ; export type ProblemInfo = { /**
     * Unique ID of the problem. See Content Documentation.md for more info
     */ uniqueId : string ; name : string ; url : string ; /**
     * Source of the problem. More information about some problem sources can be found in the probSources and the contests map.
     */ source : string ; difficulty : ProblemDifficulty ; /**
     * In the context of a module, true if the problem is starred. False otherwise.
     */ isStarred : boolean ; tags : string [ ] ; solution : ProblemSolutionInfo ; } ; export type ProblemSolutionInfo = { kind : 'internal' ; } | { kind : 'link' ; /**
     * Ex: External Sol or CPH 5.3
     */ label : string ; url : string ; } | { kind : 'label' ; label : string ; labelTooltip : string | null ; } | { kind : 'sketch' ; sketch : string ; } | null ; export type AlgoliaProblemInfo = Omit < ProblemInfo , 'uniqueId' > & { objectID : string ; problemModules : { id : string ; title : string ; } [ ] ; } ; export type ProblemMetadata = Omit < ProblemInfo , 'solution' > & { solutionMetadata : ProblemSolutionMetadata ; } ; export type ProblemSolutionMetadata = { kind : 'autogen-label-from-site' ; site : string ; } | { kind : 'internal' ; } | { kind : 'link' ; url : string ; } | { kind : 'CPH' ; section : string ; } | { kind : 'USACO' ; usacoId : string ; } | { kind : 'IOI' ; year : number ; } | { kind : 'none' ; } | { kind : 'in-module' ; moduleId : string ; } | { deprecated kind : 'sketch' ; sketch : string ; } ; export const isUsaco = ( source ) : boolean => { const posi = [ 'Bronze' , 'Silver' , 'Gold' , 'Plat' ] ; for ( let ind = 0 ; ind < posi . length ; ++ ind ) { if ( source . includes ( posi [ ind ] ) ) return true ; } if ( source . startsWith ( '20' ) ) { const posi = [ 'December' , 'January' , 'February' , 'US Open' ] ; for ( let ind = 0 ; ind < posi . length ; ++ ind ) { if ( source . endsWith ( posi [ ind ] ) ) return true ; } } return false ; } ; export function getProblemURL ( problem ) { return `/problems/${ isUsaco ( problem . source ) || problem . source === 'CSES' ? problem . uniqueId : slug ( problem . source ) }-${ slug ( problem . name . replace ( ' - ' , '' ) ) }` ; } /**
 * Retrieves the code from USACO or CSES URL's (finds trailing numbers).
 * Ex: https://cses.fi/problemset/task/1652 yields 1652
 */ const getTrailingCodeFromProblemURL = ( url ) : number => { const match = url . match ( /([0-9]+)\/?$/ ) ; if ( match === null ) { throw new Error ( 'Could not extract USACO / CSES code from URL.' ) ; } return parseInt ( match [ 1 ] ) ; } ; export const getProblemInfo = ( metadata , ordering ? ) : ProblemInfo => { if ( ! ordering ) { ordering = defaultOrdering ; } const { solutionMetadata , ... info } = metadata ; if ( ! info . source || ! info . uniqueId || info . isStarred === null || info . isStarred === undefined || ! info . name || ! info . url ) { console . error ( "problem metadata isn't valid" , metadata ) ; throw new Error ( 'Bad problem metadata' ) ; } let sol ; if ( solutionMetadata . kind === 'autogen-label-from-site' ) { const site = solutionMetadata . site ; if ( ! probSources . hasOwnProperty ( site ) || probSources [ site ] . length !== 3 ) { console . error ( metadata ) ; throw new Error ( "Couldn't autogenerate solution label from problem site " + site ) ; } sol = { kind : 'label' , label : 'Check ' + site , labelTooltip : probSources [ site ] [ 2 ] , } ; } else if ( solutionMetadata . kind === 'internal' ) { sol = { kind : 'internal' , } ; } else if ( solutionMetadata . kind === 'link' ) { sol = { kind : 'link' , url : solutionMetadata . url , label : 'External Sol' , } ; } else if ( solutionMetadata . kind === 'CPH' ) { const getSec = ( dictKey , book , sec ) => { let url = book ; if ( sec [ sec . length - 1 ] == ',' ) sec = sec . substring ( 0 , sec . length - 1 ) ; if ( ! /^\d.*$/ . test ( sec ) ) return url ; if ( ! ( sec in PGS [ dictKey ] ) ) { throw `Could not find section ${ sec } in source ${ dictKey }` ; } url += '#page=' + PGS [ dictKey ] [ sec ] ; return url ; } ; const source = 'CPH' ; const cphUrl = getSec ( source , books [ source ] [ 0 ] , solutionMetadata . section ) ; sol = { kind : 'link' , label : 'CPH ' + solutionMetadata . section , url : cphUrl , } ; } else if ( solutionMetadata . kind === 'USACO' ) { if ( ! id_to_sol . hasOwnProperty ( solutionMetadata . usacoId ) ) { throw new Error ( "Couldn't find a corresponding USACO external solution for USACO problem ID " + solutionMetadata . usacoId ) ; } sol = { kind : 'link' , label : 'External Sol' , url : `http://www.usaco.org/current/data/` + id_to_sol [ solutionMetadata . usacoId ] , } ; } else if ( solutionMetadata . kind === 'IOI' ) { const year = solutionMetadata . year ; const num = year - 1994 + 20 ; sol = { kind : 'link' , label : 'External Sol' , url : `https://ioinformatics.org/page/ioi-${ year }/` + num . toString ( ) , } ; } else if ( solutionMetadata . kind === 'none' ) { sol = null ; } else if ( solutionMetadata . kind === 'in-module' ) { if ( ! ( solutionMetadata . moduleId in ordering . moduleIDToSectionMap ) ) { throw new Error ( `Problem ${ metadata . uniqueId } - solution in nonexistent module: ${ solutionMetadata . moduleId }` ) ; } sol = { kind : 'link' , label : 'In Module' , url : `https://usaco.guide/${ ordering . moduleIDToSectionMap [ solutionMetadata . moduleId ] }/${ solutionMetadata . moduleId }#problem-${ info . uniqueId }` , } ; } else if ( solutionMetadata . kind === 'sketch' ) { sol = { kind : 'sketch' , sketch : solutionMetadata . sketch , } ; } else { throw new Error ( 'Unknown solution metadata ' + JSON . stringify ( solutionMetadata ) ) ; } return { ... info , solution : sol , } ; } ; export function generateProblemUniqueId ( source , name , url ) { if ( isUsaco ( source ) ) { return `usaco-${ getTrailingCodeFromProblemURL ( url ) }` ; } else if ( source === 'CSES' ) { return `cses-${ getTrailingCodeFromProblemURL ( url ) }` ; } else if ( source === 'CF' ) { const num = url . match ( /([0-9]+)/g ) [ 0 ] ; const char = url . match ( /\/([A-z0-9]+)$/ ) [ 1 ] ; if ( url . indexOf ( 'gym' ) !== - 1 ) { return `cfgym-${ num }${ char }` ; } else { return `cf-${ num }${ char }` ; } } else { const camelCase = x => { if ( x . match ( /^[0-9]{4}/ ) !== null ) { return `${ x [ 2 ] }${ x [ 3 ] }-${ camelCase ( x . substring ( 7 ) ) }` ; } x = x . replace ( /[^\w\s]/g , '' ) ; const str = x . replace ( /(?:^\w|[A-Z]|\b\w)/g , function ( word , index ) { return word . toUpperCase ( ) ; } ) ; if ( str . split ( ' ' ) . length === 1 ) { return str . toLowerCase ( ) ; } else { return str . replace ( /\s+/g , '' ) ; } } ; if ( source === 'Baltic OI' ) { return `baltic-${ camelCase ( name ) }` ; } else if ( source === 'Balkan OI' ) { return `balkan-${ camelCase ( name ) }` ; } else { return `${ camelCase ( source ) }-${ camelCase ( name ) }` ; } } } export function autoGenerateSolutionMetadata ( source , name , url ) { if ( isUsaco ( source ) ) { return { kind : 'USACO' , usacoId : '' + getTrailingCodeFromProblemURL ( url ) , } ; } else if ( source == 'IOI' ) { for ( let i = 1994 ; i <= 2089 ; ++ i ) { const des = i . toString ( ) ; let des2 = ( i % 100 ) . toString ( ) ; if ( des2 . length == 1 ) des2 = '0' + des2 ; if ( name . indexOf ( des ) !== - 1 || name . indexOf ( des2 ) !== - 1 ) { return { kind : 'IOI' , year : i , } ; } } return null ; } else if ( probSources . hasOwnProperty ( source ) && probSources [ source ] . length === 3 ) { return { kind : 'autogen-label-from-site' , site : source , } ; } return null ; } export type ProblemSolution = { kind : 'internal' | 'link' | 'text' | 'sketch' ; /**
     * The URL of the problem solution. Defined for kind = "internal" and kind = "link"
     */ url ? : string ; /**
     * The label of the problem solution, defined for kind = "link" and kind = "text"
     */ label ? : string ; /**
     * A tooltip to show in addition to the label, sometimes defined
     */ labelTooltip ? : string | null ; /**
     * Defined for kind = "sketch"
     */ sketch ? : string ; } ; const isExternal = link => { return link . startsWith ( 'http' ) ; } ; const isInternal = link => { return /^[a-zA-Z\-0-9]+$/ . test ( link ) ; } ; export class Problem { public url : string ; public solution : ProblemSolution | null = null ; public hover = '' ; public tooltipHoverDescription : string | null ; public solutionMetadata : any ; get uniqueID ( ) : string { let id ; if ( [ 'Bronze' , 'Silver' , 'Gold' , 'Plat' ] . some ( x => this . source . indexOf ( x ) !== - 1 ) ) { id = `usaco-${ this . id }` ; } else if ( this . source === 'CSES' ) { id = `cses-${ this . id }` ; } else if ( this . source === 'Kattis' && ! this . id . startsWith ( 'http' ) ) { id = `kattis-${ this . id }` ; } else if ( this . source === 'CF' ) { const num = this . id . match ( /([0-9]+)/g ) [ 0 ] ; const char = this . id . match ( /\/([A-z0-9]+)$/ ) [ 1 ] ; if ( this . id . indexOf ( 'gym' ) !== - 1 ) { id = `cfgym-${ num }${ char }` ; } else { id = `cf-${ num }${ char }` ; } } else { const camelCase = x => { if ( x . match ( /^[0-9]{4}/ ) !== null ) { return `${ x [ 2 ] }${ x [ 3 ] }-${ camelCase ( x . substring ( 7 ) ) }` ; } x = x . replace ( /[^\w\s]/g , '' ) ; const str = x . replace ( /(?:^\w|[A-Z]|\b\w)/g , function ( word , index ) { return word . toUpperCase ( ) ; } ) ; if ( str . split ( ' ' ) . length === 1 ) { return str . toLowerCase ( ) ; } else { return str . replace ( /\s+/g , '' ) ; } } ; if ( this . source === 'Baltic OI' ) { id = `baltic-${ camelCase ( this . name ) }` ; } else if ( this . source === 'Balkan OI' ) { id = `balkan-${ camelCase ( this . name ) }` ; } else { id = `${ camelCase ( this . source ) }-${ camelCase ( this . name ) }` ; } } let extra = '' ; if ( this . solutionMetadata ?. kind === 'internal' ) { if ( this . solID !== id ) { extra += '   [Current Sol ID: ' + this . solID + ']' ; } } console . log ( `${ id }${ extra }` ) ; return id ; } private autoGenerateInfoFromSource ( ) { if ( ! ( this . source in probSources ) && isUsaco ( this . source ) ) { this . url = probSources [ 'Bronze' ] [ 0 ] + this . url ; return ; } if ( this . source in probSources ) { if ( ! this . url . startsWith ( 'http' ) ) { if ( this . source == 'CF' && ( this . url . startsWith ( 'problemset' ) || this . url . startsWith ( 'contest' ) || this . url . startsWith ( 'gym' ) || this . url . startsWith ( 'edu' ) ) ) { this . url = 'https://codeforces.com/' + this . url ; } else this . url = probSources [ this . source ] [ 0 ] + this . url ; } this . tooltipHoverDescription = probSources [ this . source ] [ 1 ] ; } else if ( this . source in contests ) { if ( ! this . url . startsWith ( 'http' ) ) { this . url = probSources [ contests [ this . source ] [ 0 ] ] [ 0 ] + this . url ; } this . tooltipHoverDescription = contests [ this . source ] [ 1 ] ; } else { if ( ! this . url . startsWith ( 'http' ) ) { throw `URL ${ this . id } is not valid. Did you make a typo in the problem source (${ this . source }), or in the URL? Problem name: ${ this . name }` ; } if ( this . source . indexOf ( '@' ) != - 1 ) { const ind = this . source . indexOf ( '@' ) ; this . tooltipHoverDescription = this . source . substring ( ind + 1 , this . source . length ) ; this . source = this . source . substring ( 0 , ind ) ; } } } private tryAutoGeneratingSolution ( ) { let autoGeneratedSolURL = null ; if ( isUsaco ( this . source ) && this . id in id_to_sol ) { autoGeneratedSolURL = `http://www.usaco.org/current/data/` + id_to_sol [ this . id ] ; this . solutionMetadata = { kind : 'USACO' , usacoId : this . id , } ; } else if ( this . source == 'IOI' ) { for ( let i = 1994 ; i <= 2017 ; ++ i ) { const des = i . toString ( ) ; if ( this . name . indexOf ( des ) != - 1 ) { const num = i - 1994 + 20 ; autoGeneratedSolURL = `https://ioinformatics.org/page/ioi-${ i }/` + num . toString ( ) ; this . solutionMetadata = { kind : 'IOI' , usacoId : i , } ; break ; } } if ( autoGeneratedSolURL === null ) { for ( let i = 1994 ; i <= 2017 ; ++ i ) { let des = ( i % 100 ) . toString ( ) ; if ( des . length == 1 ) des = '0' + des ; if ( this . name . indexOf ( des ) != - 1 ) { const num = i - 1994 + 20 ; autoGeneratedSolURL = `https://ioinformatics.org/page/ioi-${ i }/` + num . toString ( ) ; this . solutionMetadata = { kind : 'IOI' , usacoId : i , } ; break ; } } } } if ( autoGeneratedSolURL !== null ) { this . solution = { kind : 'link' , url : autoGeneratedSolURL , label : 'External Sol' , } ; } else { if ( this . source in probSources && probSources [ this . source ] . length == 3 ) { this . solution = { kind : 'text' , label : 'Check ' + this . source , labelTooltip : probSources [ this . source ] [ 2 ] , } ; this . solutionMetadata = { kind : 'autogen-label-from-site' , site : this . source , } ; } else { for ( const source in probSources ) { if ( probSources [ source ] . length == 3 && this . url . startsWith ( probSources [ source ] [ 0 ] ) ) { this . solution = { kind : 'text' , label : 'Check ' + source , labelTooltip : probSources [ source ] [ 2 ] , } ; this . solutionMetadata = { kind : 'autogen-label-from-site' , site : source , } ; break ; } } } } } constructor ( public source , public name , public id , public difficulty ? , public starred ? , public tags ? , public solID ? , public solQuality = 'ok' , public fraction ? , public moduleLink ? ) { this . url = id ; this . starred = this . starred ?? false ; this . autoGenerateInfoFromSource ( ) ; solID = solID || '' ; if ( isInternal ( solID ) ) { this . solution = { kind : 'internal' , url : `/solutions/${ solID }` , } ; this . solutionMetadata = { kind : 'internal' , } ; } else if ( isExternal ( solID ) ) { this . solution = { kind : 'link' , url : solID , label : 'External Sol' , } ; this . solutionMetadata = { kind : 'link' , url : solID , } ; } else if ( solID . startsWith ( '@CPH' ) ) { const getSec = ( dictKey , book , sec ) => { let url = book ; if ( sec [ sec . length - 1 ] == ',' ) sec = sec . substring ( 0 , sec . length - 1 ) ; if ( ! /^\d.*$/ . test ( sec ) ) return url ; if ( ! ( sec in PGS [ dictKey ] ) ) { throw `Could not find section ${ sec } in source ${ dictKey }` ; } url += '#page=' + PGS [ dictKey ] [ sec ] ; return url ; } ; const source = 'CPH' ; const cphUrl = getSec ( source , books [ source ] [ 0 ] , solID . substring ( 5 ) ) ; this . solution = { kind : 'link' , label : solID . substring ( 1 ) , url : cphUrl , } ; this . solutionMetadata = { kind : 'CPH' , section : solID . substring ( 5 ) , } ; } else if ( solID . startsWith ( '@' ) ) { let solMsg = null ; if ( solID == '@@' ) { this . solutionMetadata = { kind : 'none' , } ; } else if ( solID == '@B' ) { solMsg = 'Below' ; this . solutionMetadata = { kind : 'in-module' , } ; } else { this . solutionMetadata = { kind : 'in-module' , } ; solMsg = solID . substring ( 1 ) ; } if ( solMsg ) { this . solutionMetadata = { kind : 'in-module' , } ; this . solution = { kind : 'text' , label : solMsg , } ; } } else { this . tryAutoGeneratingSolution ( ) ; if ( solID && ! this . solution ) { this . solutionMetadata = { kind : 'sketch' , sketch : solID , } ; this . solution = { kind : 'sketch' , sketch : solID , } ; } } } } export type ProblemProgress = 'Not Attempted' | 'Solving' | 'Solved' | 'Reviewing' | 'Skipped' | 'Ignored' ; export const PROBLEM_PROGRESS_OPTIONS = [ 'Not Attempted' , 'Solving' , 'Solved' , 'Reviewing' , 'Skipped' , 'Ignored' , ] ; export type ProblemDifficulty = 'Very Easy' | 'Easy' | 'Normal' | 'Hard' | 'Very Hard' | 'Insane' ; export const PROBLEM_DIFFICULTY_OPTIONS = [ 'Very Easy' , 'Easy' , 'Normal' , 'Hard' , 'Very Hard' , 'Insane' , ] ; export type ProblemFeedback = { difficulty : ProblemDifficulty | null ; tags : string [ ] ; solutionCode : string ; isCodePublic : boolean ; otherFeedback : string ; } ;