ShafinKhadem's blog

By ShafinKhadem, history, 6 months ago, In English

Today I luckily discovered tourist's library from this comment. That made me think, it would be nice if github account could be added to profile, we could easily view many users' libraries and other public repos.

Read more »

 
 
 
 
  • Vote: I like it
  • +62
  • Vote: I do not like it

By ShafinKhadem, history, 7 months ago, In English

I was curious about rating inflation, so I generated a json object containing counts and percentiles and some plots of codeforces rating distribution over months, only counting active contestants:

Json object
{
    "2015-01-01": {
        "Active": {
            "count": 21827,
            "percentile": 0.0
        },
        "Expert+": {
            "count": 6763,
            "percentile": 69.01543959316443
        },
        "CM+": {
            "count": 1778,
            "percentile": 91.85412562422688
        },
        "M+": {
            "count": 724,
            "percentile": 96.68300728455583
        },
        "IM+": {
            "count": 236,
            "percentile": 98.91877033032483
        },
        "GM+": {
            "count": 124,
            "percentile": 99.43189627525541
        },
        "IGM+": {
            "count": 21,
            "percentile": 99.90378888532551
        },
        "LGM": {
            "count": 2,
            "percentile": 99.99083703669767
        }
    },
    "2015-02-01": {
        "Active": {
            "count": 21911,
            "percentile": 0.0
        },
        "Expert+": {
            "count": 6799,
            "percentile": 68.96992378257497
        },
        "CM+": {
            "count": 1682,
            "percentile": 92.32349048423167
        },
        "M+": {
            "count": 701,
            "percentile": 96.80069371548537
        },
        "IM+": {
            "count": 243,
            "percentile": 98.89096800693716
        },
        "GM+": {
            "count": 135,
            "percentile": 99.38387111496509
        },
        "IGM+": {
            "count": 24,
            "percentile": 99.89046597599379
        },
        "LGM": {
            "count": 1,
            "percentile": 99.99543608233307
        }
    },
    "2015-03-01": {
        "Active": {
            "count": 22980,
            "percentile": 0.0
        },
        "Expert+": {
            "count": 6987,
            "percentile": 69.59530026109661
        },
        "CM+": {
            "count": 1772,
            "percentile": 92.28894691035683
        },
        "M+": {
            "count": 732,
            "percentile": 96.81462140992167
        },
        "IM+": {
            "count": 268,
            "percentile": 98.8337684943429
        },
        "GM+": {
            "count": 136,
            "percentile": 99.40818102697999
        },
        "IGM+": {
            "count": 23,
            "percentile": 99.89991296779809
        },
        "LGM": {
            "count": 1,
            "percentile": 99.99564838990426
        }
    },
    "2015-04-01": {
        "Active": {
            "count": 22144,
            "percentile": 0.0
        },
        "Expert+": {
            "count": 6834,
            "percentile": 69.13836705202313
        },
        "CM+": {
            "count": 1770,
            "percentile": 92.0068641618497
        },
        "M+": {
            "count": 770,
            "percentile": 96.52276011560694
        },
        "IM+": {
            "count": 280,
            "percentile": 98.73554913294798
        },
        "GM+": {
            "count": 153,
            "percentile": 99.30906791907515
        },
        "IGM+": {
            "count": 33,
            "percentile": 99.85097543352602
        },
        "LGM": {
            "count": 2,
            "percentile": 99.99096820809248
        }
    },
    "2015-05-01": {
        "Active": {
            "count": 21403,
            "percentile": 0.0
        },
        "Expert+": {
            "count": 6496,
            "percentile": 69.64911461010139
        },
        "CM+": {
            "count": 1803,
            "percentile": 91.57594729710789
        },
        "M+": {
            "count": 781,
            "percentile": 96.35097883474279
        },
        "IM+": {
            "count": 291,
            "percentile": 98.64037751717049
        },
        "GM+": {
            "count": 172,
            "percentile": 99.1963743400458
        },
        "IGM+": {
            "count": 34,
            "percentile": 99.84114376489278
        },
        "LGM": {
            "count": 1,
            "percentile": 99.99532775779096
        }
    },
    "2015-06-01": {
        "Active": {
            "count": 22377,
            "percentile": 0.0
        },
        "Expert+": {
            "count": 6768,
            "percentile": 69.75465880144792
        },
        "CM+": {
            "count": 1821,
            "percentile": 91.86217991687894
        },
        "M+": {
            "count": 783,
            "percentile": 96.50087143048665
        },
        "IM+": {
            "count": 310,
            "percentile": 98.61464896992447
        },
        "GM+": {
            "count": 181,
            "percentile": 99.19113375340751
        },
        "IGM+": {
            "count": 42,
            "percentile": 99.81230727979622
        },
        "LGM": {
            "count": 2,
            "percentile": 99.99106225141887
        }
    },
    "2015-07-01": {
        "Active": {
            "count": 23683,
            "percentile": 0.0
        },
        "Expert+": {
            "count": 7224,
            "percentile": 69.49710762994553
        },
        "CM+": {
            "count": 1934,
            "percentile": 91.83380483891399
        },
        "M+": {
            "count": 844,
            "percentile": 96.43626229785077
        },
        "IM+": {
            "count": 353,
            "percentile": 98.50947937339019
        },
        "GM+": {
            "count": 201,
            "percentile": 99.15128995481992
        },
        "IGM+": {
            "count": 49,
            "percentile": 99.79310053624963
        },
        "LGM": {
            "count": 2,
            "percentile": 99.99155512392856
        }
    },
    "2015-08-01": {
        "Active": {
            "count": 22990,
            "percentile": 0.0
        },
        "Expert+": {
            "count": 7007,
            "percentile": 69.52153110047847
        },
        "CM+": {
            "count": 1834,
            "percentile": 92.02261852979557
        },
        "M+": {
            "count": 819,
            "percentile": 96.43758155719878
        },
        "IM+": {
            "count": 348,
            "percentile": 98.48629839060462
        },
        "GM+": {
            "count": 186,
            "percentile": 99.19095258808177
        },
        "IGM+": {
            "count": 51,
            "percentile": 99.77816441931274
        },
        "LGM": {
            "count": 2,
            "percentile": 99.99130056546325
        }
    },
    "2015-09-01": {
        "Active": {
            "count": 22530,
            "percentile": 0.0
        },
        "Expert+": {
            "count": 6816,
            "percentile": 69.74700399467376
        },
        "CM+": {
            "count": 1792,
            "percentile": 92.04616067465601
        },
        "M+": {
            "count": 809,
            "percentile": 96.4092321349312
        },
        "IM+": {
            "count": 334,
            "percentile": 98.51753217931646
        },
        "GM+": {
            "count": 183,
            "percentile": 99.18774966711052
        },
        "IGM+": {
            "count": 50,
            "percentile": 99.7780736795384
        },
        "LGM": {
            "count": 2,
            "percentile": 99.99112294718154
        }
    },
    "2015-10-01": {
        "Active": {
            "count": 23223,
            "percentile": 0.0
        },
        "Expert+": {
            "count": 6944,
            "percentile": 70.098609137493
        },
        "CM+": {
            "count": 1824,
            "percentile": 92.14571760754424
        },
        "M+": {
            "count": 821,
            "percentile": 96.46471170822029
        },
        "IM+": {
            "count": 346,
            "percentile": 98.51009774792232
        },
        "GM+": {
            "count": 183,
            "percentile": 99.2119881152306
        },
        "IGM+": {
            "count": 50,
            "percentile": 99.78469620634715
        },
        "LGM": {
            "count": 2,
            "percentile": 99.99138784825388
        }
    },
    "2015-11-01": {
        "Active": {
            "count": 23943,
            "percentile": 0.0
        },
        "Expert+": {
            "count": 6509,
            "percentile": 72.8146013448607
        },
        "CM+": {
            "count": 1804,
            "percentile": 92.46543875036545
        },
        "M+": {
            "count": 780,
            "percentile": 96.74226287432653
        },
        "IM+": {
            "count": 333,
            "percentile": 98.60919684250094
        },
        "GM+": {
            "count": 187,
            "percentile": 99.21897840705007
        },
        "IGM+": {
            "count": 56,
            "percentile": 99.76611118072088
        },
        "LGM": {
            "count": 2,
            "percentile": 99.99164682788289
        }
    },
    "2015-12-01": {
        "Active": {
            "count": 24664,
            "percentile": 0.0
        },
        "Expert+": {
            "count": 6456,
            "percentile": 73.82419721050924
        },
        "CM+": {
            "count": 1939,
            "percentile": 92.13833927992215
        },
        "M+": {
            "count": 739,
            "percentile": 97.00373013298734
        },
        "IM+": {
            "count": 318,
            "percentile": 98.71067142393773
        },
        "GM+": {
            "count": 188,
            "percentile": 99.23775543301979
        },
        "IGM+": {
            "count": 54,
            "percentile": 99.78105741161207
        },
        "LGM": {
            "count": 2,
            "percentile": 99.99189101524489
        }
    },
    "2016-01-01": {
        "Active": {
            "count": 24013,
            "percentile": 0.0
        },
        "Expert+": {
            "count": 5985,
            "percentile": 75.07600049972932
        },
        "CM+": {
            "count": 1854,
            "percentile": 92.27918210969058
        },
        "M+": {
            "count": 681,
            "percentile": 97.16403614708699
        },
        "IM+": {
            "count": 284,
            "percentile": 98.81730729188357
        },
        "GM+": {
            "count": 175,
            "percentile": 99.27122808478741
        },
        "IGM+": {
            "count": 61,
            "percentile": 99.74597093241161
        },
        "LGM": {
            "count": 4,
            "percentile": 99.98334235622372
        }
    },
    "2016-02-01": {
        "Active": {
            "count": 25379,
            "percentile": 0.0
        },
        "Expert+": {
            "count": 6167,
            "percentile": 75.70038220576066
        },
        "CM+": {
            "count": 1985,
            "percentile": 92.17857283580913
        },
        "M+": {
            "count": 678,
            "percentile": 97.32849994089602
        },
        "IM+": {
            "count": 295,
            "percentile": 98.83762165569959
        },
        "GM+": {
            "count": 181,
            "percentile": 99.28681193112416
        },
        "IGM+": {
            "count": 64,
            "percentile": 99.74782300327043
        },
        "LGM": {
            "count": 6,
            "percentile": 99.9763584065566
        }
    },
    "2016-03-01": {
        "Active": {
            "count": 24874,
            "percentile": 0.0
        },
        "Expert+": {
            "count": 5980,
            "percentile": 75.95883251588003
        },
        "CM+": {
            "count": 2028,
            "percentile": 91.84690841842888
        },
        "M+": {
            "count": 681,
            "percentile": 97.26220149553751
        },
        "IM+": {
            "count": 287,
            "percentile": 98.84618477124708
        },
        "GM+": {
            "count": 181,
            "percentile": 99.27233255608266
        },
        "IGM+": {
            "count": 72,
            "percentile": 99.7105411272815
        },
        "LGM": {
            "count": 4,
            "percentile": 99.98391895151563
        }
    },
    "2016-04-01": {
        "Active": {
            "count": 25851,
            "percentile": 0.0
        },
        "Expert+": {
            "count": 6089,
            "percentile": 76.44578546284477
        },
        "CM+": {
            "count": 2138,
            "percentile": 91.72952690418165
        },
        "M+": {
            "count": 748,
            "percentile": 97.10649491315617
        },
        "IM+": {
            "count": 326,
            "percentile": 98.73892692739159
        },
        "GM+": {
            "count": 203,
            "percentile": 99.21473057135121
        },
        "IGM+": {
            "count": 71,
            "percentile": 99.72534911608835
        },
        "LGM": {
            "count": 6,
            "percentile": 99.97679006614831
        }
    },
    "2016-05-01": {
        "Active": {
            "count": 23397,
            "percentile": 0.0
        },
        "Expert+": {
            "count": 5519,
            "percentile": 76.41150574860025
        },
        "CM+": {
            "count": 1979,
            "percentile": 91.54165063897081
        },
        "M+": {
            "count": 717,
            "percentile": 96.93550455186562
        },
        "IM+": {
            "count": 319,
            "percentile": 98.63657733897509
        },
        "GM+": {
            "count": 206,
            "percentile": 99.11954524084284
        },
        "IGM+": {
            "count": 75,
            "percentile": 99.67944608283113
        },
        "LGM": {
            "count": 5,
            "percentile": 99.9786297388554
        }
    },
    "2016-06-01": {
        "Active": {
            "count": 23271,
            "percentile": 0.0
        },
        "Expert+": {
            "count": 5531,
            "percentile": 76.23222036010485
        },
        "CM+": {
            "count": 2111,
            "percentile": 90.92862360878347
        },
        "M+": {
            "count": 722,
            "percentile": 96.89742598083451
        },
        "IM+": {
            "count": 310,
            "percentile": 98.66786988096773
        },
        "GM+": {
            "count": 205,
            "percentile": 99.11907524386575
        },
        "IGM+": {
            "count": 77,
            "percentile": 99.66911606720811
        },
        "LGM": {
            "count": 7,
            "percentile": 99.96991964247347
        }
    },
    "2016-07-01": {
        "Active": {
            "count": 24808,
            "percentile": 0.0
        },
        "Expert+": {
            "count": 5832,
            "percentile": 76.49145436955821
        },
        "CM+": {
            "count": 2159,
            "percentile": 91.29716220574008
        },
        "M+": {
            "count": 752,
            "percentile": 96.96871976781684
        },
        "IM+": {
            "count": 330,
            "percentile": 98.6697839406643
        },
        "GM+": {
            "count": 217,
            "percentile": 99.12528216704288
        },
        "IGM+": {
            "count": 82,
            "percentile": 99.66946146404386
        },
        "LGM": {
            "count": 8,
            "percentile": 99.9677523379555
        }
    },
    "2016-08-01": {
        "Active": {
            "count": 24501,
            "percentile": 0.0
        },
        "Expert+": {
            "count": 5718,
            "percentile": 76.6621770539978
        },
        "CM+": {
            "count": 2163,
            "percentile": 91.17178890657524
        },
        "M+": {
            "count": 748,
            "percentile": 96.94706338516795
        },
        "IM+": {
            "count": 323,
            "percentile": 98.68168646177708
        },
        "GM+": {
            "count": 216,
            "percentile": 99.11840333047631
        },
        "IGM+": {
            "count": 87,
            "percentile": 99.64491245255296
        },
        "LGM": {
            "count": 5,
            "percentile": 99.97959266968695
        }
    },
    "2016-09-01": {
        "Active": {
            "count": 25680,
            "percentile": 0.0
        },
        "Expert+": {
            "count": 5870,
            "percentile": 77.14174454828661
        },
        "CM+": {
            "count": 2241,
            "percentile": 91.2733644859813
        },
        "M+": {
            "count": 735,
            "percentile": 97.13785046728972
        },
        "IM+": {
            "count": 312,
            "percentile": 98.78504672897196
        },
        "GM+": {
            "count": 212,
            "percentile": 99.17445482866043
        },
        "IGM+": {
            "count": 77,
            "percentile": 99.70015576323988
        },
        "LGM": {
            "count": 7,
            "percentile": 99.97274143302181
        }
    },
    "2016-10-01": {
        "Active": {
            "count": 25659,
            "percentile": 0.0
        },
        "Expert+": {
            "count": 5850,
            "percentile": 77.20098211153982
        },
        "CM+": {
            "count": 2245,
            "percentile": 91.25063330605246
        },
        "M+": {
            "count": 706,
            "percentile": 97.2485287813243
        },
        "IM+": {
            "count": 294,
            "percentile": 98.8542032035543
        },
        "GM+": {
            "count": 192,
            "percentile": 99.25172454109669
        },
        "IGM+": {
            "count": 84,
            "percentile": 99.6726294867298
        },
        "LGM": {
            "count": 7,
            "percentile": 99.97271912389415
        }
    },
    "2016-11-01": {
        "Active": {
            "count": 29332,
            "percentile": 0.0
        },
        "Expert+": {
            "count": 6334,
            "percentile": 78.40583662893768
        },
        "CM+": {
            "count": 2456,
            "percentile": 91.62689213146052
        },
        "M+": {
            "count": 794,
            "percentile": 97.29305877539888
        },
        "IM+": {
            "count": 311,
            "percentile": 98.93972453293331
        },
        "GM+": {
            "count": 207,
            "percentile": 99.29428610391382
        },
        "IGM+": {
            "count": 84,
            "percentile": 99.71362334651575
        },
        "LGM": {
            "count": 9,
            "percentile": 99.96931678712669
        }
    },
    "2016-12-01": {
        "Active": {
            "count": 30017,
            "percentile": 0.0
        },
        "Expert+": {
            "count": 6388,
            "percentile": 78.71872605523536
        },
        "CM+": {
            "count": 2458,
            "percentile": 91.81130692607522
        },
        "M+": {
            "count": 792,
            "percentile": 97.36149515274678
        },
        "IM+": {
            "count": 326,
            "percentile": 98.913948762368
        },
        "GM+": {
            "count": 213,
            "percentile": 99.29040210547356
        },
        "IGM+": {
            "count": 77,
            "percentile": 99.74347869540594
        },
        "LGM": {
            "count": 11,
            "percentile": 99.9633540993437
        }
    },
    "2017-01-01": {
        "Active": {
            "count": 31613,
            "percentile": 0.0
        },
        "Expert+": {
            "count": 6742,
            "percentile": 78.67333059184513
        },
        "CM+": {
            "count": 2607,
            "percentile": 91.75339259165533
        },
        "M+": {
            "count": 839,
            "percentile": 97.34602853256571
        },
        "IM+": {
            "count": 335,
            "percentile": 98.9403093663999
        },
        "GM+": {
            "count": 230,
            "percentile": 99.27245120678202
        },
        "IGM+": {
            "count": 84,
            "percentile": 99.73428652769431
        },
        "LGM": {
            "count": 8,
            "percentile": 99.97469395501851
        }
    },
    "2017-02-01": {
        "Active": {
            "count": 32078,
            "percentile": 0.0
        },
        "Expert+": {
            "count": 6755,
            "percentile": 78.94195398715631
        },
        "CM+": {
            "count": 2597,
            "percentile": 91.90410873495854
        },
        "M+": {
            "count": 847,
            "percentile": 97.35956106989214
        },
        "IM+": {
            "count": 341,
            "percentile": 98.93696614502151
        },
        "GM+": {
            "count": 235,
            "percentile": 99.26741068645177
        },
        "IGM+": {
            "count": 90,
            "percentile": 99.7194338799177
        },
        "LGM": {
            "count": 10,
            "percentile": 99.96882598665752
        }
    },
    "2017-03-01": {
        "Active": {
            "count": 32786,
            "percentile": 0.0
        },
        "Expert+": {
            "count": 6870,
            "percentile": 79.04593424022448
        },
        "CM+": {
            "count": 2688,
            "percentile": 91.80137863722321
        },
        "M+": {
            "count": 906,
            "percentile": 97.2366253888855
        },
        "IM+": {
            "count": 372,
            "percentile": 98.86536936497285
        },
        "GM+": {
            "count": 242,
            "percentile": 99.2618800707619
        },
        "IGM+": {
            "count": 93,
            "percentile": 99.71634234124322
        },
        "LGM": {
            "count": 9,
            "percentile": 99.97254925882999
        }
    },
    "2017-04-01": {
        "Active": {
            "count": 34047,
            "percentile": 0.0
        },
        "Expert+": {
            "count": 7143,
            "percentile": 79.02017798925016
        },
        "CM+": {
            "count": 2771,
            "percentile": 91.86125062413723
        },
        "M+": {
            "count": 947,
            "percentile": 97.21855082679825
        },
        "IM+": {
            "count": 396,
            "percentile": 98.83690192968544
        },
        "GM+": {
            "count": 266,
            "percentile": 99.2187270537786
        },
        "IGM+": {
            "count": 104,
            "percentile": 99.69453990072547
        },
        "LGM": {
            "count": 10,
            "percentile": 99.97062883660821
        }
    },
    "2017-05-01": {
        "Active": {
            "count": 31673,
            "percentile": 0.0
        },
        "Expert+": {
            "count": 6722,
            "percentile": 78.77687620370662
        },
        "CM+": {
            "count": 2621,
            "percentile": 91.72481293215041
        },
        "M+": {
            "count": 911,
            "percentile": 97.12373314810722
        },
        "IM+": {
            "count": 394,
            "percentile": 98.756038266031
        },
        "GM+": {
            "count": 260,
            "percentile": 99.17911154611183
        },
        "IGM+": {
            "count": 100,
            "percentile": 99.68427367158148
        },
        "LGM": {
            "count": 13,
            "percentile": 99.95895557730559
        }
    },
    "2017-06-01": {
        "Active": {
            "count": 31438,
            "percentile": 0.0
        },
        "Expert+": {
            "count": 6834,
            "percentile": 78.26197595266875
        },
        "CM+": {
            "count": 2692,
            "percentile": 91.43711432024938
        },
        "M+": {
            "count": 956,
            "percentile": 96.95909408995483
        },
        "IM+": {
            "count": 407,
            "percentile": 98.70538838348496
        },
        "GM+": {
            "count": 263,
            "percentile": 99.16343278834532
        },
        "IGM+": {
            "count": 106,
            "percentile": 99.66282842420001
        },
        "LGM": {
            "count": 13,
            "percentile": 99.95864876900566
        }
    },
    "2017-07-01": {
        "Active": {
            "count": 30097,
            "percentile": 0.0
        },
        "Expert+": {
            "count": 6751,
            "percentile": 77.56919294281822
        },
        "CM+": {
            "count": 2706,
            "percentile": 91.0090706714955
        },
        "M+": {
            "count": 946,
            "percentile": 96.85682958434396
        },
        "IM+": {
            "count": 410,
            "percentile": 98.63773798052962
        },
        "GM+": {
            "count": 266,
            "percentile": 99.11619098248995
        },
        "IGM+": {
            "count": 108,
            "percentile": 99.64116024852976
        },
        "LGM": {
            "count": 14,
            "percentile": 99.95348373592053
        }
    },
    "2017-08-01": {
        "Active": {
            "count": 30553,
            "percentile": 0.0
        },
        "Expert+": {
            "count": 6711,
            "percentile": 78.03489019081596
        },
        "CM+": {
            "count": 2678,
            "percentile": 91.23490328282001
        },
        "M+": {
            "count": 932,
            "percentile": 96.94956305436455
        },
        "IM+": {
            "count": 395,
            "percentile": 98.70716459922103
        },
        "GM+": {
            "count": 263,
            "percentile": 99.13920073315222
        },
        "IGM+": {
            "count": 105,
            "percentile": 99.65633489346382
        },
        "LGM": {
            "count": 13,
            "percentile": 99.9574509868098
        }
    },
    "2017-09-01": {
        "Active": {
            "count": 29499,
            "percentile": 0.0
        },
        "Expert+": {
            "count": 6480,
            "percentile": 78.03315366622597
        },
        "CM+": {
            "count": 2540,
            "percentile": 91.38953862842808
        },
        "M+": {
            "count": 870,
            "percentile": 97.05074748296552
        },
        "IM+": {
            "count": 362,
            "percentile": 98.77283975727991
        },
        "GM+": {
            "count": 232,
            "percentile": 99.21353266212414
        },
        "IGM+": {
            "count": 99,
            "percentile": 99.66439540323401
        },
        "LGM": {
            "count": 14,
            "percentile": 99.9525407640937
        }
    },
    "2017-10-01": {
        "Active": {
            "count": 29556,
            "percentile": 0.0
        },
        "Expert+": {
            "count": 6528,
            "percentile": 77.91311408850994
        },
        "CM+": {
            "count": 2566,
            "percentile": 91.31817566653133
        },
        "M+": {
            "count": 934,
            "percentile": 96.83989714440385
        },
        "IM+": {
            "count": 408,
            "percentile": 98.61956963053187
        },
        "GM+": {
            "count": 270,
            "percentile": 99.08647990255785
        },
        "IGM+": {
            "count": 107,
            "percentile": 99.63797536879144
        },
        "LGM": {
            "count": 13,
            "percentile": 99.95601569901204
        }
    },
    "2017-11-01": {
        "Active": {
            "count": 31813,
            "percentile": 0.0
        },
        "Expert+": {
            "count": 6760,
            "percentile": 78.75082513437903
        },
        "CM+": {
            "count": 2658,
            "percentile": 91.64492503064785
        },
        "M+": {
            "count": 970,
            "percentile": 96.95093200892717
        },
        "IM+": {
            "count": 418,
            "percentile": 98.68607173168202
        },
        "GM+": {
            "count": 278,
            "percentile": 99.12614340049666
        },
        "IGM+": {
            "count": 110,
            "percentile": 99.65422940307421
        },
        "LGM": {
            "count": 16,
            "percentile": 99.9497060949926
        }
    },
    "2017-12-01": {
        "Active": {
            "count": 31706,
            "percentile": 0.0
        },
        "Expert+": {
            "count": 6495,
            "percentile": 79.51491831199142
        },
        "CM+": {
            "count": 2512,
            "percentile": 92.07720936100422
        },
        "M+": {
            "count": 866,
            "percentile": 97.26865577493218
        },
        "IM+": {
            "count": 382,
            "percentile": 98.79518072289157
        },
        "GM+": {
            "count": 248,
            "percentile": 99.21781366302908
        },
        "IGM+": {
            "count": 100,
            "percentile": 99.68460228347946
        },
        "LGM": {
            "count": 16,
            "percentile": 99.94953636535672
        }
    },
    "2018-01-01": {
        "Active": {
            "count": 35571,
            "percentile": 0.0
        },
        "Expert+": {
            "count": 7172,
            "percentile": 79.8375080824267
        },
        "CM+": {
            "count": 2725,
            "percentile": 92.33926513170842
        },
        "M+": {
            "count": 926,
            "percentile": 97.39675578420623
        },
        "IM+": {
            "count": 400,
            "percentile": 98.87548845970032
        },
        "GM+": {
            "count": 258,
            "percentile": 99.2746900565067
        },
        "IGM+": {
            "count": 113,
            "percentile": 99.68232548986533
        },
        "LGM": {
            "count": 15,
            "percentile": 99.95783081723876
        }
    },
    "2018-02-01": {
        "Active": {
            "count": 36611,
            "percentile": 0.0
        },
        "Expert+": {
            "count": 7293,
            "percentile": 80.07975744994674
        },
        "CM+": {
            "count": 2808,
            "percentile": 92.33017399142334
        },
        "M+": {
            "count": 921,
            "percentile": 97.48436262325531
        },
        "IM+": {
            "count": 392,
            "percentile": 98.92928354866024
        },
        "GM+": {
            "count": 259,
            "percentile": 99.29256234465052
        },
        "IGM+": {
            "count": 109,
            "percentile": 99.70227527245909
        },
        "LGM": {
            "count": 15,
            "percentile": 99.95902870721915
        }
    },
    "2018-03-01": {
        "Active": {
            "count": 38369,
            "percentile": 0.0
        },
        "Expert+": {
            "count": 7782,
            "percentile": 79.718001511637
        },
        "CM+": {
            "count": 3075,
            "percentile": 91.98571763663374
        },
        "M+": {
            "count": 968,
            "percentile": 97.47712997471918
        },
        "IM+": {
            "count": 393,
            "percentile": 98.97573561990149
        },
        "GM+": {
            "count": 258,
            "percentile": 99.32758216268341
        },
        "IGM+": {
            "count": 105,
            "percentile": 99.72634157783628
        },
        "LGM": {
            "count": 16,
            "percentile": 99.95829966900362
        }
    },
    "2018-04-01": {
        "Active": {
            "count": 38465,
            "percentile": 0.0
        },
        "Expert+": {
            "count": 7902,
            "percentile": 79.45664890159885
        },
        "CM+": {
            "count": 3088,
            "percentile": 91.97192252697258
        },
        "M+": {
            "count": 990,
            "percentile": 97.42623163915248
        },
        "IM+": {
            "count": 424,
            "percentile": 98.89769920707137
        },
        "GM+": {
            "count": 274,
            "percentile": 99.28766411023008
        },
        "IGM+": {
            "count": 113,
            "percentile": 99.70622643962044
        },
        "LGM": {
            "count": 15,
            "percentile": 99.96100350968413
        }
    },
    "2018-05-01": {
        "Active": {
            "count": 37568,
            "percentile": 0.0
        },
        "Expert+": {
            "count": 7757,
            "percentile": 79.35210817717206
        },
        "CM+": {
            "count": 3099,
            "percentile": 91.75095826235093
        },
        "M+": {
            "count": 958,
            "percentile": 97.44995741056218
        },
        "IM+": {
            "count": 395,
            "percentile": 98.94857325383305
        },
        "GM+": {
            "count": 261,
            "percentile": 99.30525979557069
        },
        "IGM+": {
            "count": 104,
            "percentile": 99.72316865417376
        },
        "LGM": {
            "count": 14,
            "percentile": 99.96273424190801
        }
    },
    "2018-06-01": {
        "Active": {
            "count": 41045,
            "percentile": 0.0
        },
        "Expert+": {
            "count": 8469,
            "percentile": 79.36654890973323
        },
        "CM+": {
            "count": 3261,
            "percentile": 92.05506151784627
        },
        "M+": {
            "count": 1155,
            "percentile": 97.18601534900719
        },
        "IM+": {
            "count": 423,
            "percentile": 98.96942380314289
        },
        "GM+": {
            "count": 277,
            "percentile": 99.32513095383116
        },
        "IGM+": {
            "count": 110,
            "percentile": 99.73200146181021
        },
        "LGM": {
            "count": 15,
            "percentile": 99.9634547447923
        }
    },
    "2018-07-01": {
        "Active": {
            "count": 41929,
            "percentile": 0.0
        },
        "Expert+": {
            "count": 8807,
            "percentile": 78.99544468029288
        },
        "CM+": {
            "count": 3321,
            "percentile": 92.07946767153999
        },
        "M+": {
            "count": 1269,
            "percentile": 96.9734551265234
        },
        "IM+": {
            "count": 432,
            "percentile": 98.96968685158244
        },
        "GM+": {
            "count": 289,
            "percentile": 99.31073958358176
        },
        "IGM+": {
            "count": 118,
            "percentile": 99.71857187149705
        },
        "LGM": {
            "count": 15,
            "percentile": 99.96422523790217
        }
    },
    "2018-08-01": {
        "Active": {
            "count": 43558,
            "percentile": 0.0
        },
        "Expert+": {
            "count": 9319,
            "percentile": 78.6055374443271
        },
        "CM+": {
            "count": 3221,
            "percentile": 92.60526194958446
        },
        "M+": {
            "count": 1235,
            "percentile": 97.16469994030948
        },
        "IM+": {
            "count": 411,
            "percentile": 99.05643050645116
        },
        "GM+": {
            "count": 269,
            "percentile": 99.38243261857752
        },
        "IGM+": {
            "count": 109,
            "percentile": 99.74975894210019
        },
        "LGM": {
            "count": 16,
            "percentile": 99.96326736764773
        }
    },
    "2018-09-01": {
        "Active": {
            "count": 43212,
            "percentile": 0.0
        },
        "Expert+": {
            "count": 9224,
            "percentile": 78.65407757104508
        },
        "CM+": {
            "count": 3216,
            "percentile": 92.55762288253263
        },
        "M+": {
            "count": 1308,
            "percentile": 96.97306303804498
        },
        "IM+": {
            "count": 440,
            "percentile": 98.98176432472461
        },
        "GM+": {
            "count": 291,
            "percentile": 99.32657595112468
        },
        "IGM+": {
            "count": 123,
            "percentile": 99.71535684532074
        },
        "LGM": {
            "count": 19,
            "percentile": 99.95603073220401
        }
    },
    "2018-10-01": {
        "Active": {
            "count": 45562,
            "percentile": 0.0
        },
        "Expert+": {
            "count": 9000,
            "percentile": 80.24669680874413
        },
        "CM+": {
            "count": 3206,
            "percentile": 92.96343444098152
        },
        "M+": {
            "count": 1364,
            "percentile": 97.00627716079188
        },
        "IM+": {
            "count": 438,
            "percentile": 99.03867257802555
        },
        "GM+": {
            "count": 303,
            "percentile": 99.33497212589438
        },
        "IGM+": {
            "count": 118,
            "percentile": 99.74101224704798
        },
        "LGM": {
            "count": 19,
            "percentile": 99.9582985821518
        }
    },
    "2018-11-01": {
        "Active": {
            "count": 49401,
            "percentile": 0.0
        },
        "Expert+": {
            "count": 9504,
            "percentile": 80.76152304609218
        },
        "CM+": {
            "count": 3381,
            "percentile": 93.15600898767231
        },
        "M+": {
            "count": 1460,
            "percentile": 97.04459423898302
        },
        "IM+": {
            "count": 470,
            "percentile": 99.04860225501508
        },
        "GM+": {
            "count": 315,
            "percentile": 99.36236108580798
        },
        "IGM+": {
            "count": 124,
            "percentile": 99.74899293536568
        },
        "LGM": {
            "count": 27,
            "percentile": 99.9453452359264
        }
    },
    "2018-12-01": {
        "Active": {
            "count": 49805,
            "percentile": 0.0
        },
        "Expert+": {
            "count": 9639,
            "percentile": 80.646521433591
        },
        "CM+": {
            "count": 3421,
            "percentile": 93.13121172573035
        },
        "M+": {
            "count": 1556,
            "percentile": 96.87581568115651
        },
        "IM+": {
            "count": 471,
            "percentile": 99.05431181608272
        },
        "GM+": {
            "count": 326,
            "percentile": 99.34544724425258
        },
        "IGM+": {
            "count": 125,
            "percentile": 99.74902118261218
        },
        "LGM": {
            "count": 28,
            "percentile": 99.94378074490513
        }
    },
    "2019-01-01": {
        "Active": {
            "count": 51993,
            "percentile": 0.0
        },
        "Expert+": {
            "count": 10092,
            "percentile": 80.5896947666032
        },
        "CM+": {
            "count": 3520,
            "percentile": 93.22985786548189
        },
        "M+": {
            "count": 1616,
            "percentile": 96.89188929278941
        },
        "IM+": {
            "count": 504,
            "percentile": 99.03063873983037
        },
        "GM+": {
            "count": 348,
            "percentile": 99.33067912988287
        },
        "IGM+": {
            "count": 135,
            "percentile": 99.74034966245456
        },
        "LGM": {
            "count": 23,
            "percentile": 99.95576327582559
        }
    },
    "2019-02-01": {
        "Active": {
            "count": 53230,
            "percentile": 0.0
        },
        "Expert+": {
            "count": 10677,
            "percentile": 79.94176216419312
        },
        "CM+": {
            "count": 3683,
            "percentile": 93.08096937817021
        },
        "M+": {
            "count": 1696,
            "percentile": 96.81382678940447
        },
        "IM+": {
            "count": 531,
            "percentile": 99.00244223182416
        },
        "GM+": {
            "count": 369,
            "percentile": 99.3067818899117
        },
        "IGM+": {
            "count": 135,
            "percentile": 99.74638361826038
        },
        "LGM": {
            "count": 23,
            "percentile": 99.95679128311103
        }
    },
    "2019-03-01": {
        "Active": {
            "count": 54824,
            "percentile": 0.0
        },
        "Expert+": {
            "count": 10881,
            "percentile": 80.15285276521232
        },
        "CM+": {
            "count": 3829,
            "percentile": 93.01583248212462
        },
        "M+": {
            "count": 1732,
            "percentile": 96.84079964978841
        },
        "IM+": {
            "count": 530,
            "percentile": 99.03327010068583
        },
        "GM+": {
            "count": 369,
            "percentile": 99.32693710783599
        },
        "IGM+": {
            "count": 132,
            "percentile": 99.75922953451044
        },
        "LGM": {
            "count": 22,
            "percentile": 99.95987158908507
        }
    },
    "2019-04-01": {
        "Active": {
            "count": 55614,
            "percentile": 0.0
        },
        "Expert+": {
            "count": 11224,
            "percentile": 79.81803143093465
        },
        "CM+": {
            "count": 3769,
            "percentile": 93.22292947818895
        },
        "M+": {
            "count": 1755,
            "percentile": 96.84431977559608
        },
        "IM+": {
            "count": 534,
            "percentile": 99.03981011975402
        },
        "GM+": {
            "count": 358,
            "percentile": 99.3562771963894
        },
        "IGM+": {
            "count": 134,
            "percentile": 99.75905347574351
        },
        "LGM": {
            "count": 21,
            "percentile": 99.96223972381055
        }
    },
    "2019-05-01": {
        "Active": {
            "count": 54309,
            "percentile": 0.0
        },
        "Expert+": {
            "count": 11057,
            "percentile": 79.64057522694213
        },
        "CM+": {
            "count": 3706,
            "percentile": 93.17608499512052
        },
        "M+": {
            "count": 1721,
            "percentile": 96.8310961350789
        },
        "IM+": {
            "count": 544,
            "percentile": 98.99832440295347
        },
        "GM+": {
            "count": 355,
            "percentile": 99.34633302030971
        },
        "IGM+": {
            "count": 135,
            "percentile": 99.75142241617411
        },
        "LGM": {
            "count": 24,
            "percentile": 99.95580842954206
        }
    },
    "2019-06-01": {
        "Active": {
            "count": 53440,
            "percentile": 0.0
        },
        "Expert+": {
            "count": 10822,
            "percentile": 79.74925149700599
        },
        "CM+": {
            "count": 3687,
            "percentile": 93.10067365269461
        },
        "M+": {
            "count": 1692,
            "percentile": 96.83383233532935
        },
        "IM+": {
            "count": 541,
            "percentile": 98.98764970059881
        },
        "GM+": {
            "count": 355,
            "percentile": 99.33570359281437
        },
        "IGM+": {
            "count": 129,
            "percentile": 99.75860778443113
        },
        "LGM": {
            "count": 27,
            "percentile": 99.9494760479042
        }
    },
    "2019-07-01": {
        "Active": {
            "count": 55973,
            "percentile": 0.0
        },
        "Expert+": {
            "count": 11396,
            "percentile": 79.64018365997892
        },
        "CM+": {
            "count": 3878,
            "percentile": 93.07165955014024
        },
        "M+": {
            "count": 1857,
            "percentile": 96.68232898004395
        },
        "IM+": {
            "count": 566,
            "percentile": 98.98879817054652
        },
        "GM+": {
            "count": 370,
            "percentile": 99.33896700194737
        },
        "IGM+": {
            "count": 137,
            "percentile": 99.75523913315348
        },
        "LGM": {
            "count": 25,
            "percentile": 99.9553356082397
        }
    },
    "2019-08-01": {
        "Active": {
            "count": 54863,
            "percentile": 0.0
        },
        "Expert+": {
            "count": 11070,
            "percentile": 79.82246687202668
        },
        "CM+": {
            "count": 3773,
            "percentile": 93.12286969360042
        },
        "M+": {
            "count": 1756,
            "percentile": 96.7993000747316
        },
        "IM+": {
            "count": 539,
            "percentile": 99.0175528133715
        },
        "GM+": {
            "count": 361,
            "percentile": 99.3419973388258
        },
        "IGM+": {
            "count": 132,
            "percentile": 99.75940068898893
        },
        "LGM": {
            "count": 20,
            "percentile": 99.96354555893772
        }
    },
    "2019-09-01": {
        "Active": {
            "count": 58265,
            "percentile": 0.0
        },
        "Expert+": {
            "count": 11493,
            "percentile": 80.27460739723676
        },
        "CM+": {
            "count": 3880,
            "percentile": 93.3407706170085
        },
        "M+": {
            "count": 1829,
            "percentile": 96.86089419033725
        },
        "IM+": {
            "count": 547,
            "percentile": 99.06118596069682
        },
        "GM+": {
            "count": 357,
            "percentile": 99.38728224491547
        },
        "IGM+": {
            "count": 138,
            "percentile": 99.76315111988329
        },
        "LGM": {
            "count": 22,
            "percentile": 99.96224148287995
        }
    },
    "2019-10-01": {
        "Active": {
            "count": 59849,
            "percentile": 0.0
        },
        "Expert+": {
            "count": 11653,
            "percentile": 80.529332152584
        },
        "CM+": {
            "count": 4054,
            "percentile": 93.22628615348627
        },
        "M+": {
            "count": 1936,
            "percentile": 96.76519240087553
        },
        "IM+": {
            "count": 585,
            "percentile": 99.02254005914885
        },
        "GM+": {
            "count": 382,
            "percentile": 99.36172701298267
        },
        "IGM+": {
            "count": 154,
            "percentile": 99.74268575916055
        },
        "LGM": {
            "count": 22,
            "percentile": 99.96324082273722
        }
    },
    "2019-11-01": {
        "Active": {
            "count": 63011,
            "percentile": 0.0
        },
        "Expert+": {
            "count": 12046,
            "percentile": 80.8827030201076
        },
        "CM+": {
            "count": 4090,
            "percentile": 93.5090698449477
        },
        "M+": {
            "count": 1933,
            "percentile": 96.93228166510609
        },
        "IM+": {
            "count": 599,
            "percentile": 99.04937233181508
        },
        "GM+": {
            "count": 396,
            "percentile": 99.37153830283602
        },
        "IGM+": {
            "count": 170,
            "percentile": 99.73020583707607
        },
        "LGM": {
            "count": 24,
            "percentile": 99.96191141229309
        }
    },
    "2019-12-01": {
        "Active": {
            "count": 66892,
            "percentile": 0.0
        },
        "Expert+": {
            "count": 12650,
            "percentile": 81.08891945225139
        },
        "CM+": {
            "count": 4378,
            "percentile": 93.45512168869222
        },
        "M+": {
            "count": 2046,
            "percentile": 96.941338276625
        },
        "IM+": {
            "count": 628,
            "percentile": 99.0611732344675
        },
        "GM+": {
            "count": 411,
            "percentile": 99.38557675058303
        },
        "IGM+": {
            "count": 182,
            "percentile": 99.72791963164504
        },
        "LGM": {
            "count": 25,
            "percentile": 99.96262632302816
        }
    },
    "2020-01-01": {
        "Active": {
            "count": 68560,
            "percentile": 0.0
        },
        "Expert+": {
            "count": 13103,
            "percentile": 80.88827304550759
        },
        "CM+": {
            "count": 4546,
            "percentile": 93.36931155192532
        },
        "M+": {
            "count": 2028,
            "percentile": 97.04200700116687
        },
        "IM+": {
            "count": 660,
            "percentile": 99.03733955659277
        },
        "GM+": {
            "count": 444,
            "percentile": 99.35239206534422
        },
        "IGM+": {
            "count": 186,
            "percentile": 99.72870478413068
        },
        "LGM": {
            "count": 28,
            "percentile": 99.95915985997667
        }
    },
    "2020-02-01": {
        "Active": {
            "count": 70732,
            "percentile": 0.0
        },
        "Expert+": {
            "count": 13363,
            "percentile": 81.10756093423062
        },
        "CM+": {
            "count": 4591,
            "percentile": 93.50930272012667
        },
        "M+": {
            "count": 2061,
            "percentile": 97.08618447096082
        },
        "IM+": {
            "count": 672,
            "percentile": 99.04993496578635
        },
        "GM+": {
            "count": 459,
            "percentile": 99.35107165073799
        },
        "IGM+": {
            "count": 187,
            "percentile": 99.735621783634
        },
        "LGM": {
            "count": 27,
            "percentile": 99.96182774416106
        }
    },
    "2020-03-01": {
        "Active": {
            "count": 71695,
            "percentile": 0.0
        },
        "Expert+": {
            "count": 13861,
            "percentile": 80.66671315991353
        },
        "CM+": {
            "count": 4814,
            "percentile": 93.28544528907176
        },
        "M+": {
            "count": 2172,
            "percentile": 96.97050003486993
        },
        "IM+": {
            "count": 704,
            "percentile": 99.01806262640352
        },
        "GM+": {
            "count": 484,
            "percentile": 99.32491805565242
        },
        "IGM+": {
            "count": 209,
            "percentile": 99.70848734221354
        },
        "LGM": {
            "count": 31,
            "percentile": 99.95676128042402
        }
    },
    "2020-04-01": {
        "Active": {
            "count": 78064,
            "percentile": 0.0
        },
        "Expert+": {
            "count": 14803,
            "percentile": 81.03735396597664
        },
        "CM+": {
            "count": 5080,
            "percentile": 93.49251895880303
        },
        "M+": {
            "count": 2384,
            "percentile": 96.94609551137528
        },
        "IM+": {
            "count": 742,
            "percentile": 99.04949784791965
        },
        "GM+": {
            "count": 502,
            "percentile": 99.35693789711006
        },
        "IGM+": {
            "count": 213,
            "percentile": 99.72714695634352
        },
        "LGM": {
            "count": 34,
            "percentile": 99.95644599303135
        }
    },
    "2020-05-01": {
        "Active": {
            "count": 84375,
            "percentile": 0.0
        },
        "Expert+": {
            "count": 16181,
            "percentile": 80.82251851851852
        },
        "CM+": {
            "count": 5695,
            "percentile": 93.25037037037038
        },
        "M+": {
            "count": 2526,
            "percentile": 97.00622222222222
        },
        "IM+": {
            "count": 782,
            "percentile": 99.07318518518518
        },
        "GM+": {
            "count": 515,
            "percentile": 99.38962962962962
        },
        "IGM+": {
            "count": 221,
            "percentile": 99.73807407407408
        },
        "LGM": {
            "count": 36,
            "percentile": 99.95733333333334
        }
    },
    "2020-06-01": {
        "Active": {
            "count": 91526,
            "percentile": 0.0
        },
        "Expert+": {
            "count": 17102,
            "percentile": 81.31459913030177
        },
        "CM+": {
            "count": 5988,
            "percentile": 93.45759674846492
        },
        "M+": {
            "count": 2942,
            "percentile": 96.78561283132662
        },
        "IM+": {
            "count": 797,
            "percentile": 99.12920918646068
        },
        "GM+": {
            "count": 525,
            "percentile": 99.42639250049166
        },
        "IGM+": {
            "count": 228,
            "percentile": 99.75089045735638
        },
        "LGM": {
            "count": 32,
            "percentile": 99.96503725717282
        }
    },
    "2020-07-01": {
        "Active": {
            "count": 95717,
            "percentile": 0.0
        },
        "Expert+": {
            "count": 17265,
            "percentile": 81.96245181106805
        },
        "CM+": {
            "count": 6202,
            "percentile": 93.52048225498083
        },
        "M+": {
            "count": 3156,
            "percentile": 96.70278007041591
        },
        "IM+": {
            "count": 812,
            "percentile": 99.15166584828191
        },
        "GM+": {
            "count": 517,
            "percentile": 99.45986606349969
        },
        "IGM+": {
            "count": 214,
            "percentile": 99.77642425065558
        },
        "LGM": {
            "count": 28,
            "percentile": 99.97074709821662
        }
    },
    "2020-08-01": {
        "Active": {
            "count": 98330,
            "percentile": 0.0
        },
        "Expert+": {
            "count": 17161,
            "percentile": 82.54754398454185
        },
        "CM+": {
            "count": 6459,
            "percentile": 93.43130275602563
        },
        "M+": {
            "count": 3200,
            "percentile": 96.74565239499644
        },
        "IM+": {
            "count": 841,
            "percentile": 99.14471677006
        },
        "GM+": {
            "count": 544,
            "percentile": 99.4467609071494
        },
        "IGM+": {
            "count": 223,
            "percentile": 99.77321265127631
        },
        "LGM": {
            "count": 37,
            "percentile": 99.96237160581714
        }
    }
}

