Newtech66's blog

Codeforces Round #819 (Div. 1 + Div. 2) and Grimoire of Code Annual Contest 2022
By Newtech66, 2 years ago, In English

Hello Codeforces!

Grimoire of Code, the official Competitive Programming club of IIT Kharagpur, is happy to invite everyone to take part in Codeforces Round 819 (Div. 1 + Div. 2) and Grimoire of Code Annual Contest 2022 which will take place on Sep/06/2022 17:35 (Moscow time). This round will be rated for everyone.

You will be given 8 problems and 2 hours 15 minutes to solve them.

The problems have been authored and prepared by Grimoire of Code members Anubhav anubhavdhar Dhar, Debajyoti little_angel Dasgupta, and Mainak Newtech66 Roy.

We'd like to thank all the people who made this round possible:

We hope everyone will enjoy the contest.

See you on the leaderboard!

About Grimoire of Code:

Grimoire of Code is the official Competitive Programming club of IIT Kharagpur created by and for competitive programming enthusiasts. We promote competitive programming culture in our college, and provide a forum for interested minds to discuss their thoughts and ideas. We also conduct mock coding rounds for placements and internships in Indian colleges.

You can check out our Facebook page here.

You can check out the problems from last year's Annual Contest here.

Updates

UPD1: The contest duration has been extended to 2 hours 15 minutes.

UPD2: Score distribution: $$$500-1000-1500-2000-2250-2750-3250-3500$$$

UPD3: Congratulations to the winners!

  1. Benq
  2. tourist
  3. jiangly
  4. Maksim1744
  5. kotatsugame
  6. tatyam
  7. TLEwpdus
  8. gyh20
  9. turmax
  10. Radewoosh

UPD4: Editorial (editorial for F will be added soon) It is now added.

UPD5: The contest is unrated due to problem copying. Details.

  • Vote: I like it
  • -1094
  • Vote: I do not like it

Comments Comments (239)
| Write comment?
»
2 years ago, # |
  Vote: I like it +337 Vote: I do not like it
As a tester
→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it +65 Vote: I do not like it

    when asking for downvotes and asking for upvotes are unsurprisingly in the same SCC

    → Reply
    • »
      »
      »
      2 years ago, # ^ |
      ← Rev. 2   Vote: I like it -48 Vote: I do not like it 
      Mihai Eminescu

      Luceafărul

      A fost odată ca-n povești, A fost ca niciodată. Din rude mari împărătești, O prea frumoasă fată.

      Și era una la părinți Și mândră-n toate cele, Cum e Fecioara între sfinți Și luna între stele.

      Din umbra falnicelor bolți Ea pasul și-l îndreaptă Lângă fereastră, unde-n colț Luceafărul așteaptă.

      Privea în zare cum pe mări Răsare și străluce, Pe mișcătoarele cărări Corăbii negre duce.

      Îl vede azi, îl vede mâini, Astfel dorința-i gata; El iar, privind de săptămâni, Îi cade draga fată.

      Cum ea pe coate-și răzima Visând ale ei tâmple, De dorul lui și inima Și sufletu-i se împle.

      Și cât de viu s-aprinde el În orișicare sară, Spre umbra negrului castel Când ea o să-i apară.

      ...

      Și pas cu pas pe urma ei Alunecă-n odaie, Țesând cu recile-i scântei O mreajă de văpaie.

      Și când în pat se-ntinde drept Copila să se culce, I-atinge mâinile pe piept, I-nchide geana dulce;

      Și din oglindă luminiș Pe trupu-i se revarsă, Pe ochii mari, bătând închiși Pe fața ei întoarsă.

      Ea îl privea cu un surâs, El tremura-n oglindă, Căci o urma adânc în vis De suflet să se prindă.

      Iar ea vorbind cu el în somn, Oftând din greu suspină: - O, dulce-al nopții mele domn, De ce nu vii tu? Vină!

      Cobori în jos, luceafăr blând, Alunecând pe-o rază, Pătrunde-n casă și în gând Și viața-mi luminează!

      El asculta tremurător, Se aprindea mai tare Și s-arunca fulgerător, Se cufunda în mare;

      Și apa unde-au fost căzut În cercuri se rotește, Și din adânc necunoscut Un mândru tânăr crește.

      Ușor el trece ca pe prag Pe marginea ferestei Și ține-n mână un toiag Încununat cu trestii.

      Părea un tânăr voievod Cu păr de aur moale, Un vânăt giulgi se-ncheie nod Pe umerele goale.

      Iar umbra feței străvezii E albă ca de ceară - Un mort frumos cu ochii vii Ce scânteie-n afară.

      • Din sfera mea venii cu greu Ca să-ți urmez chemarea, Iar cerul este tatăl meu Și mumă-mea e marea.

      Ca în cămara ta să vin, Să te privesc de-aproape, Am coborât cu-al meu senin Și m-am născut din ape.

      O, vin'! odorul meu nespus, Și lumea ta o lasă; Eu sunt luceafărul de sus, Iar tu să-mi fii mireasă.

      Colo-n palate de mărgean Te-oi duce veacuri multe, Și toată lumea-n ocean De tine o s-asculte.

      • O, ești frumos, cum numa-n vis Un înger se arată, Dară pe calea ce-ai deschis N-oi merge niciodată;

      Străin la vorbă și la port, Lucești fără de viață, Căci eu sunt vie, tu ești mort, Și ochiul tău mă-ngheață.

      ...

      Trecu o zi, trecură trei Și iarăși, noaptea, vine Luceafărul deasupra ei Cu razele-i senine.

      Ea trebui de el în somn Aminte să-și aducă Și dor de-al valurilor domn De inim-o apucă:

      • Cobori în jos, luceafăr blând, Alunecând pe-o rază, Pătrunde-n casă și în gând Și viața-mi luminează!

      Cum el din cer o auzi, Se stinse cu durere, Iar ceru-ncepe a roti În locul unde piere;

      În aer rumene văpăi Se-ntind pe lumea-ntreagă, Și din a chaosului văi Un mândru chip se-ncheagă;

      Pe negre vițele-i de păr Coroana-i arde pare, Venea plutind în adevăr Scăldat în foc de soare.

      Din negru giulgi se desfășor Marmoreele brațe, El vine trist și gânditor Și palid e la față;

      Dar ochii mari și minunați Lucesc adânc himeric, Ca două patimi fără saț Și pline de-ntuneric.

      • Din sfera mea venii cu greu Ca să te-ascult ș-acuma, Și soarele e tatăl meu, Iar noaptea-mi este muma;

      O, vin', odorul meu nespus, Și lumea ta o lasă; Eu sunt luceafărul de sus, Iar tu să-mi fii mireasă.

      O, vin', în părul tău bălai S-anin cununi de stele, Pe-a mele ceruri să răsai Mai mândră decât ele.

      • O, ești frumos cum numa-n vis Un demon se arată, Dară pe calea ce-ai deschis N-oi merge niciodată!

      Mă dor de crudul tău amor A pieptului meu coarde, Și ochii mari și grei mă dor, Privirea ta mă arde.

      • Dar cum ai vrea să mă cobor? Au nu-nțelegi tu oare, Cum că eu sunt nemuritor, Și tu ești muritoare?

      • Nu caut vorbe pe ales, Nici știu cum aș începe - Deși vorbești pe înțeles, Eu nu te pot pricepe;

      Dar dacă vrei cu crezământ Să te-ndrăgesc pe tine, Tu te coboară pe pământ, Fii muritor ca mine.

      • Tu-mi cei chiar nemurirea mea În schimb pe-o sărutare, Dar voi să știi asemenea Cât te iubesc de tare;

      Da, mă voi naște din păcat, Primind o altă lege; Cu vecinicia sunt legat, Ci voi să mă dezlege.

      Și se tot duce... S-a tot dus. De dragu-unei copile, S-a rupt din locul lui de sus, Pierind mai multe zile.

      ...

      În vremea asta Cătălin, Viclean copil de casă, Ce umple cupele cu vin Mesenilor la masă,

      Un paj ce poartă pas cu pas A-mpărătesii rochii, Băiat din flori și de pripas, Dar îndrăzneț cu ochii,

      Cu obrăjei ca doi bujori De rumeni, bată-i vina, Se furișează pânditor Privind la Cătălina.

      Dar ce frumoasă se făcu Și mândră, arz-o focul; Ei, Cătălin, acu-i acu Ca să-ți încerci norocul.

      Și-n treacăt o cuprinse lin Într-un ungher degrabă. - Da' ce vrei, mări Cătălin? Ia du-t' de-ți vezi de treabă.

      • Ce voi? Aș vrea să nu mai stai Pe gânduri totdeauna, Să râzi mai bine și să-mi dai O gură, numai una.

      • Dar nici nu știu măcar ce-mi ceri, Dă-mi pace, fugi departe - O, de luceafărul din cer M-a prins un dor de moarte.

      • Dacă nu știi, ți-aș arăta Din bob în bob amorul, Ci numai nu te mânia, Ci stai cu binișorul.

      Cum vânătoru-ntinde-n crâng La păsărele lațul, Când ți-oi întinde brațul stâng Să mă cuprinzi cu brațul;

      Și ochii tăi nemișcători Sub ochii mei rămâie... De te înalț de subsuori Te-nalță din călcâie;

      Când fața mea se pleacă-n jos, În sus rămâi cu fața, Să ne privim nesățios Și dulce toată viața;

      Și ca să-ți fie pe deplin Iubirea cunoscută, Când sărutându-te mă-nclin, Tu iarăși mă sărută.

      Ea-l asculta pe copilaș Uimită și distrasă, Și rușinos și drăgălaș, Mai nu vrea, mai se lasă,

      Și-i zice-ncet: — Încă de mic Te cunoșteam pe tine, Și guraliv și de nimic, Te-ai potrivi cu mine...

      Dar un luceafăr, răsărit Din liniștea uitării, Dă orizon nemărginit Singurătății mării;

      Și tainic genele le plec, Căci mi le umple plânsul Când ale apei valuri trec Călătorind spre dânsul;

      Lucește c-un amor nespus, Durerea să-mi alunge, Dar se înalță tot mai sus, Ca să nu-l pot ajunge.

      Pătrunde trist cu raze reci Din lumea ce-l desparte... În veci îl voi iubi și-n veci Va rămânea departe...

      De-aceea zilele îmi sunt Pustii ca niște stepe, Dar nopțile-s de-un farmec sfânt Ce nu-l mai pot pricepe.

      • Tu ești copilă, asta e... Hai ș-om fugi în lume, Doar ni s-or pierde urmele Și nu ne-or ști de nume,

      Căci amândoi vom fi cuminți, Vom fi voioși și teferi, Vei pierde dorul de părinți Și visul de luceferi.

      ...

      Porni luceafărul. Creșteau În cer a lui aripe, Și căi de mii de ani treceau În tot atâtea clipe.

      Un cer de stele dedesubt, Deasupra-i cer de stele - Părea un fulger ne'ntrerupt Rătăcitor prin ele.

      Și din a chaosului văi, Jur împrejur de sine, Vedea, ca-n ziua cea dentâi, Cum izvorau lumine;

      Cum izvorând îl înconjor Ca niște mări, de-a-notul... El zboară, gând purtat de dor, Pân' piere totul, totul;

      Căci unde-ajunge nu-i hotar, Nici ochi spre a cunoaște, Și vremea-ncearcă în zadar Din goluri a se naște.

      Nu e nimic și totuși e O sete care-l soarbe, E un adânc asemene Uitării celei oarbe.

      • De greul negrei vecinicii, Părinte, mă dezleagă Și lăudat pe veci să fii Pe-a lumii scară-ntreagă;

      O, cere-mi, Doamne, orice preț Dar dă-mi o altă soarte, Căci tu izvor ești de vieți Și dătător de moarte;

      Reia-mi al nemuririi nimb Și focul din privire, Și pentru toate dă-mi în schimb O oră de iubire...

      Din chaos, Doamne,-am apărut Și m-aș întoarce-n chaos... Și din repaos m-am născut, Mi-e sete de repaos.

      • Hyperion, ce din genuni Răsai c-o-ntreagă lume, Nu cere semne și minuni Care n-au chip și nume;

      Tu vrei un om să te socoți Cu ei să te asameni? Dar piară oamenii cu toți, S-ar naște iarăși oameni.

      Ei numai doar durează-n vânt Deșerte idealuri - Când valuri află un mormânt, Răsar în urmă valuri;

      Ei doar au stele cu noroc Și prigoniri de soarte, Noi nu avem nici timp, nici loc Și nu cunoaștem moarte.

      Din sânul vecinicului ieri Trăiește azi ce moare, Un soare de s-ar stinge-n cer S-aprinde iarăși soare;

      Părând pe veci a răsări, Din urmă moartea-l paște, Căci toți se nasc spre a muri Și mor spre a se naște.

      Iar tu, Hyperion, rămâi Oriunde ai apune... Cere-mi cuvântul meu dentâi - Să-ți dau înțelepciune?

      Vrei să dau glas acelei guri, Ca dup-a ei cântare Să se ia munții cu păduri Și insulele-n mare?

      Vrei poate-n faptă să arăți Dreptate și tărie? Ți-aș da pământul în bucăți Să-l faci împărăție.

      Îți dau catarg lângă catarg, Oștiri spre a străbate Pământu-n lung și marea-n larg, Dar moartea nu se poate...

      Și pentru cine vrei să mori? Întoarce-te, te-ndreaptă Spre-acel pământ rătăcitor Și vezi ce te așteaptă.

      ...

      În locul lui menit din cer Hyperion se-ntoarse Și, ca și-n ziua cea de ieri, Lumina și-o revarsă.

      Căci este sara-n asfințit Și noaptea o să-nceapă; Răsare luna liniștit Și tremurând din apă

      Și umple cu-ale ei scântei Cărările din crânguri. Sub șirul lung de mândri tei Ședeau doi tineri singuri:

      • O, lasă-mi capul meu pe sân, Iubito, să se culce Sub raza ochiului senin Și negrăit de dulce;

      Cu farmecul luminii reci Gândirile străbate-mi, Revarsă liniște de veci Pe noaptea mea de patimi.

      Și de asupra mea rămâi Durerea mea de-o curmă, Căci ești iubirea mea dentâi Și visul meu din urmă.

      Hyperion vedea de sus Uimirea-n a lor față: Abia un braț pe gât i-a pus Și ea l-a prins în brațe...

      Miroase florile-argintii Și cad, o dulce ploaie, Pe creștetele-a doi copii Cu plete lungi, bălaie.

      Ea, îmbătată de amor, Ridică ochii. Vede Luceafărul. Și-ncetișor Dorințele-i încrede:

      • Cobori în jos, luceafăr blând, Alunecând pe-o rază, Pătrunde-n codru și în gând, Norocu-mi luminează!

      El tremură ca alte dăți În codri și pe dealuri, Călăuzind singurătăți De mișcătoare valuri;

      Dar nu mai cade ca-n trecut În mări din tot înaltul: - Ce-ți pasă ție, chip de lut, Dac-oi fi eu sau altul?

      Trăind în cercul vostru strâmt Norocul vă petrece, Ci eu în lumea mea mă simt Nemuritor și rece.

      1883, aprilie

      → Reply
  • »
    »
    2 years ago, # ^ |
    ← Rev. 2   Vote: I like it +60 Vote: I do not like it

    posting mind blowing meme to get upvotes :

    → Reply