Plot for Experts:

Spoiler

Codes and files are available here.

Read more »

 
 
 
 
  • Vote: I like it
  • +111
  • Vote: I do not like it

By ShafinKhadem, history, 12 months ago, In English

As I couldn't find any easy way to find problem difficulty rating without seeing tags, I have written a python3 script to do it:

Code

Usage: Run the script. Input the contestId (from URL, e.g. 1148) to view rating of all problems of that contests. Input contestId/problemIndex (e.g. 1108/E2) to view rating of only that problem.

If the problem has no rating yet, it will print None. Exception will be thrown if it fails to connect to codeforces server or invalid input is given.

Read more »

 
 
 
 
  • Vote: I like it
  • +28
  • Vote: I do not like it

By ShafinKhadem, 2 years ago, In English

Though some articles of this topic are already available, as a beginner I found them quite hard. So I decided to write down my thoughts here, in case someone finds it useful. Sorry for poor formatting and poor English.

Using one BIT we can do range increment and point query: For increasing a[l...r] by val, tmp[l] += val, tmp[r+1] += -val. After any number of range updates, prefixSum(i) of tmp[] denotes total increment in a[i] till now. BIT supports both point increment and prefixSum query.

Using another BIT with this BIT, we can also calculate range query. Let, prefixSum(i) from first BIT is a[i] = a[i]*(i-(i-1)). Our target is to calculate prefixSumOFa(i) in O(logn).