»
2 years ago, # |
  Vote: I like it +60 Vote: I do not like it
As the leamder
→ Reply
»
2 years ago, # |
  Vote: I like it +52 Vote: I do not like it
As an author
→ Reply
»
2 years ago, # |
  Vote: I like it +30 Vote: I do not like it

Div 1+2 and 8 problems! Looking forward to it.

When will scoring distribution come out?

→ Reply
»
2 years ago, # |
  Vote: I like it +9 Vote: I do not like it

As a tester, I just hope everyone's super-super-supercalifragilisticexpialidocious performance on the contest.

→ Reply
»
2 years ago, # |
  Vote: I like it +30 Vote: I do not like it

As not a tester, I did not test this round.

→ Reply
»
2 years ago, # |
  Vote: I like it -10 Vote: I do not like it

I want contribution, I also want rating, I can't have both of them, So I choose rating instead of contribution.

→ Reply
»
2 years ago, # |
← Rev. 2   Vote: I like it +15 Vote: I do not like it

As a participant,I'm hoping for a great round!

→ Reply
»
2 years ago, # |
  Vote: I like it -262 Vote: I do not like it
As an author
→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it -8 Vote: I do not like it

    omg that thumbs up emoji looks fabulous

    → Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it -21 Vote: I do not like it

    also YOU SHOULDNT BRAINSTORM THE SOLUTIONS WITH OTHERS DURING CONTEST ITS AGAINST THE RULES

    (yes, I couldn't believe my eyes after reading that line)

    → Reply
    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it -22 Vote: I do not like it

      what's wrong with all this downvote, I'm just stating the facts. are they all cheaters or what

      → Reply
      • »
        »
        »
        »
        2 years ago, # ^ |
          Vote: I like it -251 Vote: I do not like it

        Come on dude! Isn't it obvious that, by "you guys", I meant everyone, brainstorm the solutions "individually"

        → Reply
        • »
          »
          »
          »
          »
          2 years ago, # ^ |
            Vote: I like it +76 Vote: I do not like it

          Well, yes, except for the fact that brainstorming, in common sense and as stated on this wikipedia page, is a "group creativity technique". Using a group creativity technique where there isn't a group would be a pain...

          → Reply
          • »
            »
            »
            »
            »
            »
            2 years ago, # ^ |
              Vote: I like it +6 Vote: I do not like it

            got downvoted for being right

            → Reply
          • »
            »
            »
            »
            »
            »
            2 years ago, # ^ |
              Vote: I like it +3 Vote: I do not like it

            now this is a comeback

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              2 years ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              help me, this comeback has reversed somehow

              → Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it +7 Vote: I do not like it

    after the contest, I realized.

    You (plural) might have tried your best to make the problems as interesting as possible, but you (singular) didn't! Shame on you!

    → Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    F*ck you problem stoler.

    Let's downvote him to make his contribution lower than zxyoi cuz it's the second time such situation happens

    → Reply
»
2 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

IIT KGP !orz

→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    What is IIT KGP?

    → Reply
    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it +10 Vote: I do not like it

      Indian Institute of Technology, Kharagpur. It's India's one of the best engineering institute.

      → Reply
»
2 years ago, # |
  Vote: I like it +6 Vote: I do not like it
As a pupil contestant
→ Reply
»
2 years ago, # |
  Vote: I like it +1 Vote: I do not like it

I hope I can do at least the first one

→ Reply
»
2 years ago, # |
  Vote: I like it +91 Vote: I do not like it

ff23f4eac312f8598394447d6c543af0dc0a11f1

→ Reply
»
2 years ago, # |
  Vote: I like it +50 Vote: I do not like it

Really happy to see IIT KGP finally setting contests in Codeforces. Kudos to the entire team of problemsetters.

→ Reply
»
2 years ago, # |
← Rev. 2   Vote: I like it +10 Vote: I do not like it

I love div.1 + div.2 contests
Good luck for everyone!!
Hoping for a nice problems❤️

→ Reply
»
2 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Is it rated for DIV 2 ?

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Hoping to solve 4 problems, would be great

→ Reply
»
2 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Hope to become as soon as possible Candidate Master.

→ Reply
»
2 years ago, # |
  Vote: I like it +6 Vote: I do not like it
As a xxx

Here is: hided content

The above comment is edited as follows:

<div class="spoiler">
  <b class="spoiler-title">As a xxx</b>
  <div class="spoiler-content" style="display: none;">
    <p>Give me xxx</p>
  </div>
</div>

Here is: <span style="color: white;">hided content</span>
→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

good luck everyone and hope the problems this time is not mathforces qwq

→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    some moderate amount of math is fine, last time it was kinda excessive but the problems were very interesting

    → Reply
»
2 years ago, # |
  Vote: I like it -12 Vote: I do not like it

Contest time collides with IND VS AFG cricket match. Very unfortunate.

→ Reply
»
2 years ago, # |
  Vote: I like it +1 Vote: I do not like it

All the Best EveryOne!

→ Reply
»
2 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Good luck to all

→ Reply
»
2 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Sometimes you win, sometimes you learn

→ Reply
»
2 years ago, # |
  Vote: I like it +9 Vote: I do not like it

We just got trolled

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve D?

→ Reply
  • »
    »
    2 years ago, # ^ |
    ← Rev. 2   Vote: I like it +1 Vote: I do not like it

    Color everything in blue. Now do a DFS from node 1. Since m is at most n+2, you will get at most 3 back edges. Store those back edges while traversing by dfs.

    Now you have obtained some tree rooted in node 1, with some back edges. Now if you have less than 3 back edges, simply color those back edges as red.

    If you have 3 back edges, and they form a triangle, in other words have form a-b, b-c, a-c, color a-b and b-c as red. Now look at a-c. Coloring this as red would be a waste, because a, b, c are already connected. So instead leave it as blue. Find out whether a or c has a greater depth in the DFS tree. Let’s say d = deepest(a, c). Color the edge d and parent[d] in red. This way we preserve the tree structure of the blue subgraph and decrement the number of connected components in the red subgraph.

    If you have 3 back edges that do not form such a triangle/cycle. Just color them in red.

    I highly suggest drawing a tree structure with back edges to understand it better.

    → Reply
»
2 years ago, # |
  Vote: I like it +17 Vote: I do not like it

C was so good :D

→ Reply
»
2 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Very goood problems A, B, C!

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve C? Any hints

→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Look at number of index i, such that s[i]='(' and s[i+1]!=')'

    → Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    I just use DSU.

    → Reply
    • »
      »
      »
      2 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      How is its time complexity?

      → Reply
      • »
        »
        »
        »
        2 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I don't calculate but get only 31 ms.

        → Reply
        • »
          »
          »
          »
          »
          2 years ago, # ^ |
          ← Rev. 2   Vote: I like it +22 Vote: I do not like it

          oh. that's fast. maybe the time complexity is $$$O(\text{fastenough})$$$.

          → Reply
    • »
      »
      »
      2 years ago, # ^ |
      ← Rev. 3   Vote: I like it 0 Vote: I do not like it

      DSU here how? If you could explain your thought process it would be helpful

      → Reply
      • »
        »
        »
        »
        2 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I use DSU and at the last step count the different number or parent.If make count+1 at '(' and count-1 at ')' you will see that all i for 1 to 2*n where count =1 or count=0 are conected. I use this obserbation to solve. Sorry for my poor English.

        → Reply
      • »
        »
        »
        »
        2 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Link every opening bracket to it's corresponding closing bracket. Whenever there is a ")(" in the string link those two brackets to handle the "()()" case where 1 needs to connect to 4.

        → Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    the number of positions such that s[i] = s[i+1] = ')'

    → Reply
»
2 years ago, # |
  Vote: I like it +233 Vote: I do not like it

F is shit.

→ Reply
»
2 years ago, # |
  Vote: I like it +9 Vote: I do not like it

Problem C was nice.

→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Wut it's easier than A, I'm mad because of B not saying it's hard but I'm so stupid and slow

    → Reply
    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      me here, getting 150 on A :(((((((((((((((

      → Reply
    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Good sir, can I know how you made that observation for C?
      I have never been so mad at a problem T-T

      → Reply
      • »
        »
        »
        »
        2 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I noticed that () () () for example is all connected then I assumed that all of are disconnected and everytime i see () then this one is connected to another sequence

        → Reply
        • »
          »
          »
          »
          »
          2 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          "I assumed that all of" you mean 'other' instead of 'of', right?
          Also, Thanks but I don't know why I couldn't think of this. Would it be lack of practice of 1400-1500 rated problems?

          → Reply
          • »
            »
            »
            »
            »
            »
            2 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            It needs some luck i may haven't noticed it but if we are trained on graphs it won't be a problem

            → Reply
      • »
        »
        »
        »
        2 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I JUST use DSU and at the last step count the different number or parent.If make count+1 at '(' and count-1 at ')' you will see that all i for 1 to 2*n where count =1 or count=0 are conected. I use this obserbation to solve. Sorry for my poor English.

        → Reply
        • »
          »
          »
          »
          »
          2 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Thank you! I guess having a bit more knowledge of dsu might have helped ;(

          → Reply
          • »
            »
            »
            »
            »
            »
            2 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            It doesn't need any of that just a for loop would work

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              2 years ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              Yea true, what I actually meant was, maybe knowing dsu well might have given me a different perspective because I couldn't make that observation.

              → Reply
      • »
        »
        »
        »
        2 years ago, # ^ |
        ← Rev. 2   Vote: I like it +3 Vote: I do not like it

        here's my crude drawing during contest for C, if it might help:

        notice how the component count increases for every two decreasing (or increasing, as others pointed out) steps in a row.

        → Reply
        • »
          »
          »
          »
          »
          2 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Ohh nice, I will try this idea after few days and see if I can get the approach. Honestly, what I did was to notice the how deep the opening bracket's are going and counted them.
          For eg. ( ( ( ) ) ), depth was 2.

          And for this ( ( ) ) ( ( ) ), the depth for both first and second balanced sequence is 1. So, it becomes 2 and added 1 for the remaining component. And, it even passed for all given TCs, which made me believe theres something wrong in the code and not in observation.

          I get riddled in my own ideas ;-;

          → Reply
      • »
        »
        »
        »
        2 years ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        What i thought is when the string is ((())) complete then the answer is n but the time you take out a () outside, a component decreases. So calculate no of instant parenthesis. We already have 1 instant parenthesis in the starting case. So answer will be n-(instant-1).

        → Reply
        • »
          »
          »
          »
          »
          2 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Ohh wow, this actually makes sense to me. Wish I would have thought a bit in this direction.
          Alsoo, Congrats on specialist!!

          → Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    i messed up preety badly at c

    → Reply
»
2 years ago, # |
  Vote: I like it +40 Vote: I do not like it

Problem F is boring and hard to implement :(

→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Any hints for D?

    → Reply
    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      The connected components are trees.

      → Reply
      • »
        »
        »
        »
        2 years ago, # ^ |
        ← Rev. 2   Vote: I like it +3 Vote: I do not like it

        Could you explain how to find spanning tree such that remaining 3 edges don't form a cycle( triangle )?

        → Reply
        • »
          »
          »
          »
          »
          2 years ago, # ^ |
            Vote: I like it +30 Vote: I do not like it

          Random algorithm .

          → Reply
        • »
          »
          »
          »
          »
          2 years ago, # ^ |
            Vote: I like it +34 Vote: I do not like it

          Determenistic solution: Do a DFS, for every vertex record parent and depth in DFS tree, find the 3 additional edges. If the edges do form a cycle, take any of the 3 edges (let's say (u-v), where depth[u] > depth[v]) and replace it with edge (u-parent[u]).

          → Reply
        • »
          »
          »
          »
          »
          2 years ago, # ^ |
            Vote: I like it +32 Vote: I do not like it

          Find any tree, then, if the remaining edges form a cycle, build a new tree with one edge of this cycle in it. It will guarantee that the new tree is ok.

          → Reply
      • »
        »
        »
        »
        2 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Nope, for an example, in test case 2, you have one connected component and it is cycle.

        → Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    By the way , The $$$O(n\times \sqrt{nlog_2n})$$$ solution may be easier to implement.

    → Reply
»
2 years ago, # |
  Vote: I like it +1 Vote: I do not like it

hints for D?

→ Reply
  • »
    »
    2 years ago, # ^ |
    ← Rev. 3   Vote: I like it +3 Vote: I do not like it

    I also failed it, my approach was this:

    1. use union find to color all red without loops

    2. at the end at most 3 blue edges will be left over

    3. if those three blue edges happen to form a loop, swap the last blue edge with one of the red edges -> there will be no blue loop any more

    4. my problem was I didn't know how to select the correct red edge to swap with, since for some red edges you will create a red-cycle

    → Reply
    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      You have to check if the edge you are changing from blue -> red should not be between an ancestor and child in the red tree

      → Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it
    Hint 1
    Hint 2
    Hint 3
    Solution
    → Reply
    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      How is this optimal?

      → Reply
      • »
        »
        »
        »
        2 years ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        Each edge has to decrease number of either red components or blue components, and it can only decrese one of those by exactly 1. Thus, the optimal value is $$$2 * n - m$$$. In case of there not being a triangle we have exactly this value with the above method. In case of triangle also this value, but it's a little bit harder to see.

        → Reply
»
2 years ago, # |
← Rev. 2   Vote: I like it +34 Vote: I do not like it

Defeated by the memory limit of problem F.

I wrote a segement tree without optimizing anything in the last minutes, using the memory of $$$O(n\log n)$$$. When I noticed the memory limits I didn't have time to make a change.

→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    Same here. 256MB is unnecessarily too tight! Lose the chance to gain rating.

    → Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it +20 Vote: I do not like it

    My ST table didn't get MLE.

    However, I forgot to check whether there's a time which can reach n without passing any red lights and got WA on test 7. What a pity.

    → Reply
»
2 years ago, # |
  Vote: I like it +3 Vote: I do not like it

What is the expected time complexity for D?

→ Reply
»
2 years ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

Can we solve D by randomizing? My idea is you only need to randomize m — n + 1 edges, and check if any of the two sets create a cycle. m-n+1 is at most 3 so it should be fast enough?

The proof of correctness is that, if the graph is a tree, obviously it makes no difference how the edges are allocated. If we have extra edges, then every edges will reduce the connected component by 1, so we make a tree for the blue, and the rest for red, as long as they are both trees.

→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it +12 Vote: I do not like it

    Make MST. Pick the $$$m-(n-1)$$$ edges not in MST. Only when $$$m = n+2$$$ can these edges create a cycle. If they do, then take one edge and transfer it to other color and the edge to its parent to current color, provided that the swapped edge is not in its subtree.

    → Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

What is a 'connected component' in Problem D? In the first example, it says blue edges form 2 components, but I only see 1.

→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    $$$1,2,3,5$$$ was one component, $$$4$$$ was the other

    → Reply
»
2 years ago, # |
  Vote: I like it +41 Vote: I do not like it

F is so annoying to implement (256MB memory limit makes it even worse!). But D and E are interesting.

→ Reply
  • »
    »
    2 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    How to solve E? I thought its about calculating sums of $$$\frac{P^n_{2k}}{2^k k!}$$$ or smth for $$$1\leq k \leq \lfloor \frac{n}{2} \rfloor$$$

    (sorry about the big text, things were becoming unreadable)

    → Reply
    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yeah, the way you do that subproblem is by thinking about it conceptually instead of combinatorially. You're trying to find the ways to pair some elements from n things. This can be written as a dp[n] = dp[n-1] + (n-1)*dp[n-2] (you either pair the first element with something, or u don't), which can be precomputed before you do the loop over number of 4-cycles.

      → Reply
    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Instead of permutations I thought about the problem with cycles (by building the graph of the permutation). To be almost perfect, cycles either have length 1 (pointing to itself) or length 2 (pointing to each other) or length 4, see picture. Rest was combinatorics. I will link my solution after the grading finished (was 7 minutes too late sadly...). I iterated over the amount of length-4 cycles.

      → Reply
      • »
        »
        »
        »
        2 years ago, # ^ |
        ← Rev. 2   Vote: I like it +8 Vote: I do not like it

        OHHHHHHH. I was thinking about cycles too, in this process I came up with that formula. totally missed the length-4 cycles though. E was a good problem after all!

        → Reply
        • »
          »
          »
          »
          »
          2 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          171160691.

          First I calculated $$$P_i$$$ by this recursion: $$$P_0=1$$$, $$$P_1=1$$$, $$$P_i=P_{i-1}+(i-1)\cdot P_{i-2}$$$. This is the amount of partitions of $$$i$$$ elements into sets of size $$$1$$$ and $$$2$$$.

          Then we calculate the following:

          $$$\sum_{i=0}^{4i\le n} \binom{n-2i}{2i} (2i-1)!! \cdot 2^i P_{n-4i} $$$

          The sum goes over the amount of length-$$$4$$$ cycles. The binomial calculates how many different distributions for $$$2i$$$ neighbouring 2-tile-pairs there are. The Double Factorial is the amount of combinations to form $$$4$$$-tile-cycles by choosing $$$2$$$ each from the previously distributed $$$2$$$-tile-pairs. Each $$$4$$$-tile cycle then can have 2 different orientations, so we need to multiply by $$$2^i$$$. Then $$$P_{n-4i}$$$ is the amount of combinations to form $$$1$$$ or $$$2$$$ tile pairs from the remaining nodes.

          → Reply
»
2 years ago, # |
← Rev. 7   Vote: I like it +5 Vote: I do not like it

why getting TLE at problem B? someone help me 

t = int(input())
while t>=1:
    n,m = map(int,input().split())
    if m<n:
        print("No")
 
    elif n%2 == 0 and m%2 !=0 :
        print("No")
 
    else:
        ans = []
        if n%2 !=0:
            ans = [1] * (n-1)
            a = m - (n-1)
            ans.append(a)
        else:
            ans = [1] * (n-2)
            a = (m - (n-2))//2
            ans.append(a)
            ans.append(a)
 
        print("Yes")
        for i in range(len(ans)):
            if i == len(ans)-1:
                print(ans[i])
            else: print(ans[i],end= " ")
    t-=1
→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    @u1602016 You are not decrementing variable t, so it continues to loop forever :)

    → Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Same problem. TLE with Python/PyPy3 (pretest 4), OK with C++ (system testing). Slow input/output in Python, maybe.

    Is it possible to get pretest 4 for experiments?

    Submission https://codeforces.me/contest/1726/submission/171110352 Room (with the other submissions with slightly smodified input/output) https://codeforces.me/contest/1726/room/464

    → Reply
    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      The way it works is that the input function in Python calls sys.stdout.flush. So everytime you call input you flush stdout, which can be really slow. The way to get around this is to use sys.stdin.readline instead of input. Worth noting is that input internally calls sys.stdin.readline.

      If you take a look at C++ submissions will probably see cin.tie(0), which is how you turn off this very same feature in C++.

      Knowing how to avoid flushing can be very useful in general. For example your (savsmail) C++ submission speeds up by a factor of 16 by avoiding to flush 171253842 .

      → Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    @u1602016 yes, the problem is with the slow I/O in python as it takes 5-10 times more to run compare to c/c++.

    For the cross-check part I have also converted your solution in c++, and tried to submit, and it works perfectly fine within time(561ms, note: your solution is correct) here

    Solution??? you could either use the fast I/O for python while doing CP (as @Varad2002 mentioned) or you could use c++ for CP (I would personally recommend this, as I have experienced the situation where my JAVA code throws TLE (even after using fast I/O) whereas same algorithm works within time limit in C++)

    → Reply
»
2 years ago, # |
  Vote: I like it +8 Vote: I do not like it

I couldn't enjoy this contest :(, might be very clever problems.

→ Reply
»
2 years ago, # |
  Vote: I like it +9 Vote: I do not like it

hint for c?

→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    )(

    → Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it +12 Vote: I do not like it
    Spoiler 1
    Spoiler 2
    Solution
    → Reply
    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Was this easy to catch this observation as i tried to solve trivally by making DSU but not able to do it

      → Reply
      • »
        »
        »
        »
        2 years ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        Phew, well, depends on your understanding of easy. As I was solving the problem, the Spoilers/Solution which I posted reconstruct my thought process. And I'd say I have noticed them pretty quickly. I didn't even consider building the graph explicitly (and using DSU or similar) yet.

        I guess the first thing you want to do is find observations about the structure of the problem. Only if you can't find any structure, you take out the harder techniques. And then try to find structure on the harder techniques. And always user pen and paper!

        → Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Any hints for E?

→ Reply
»
2 years ago, # |
  Vote: I like it +9 Vote: I do not like it

Really nice problems ! Keep it up authors ^_^

→ Reply
»
2 years ago, # |
  Vote: I like it +16 Vote: I do not like it

D: randomly color all edges. Break if both colors do not form cycles.

→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it +20 Vote: I do not like it

    We tried our best to break such solutions, but it seems it was not enough :(

    → Reply
    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it +13 Vote: I do not like it

      I would like to know how to break (or attempt to) these kind of solutions.

      → Reply
      • »
        »
        »
        »
        2 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        My attempts were primarily focused on maximising the number of tests, with $$$n+2$$$ edges in every case, with graphs of ~1e3 (I think?) size. So mostly randomisation. I didn't have much hope of blocking everything because of the small number of extra edges compared to the number of possible spanning trees. If anyone has better ideas, I would be very interested to know...

        → Reply
    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it +21 Vote: I do not like it

      Break? Isn't that correct?

      → Reply
      • »
        »
        »
        »
        2 years ago, # ^ |
          Vote: I like it +8 Vote: I do not like it

        Some of our testers' solutions using the same idea didn't pass, so I assumed it is incorrect.

        Of course, if the number of iterations are sufficient it should pass with high probability. Admittedly, I did not do a thorough analysis of a randomised solution because the model solution does not use randomisation.

        → Reply
        • »
          »
          »
          »
          »
          2 years ago, # ^ |
            Vote: I like it +17 Vote: I do not like it

          Well, this one looks way simpler than anything with some logic inside. I'm talking about the version with a guess that we can achieve maximum possible score ($$$2n - m$$$) and we repeat until we succeed.

          The intuition for me was that if it's anyhow hard/not straightforward to color the edges so that there are no cycles, these additional edges (yes, it's relative which ones are additional, but I'm talking about kind of a part of the graph in which something interesting happens) have to be close to each other, so the "hard" part of the graph is small, so there are not so many possibilities and we will find good one quickly.

          → Reply
  • »
    »
    2 years ago, # ^ |
    ← Rev. 2   Vote: I like it +1 Vote: I do not like it

    I did this: Colored red if nodes are in different disjoint sets, blue otherwise. However, for m=n+2, there is a possibility of a cycle of 3 formed.

    In that case, I made this observation: Suppose the 3-cycle is ABC then there is a node in A,B,C say A, such that AB and AC are connected using red. Then just take the last edge in the AB red path and make it blue, and make AB(blue) as red. It can be seen that this removes cycles in both red and blue.

    → Reply
»
2 years ago, # |
  Vote: I like it +6 Vote: I do not like it

Really enjoyed the contest, especially because all the questions were not only mathematics based. Also, waiting to submit D, solved just after the time ended. Same thing happening for the second time :')

→ Reply
»
2 years ago, # |
  Vote: I like it +16 Vote: I do not like it

Code of Problem C <<< Solving Problem C

→ Reply
»
2 years ago, # |
  Vote: I like it -13 Vote: I do not like it

wait what the heck

Spoiler
→ Reply
»
2 years ago, # |
  Vote: I like it -14 Vote: I do not like it

I had to gain only 2 points to reach CM, and solved D on paper, started coding it more than 1 hr before the end, but in the end got TL 9 because i use maps which work slow. But my idea was fully correct. Now end up losing 7 points, and only 9 will be left before CM. this is fucking disqusting, it will be already 5th time when i have <10 points bafore CM!

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Isn't $$$1.205710448301$$$ the answer for the first sample in H? I've checked that in geogebra and it seems to be so.

→ Reply
  • »
    »
    2 years ago, # ^ |
    ← Rev. 2   Vote: I like it +8 Vote: I do not like it

    Are you sure it's the first sample? I mean to say, you don't mean the second sample by any chance, right?

    → Reply
    • »
      »
      »
      2 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      I think so, here's the geogebra link: we are looking for the area bounded by $$$AB$$$, $$$AC$$$, and the circle passing through H and center O.

      → Reply
      • »
        »
        »
        »
        2 years ago, # ^ |
          Vote: I like it +26 Vote: I do not like it

        The area is bounded by a curve, but not an arc

        → Reply
      • »
        »
        »
        »
        2 years ago, # ^ |
          Vote: I like it +8 Vote: I do not like it

        If you are using a circle as an envelope for the red part, that's incorrect. The curve is not a circle.

        Check this: Click here

        → Reply
»
2 years ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

My solution to problem C passsed system tests, Even though I am pretty sure its so different from the intended solution

I solved with a sparse table and DSU, I am interested to know if the solution is correct and actually fast enough (I am 99% sure its fast enough but I don't know about its validity)

Can Someone Verify?
Submission : https://codeforces.me/contest/1726/submission/171128759

→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it -8 Vote: I do not like it

    do note that a lot of the faster ones (usually in Div1) solved it with DSU

    → Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I too solved it using seg tree and DSU.

    → Reply
»
2 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Back to back bad performance from me, hope I can bounce back soon. People who are in a phase like me, "This shall pass too" :)

→ Reply
»
2 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Check out this ridiculously easy solution for C: 171112911 (don't pay attention to that bin_power_of_two function — I forgot to delete it)

→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    The interesting thing is that I haven't found any of the red guys yet who would have approached the problem the same way.

    → Reply
    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      yes, because for them, the simpler (in the sense of observation) DSU implementation came first in mind.

      → Reply
      • »
        »
        »
        »
        2 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Could you explain the DSU solution?

        → Reply
        • »
          »
          »
          »
          »
          2 years ago, # ^ |
            Vote: I like it +3 Vote: I do not like it

          they just constructed the DSU like how they would do a normal graph and counted the components like how they would do a normal graph. only tricky part is what to merge and that's it

          → Reply
    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it -8 Vote: I do not like it

      171072071

      → Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    literally ('('+input()+')').count('))') in python.

    → Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Even this works

    → Reply
    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it 
          ll ans=1;
    forsn(i,1,2*n){
        if(s[i]=='(' && s[i-1]=='(') ans++;
    }
      → Reply
»
2 years ago, # |
  Vote: I like it -10 Vote: I do not like it

These unfamiliar names kinda throw me off the track. Wish we could use simpler names

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

If the current problem C(bracket sequence) were problem A, would it have been as difficult as it is now?

→ Reply
»
2 years ago, # |
  Vote: I like it +5 Vote: I do not like it

My exactly same code got ac after system test

AC code : https://codeforces.me/contest/1726/submission/171155848 TLE code : https://codeforces.me/contest/1726/submission/171146706

code was same compiler was same.... Just for system test load my code got tle...Please @authors do something about this...MikeMirzayanov please do something

→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it -10 Vote: I do not like it

    code was same, compiler was same, the difference is the seed

    → Reply
    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      what is seed?

      → Reply
      • »
        »
        »
        »
        2 years ago, # ^ |
        ← Rev. 2   Vote: I like it -10 Vote: I do not like it

        the seed is the value an RNG uses to start with. in your code this is chrono::steady_clock::now().time_since_epoch().count(), which varies by when the submission is run.

        → Reply
        • »
          »
          »
          »
          »
          2 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          I haven't used rng anywhere in my code...so it was not my fault at all.

          → Reply
          • »
            »
            »
            »
            »
            »
            2 years ago, # ^ |
              Vote: I like it -10 Vote: I do not like it

            oh, didn't notice it. turns out that your code barely just fit into the TL. I think you would've gotten hacked if this happened during competition, though.

            → Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    can you do something ? Newtech66

    → Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it +15 Vote: I do not like it

    Do you really think 1996ms solution for 2s problem is correct?

    → Reply
    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it -7 Vote: I do not like it

      How should I calculate this in contest time? Pretests got passed and even system tests too. But the judge load caused me TLE. Whats my fault here?

      → Reply
»
2 years ago, # |
← Rev. 2   Vote: I like it +116 Vote: I do not like it

On A, I saw a solution which initializes the answer with $$$|a_n-a_1|$$$ and, while I could've simply made a test case which breaks that solution very obviously, I instead decided to make fun of the pretests by hacking it with a test case of 50 tests with $$$n$$$ being a random number between $$$1$$$ and $$$6$$$ and $$$a_i$$$ being random numbers between $$$1$$$ and $$$10$$$. While most obviously wrong solutions like the one I hacked FSTd due to hacks specifically made against such solutions, this test case of 50 random tests also unintentionally caused FST of almost 100 solutions that don't work if a test with $$$n=1$$$ has a test right before it such that $$$a_2$$$ of the test right before the test with $$$n=1$$$ is greater than $$$a_1$$$ of the $$$n=1$$$ test.

→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it -13 Vote: I do not like it

    LOL that is awesome. this is a legend, as you are too

    → Reply
»
2 years ago, # |
  Vote: I like it +23 Vote: I do not like it

Why is the D's constraints so big? I can't understand why sum of N is 1e6. It is hard for python... (I passed pretest but got TLE on system test)

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Done C with DSU... how u guys come up with so easy solution...

→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it -13 Vote: I do not like it

    observation, but observation isn't all so easy. observation comes along with experience as well

    → Reply
    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I am not very comfortable with these graph problem as you can see from my rating that i havent encountered many graph problems till now . Do these graph problem usually have these kind observation asking wrt C

      And please guide my what i should do to reach specialist as while practicing i am comfortable upto *1500 problems but during contest i keep on getting stucked on problem C which are usually in the range of *1400 to *1600

      → Reply
      • »
        »
        »
        »
        2 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I am not very comfortable with these graph problem

        So am I! This was a different case though. I just drew some parentheses strings with pen and paper, like '(' = rising slope, ')' = falling slope. Then I connected what I needed to connect based on the statements. After that, it was a long phase of thinking, thinking hard. Usually time for thinking > time for coding, this is very normal. Accepting this is one crucial step to Specialist, imho.

        → Reply
»
2 years ago, # |
  Vote: I like it +10 Vote: I do not like it

Ratings updated preliminarily. We will remove cheaters and update the ratings again soon!

→ Reply
»
2 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Got Accept with FST code for D.
Why is this so slow? It's just O(NlogN) and N <= 1e6
Can someone explain?

https://codeforces.me/contest/1726/submission/171146699
https://codeforces.me/contest/1726/submission/171158814

→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    Same happened to me and costed me losing CM. @admins should look at this.

    → Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    maybe try having a function fix(pair p) that returns a sorted pair(smaller element before larger element). idk if it fixes your solution but it did work for my friend

    → Reply
»
2 years ago, # |
  Vote: I like it +18 Vote: I do not like it

Btw, I FST for D, but when I try to resubmit the exact same code, it passes (barely). Is it possible to reverse the FST?

→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    Faced the same issue. Not sure if they will take it into consideration, but I hope they do.

    → Reply
»
2 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Hello everyone, I'm a newbie participant. On problem A, although it runs perfectly on my computer, I got runtime error. How Can I fix this problem? I copy my code below. Thank you. (I use Microsoft Visual Studio BTW)

#include <iostream>

using namespace std;

int main() {

	int t;
	int n[1000];
	int s;
	int qr;
	int zr;
	int result;

	cin >> t;

	while (t--) {
		
		cin >> s;

		for (int i = 0; i < s; i++) {

			cin >> n[i];
		}

		for (int z = 0; z < s; z++) {
			
			for (int q = z; q < s; q++) {

				if (n[z] > n[q]) {

					zr = n[z];
					qr = n[q];
					n[z] = qr;
					n[q] = zr;

				}
				else {
					continue;
				}
			}
		}
		if (s == 1) {
			result = 0;
		}
		else {
			result = n[s - 1] - n[0];
		}

		cout << result << endl;
	}

	return 0;
}
→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    you need to increase the size of array. notice n<=2000 but you have declared an array of size 1000 only

    → Reply
»
2 years ago, # |
  Vote: I like it +4 Vote: I do not like it

After decades of the contest, Benq is on the top! Happy to see this (❁´◡`❁)

→ Reply
»
2 years ago, # |
  Vote: I like it +7 Vote: I do not like it

Just a shit

→ Reply
»
2 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Before I sleep,I saw my name turn green..What F???

→ Reply
»
2 years ago, # |
  Vote: I like it +3 Vote: I do not like it

lol everyone is downvoting this post and the editorial.

→ Reply
»
2 years ago, # |
  Vote: I like it -15 Vote: I do not like it

The coding club of IIT KGP is gonna face a lot of disrepute now becoz of you guys

→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Exactly , they may set 7 problems instead of 8 and time for 2 Hours would be better.

    → Reply
»
2 years ago, # |
← Rev. 2   Vote: I like it +58 Vote: I do not like it

A sincere request to everyone!

Newtech66 and anubhavdhar have worked really hard for this round and they weren't aware of what happened in problem F. If you don't like the problems(except F), feel free to downvote the blog, but please refrain from doing so if this is the only reason! It would be very unfair and unjustice with them :(

→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it -38 Vote: I do not like it

    This is bullshit. I support downvoting the blog post because of F, it's high time all the authors start asking their co-authors how they developed the problems, so situations like this don't repeat. Every author of the round should be held equally accountable for each problem, and the round in general.

    → Reply
»
2 years ago, # |
  Vote: I like it -8 Vote: I do not like it

where is my ratings for this contest.

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Why this contest is Unrated?

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

my rating where is gone?!! i just reached pupil pls any information?

→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    https://codeforces.me/blog/entry/106700

    → Reply
    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it -6 Vote: I do not like it

      this is unfair who are they truly punishing if the author is cheater and has no morals why would he care if the round is rated or not he is just punishing the participants in fact there is a part of the problem on those who host contests the must make sure that the problem set is unique

      → Reply
»
2 years ago, # |
  Vote: I like it +3 Vote: I do not like it

This is has happened 2nd or 3rd time, that contest has been declared unrated due to picking problems from other platforms. Please make sure that problems are original beforehand. There goes a lot of effort in solving them and then finding that contest has been declared unrated just breaks the heart :( .

→ Reply