Let, addend[i] = a[i - 1] * (i - 1) - a[i] * (i - 1). so, , assuming 1-based indexing and a[0] = a[n+1] = 0

if (a[i]==a[i-1]), addend[i] == 0. So, writing all non-zero elements of addend[] for an example a[]:

i                |   1   |   2   |   3   |   4   |   5   |   6   |   7   |   8   |   9   |

a[i]             |   0   |   3   |   3   |   0   |   0   |   2   |   2   |   2   |   0   |
addend[i]        |       | -3*1  |       |  3*3  |       | -2*5  |       |       |  2*8  |

Observation: prefixSumOFa(i) = a[i]*i + prefixSumOFaddend(i). In case you are confused about where a[i]*i come from, notice that if a[i] would be last element of a[], a[i]*i would be written in addend[i+1].

Now, to calculate prefixSumOFa(i), we can get a[i] from first BIT, for getting prefixSumOFaddend(i), we need to keep another BIT, BIT2. For increasing [l...r] by val, we need to update BIT2(l) += (-val*(l-1)) and BIT2(r+1) += val*r.

This method works even if updates overlap, as when updating [l...r], for i = [l+1...r], (a[i-1]-a[i]) remains the same, so append[i] = (a[i-1]-a[i])*(i-1) remains same. Just like previous example, only updating BIT2(l) and BIT2(r+1) is necessary. For example if we increase range [5...7] by 5 in previous example of a[]:

a[]              |   0   |   3   |   3   |   0   |   5   |   7   |   7   |   2   |   0   |
addend[]         |       | -3*1  |       |  3*3  | -5*4  | -2*5  |       |  5*7  |  2*8  |

Read more »

 
 
 
 
  • Vote: I like it
  • +26
  • Vote: I do not like it