aryanc403's blog

By aryanc403, 2 months ago, In English

I'm currently live discussing the problems. I will add problemwise timestamp after the discussion stream, and also format the blog properly.
You can join in if something in this blog is unclear or you have more questions.

2025A - Two Screens

Idea

My submission — 285842091

2025B - Binomial Coefficients, Kind Of

Hint 1
Hint 2
Hint 3

My submission — 285848201

2025C - New Game

Solution 1: Hint
Solution 2: Hint

My submission — 285852480

2025D - Attribute Checks

Hint 1
Hint 2
Hint 3
Hint 4
Hint 5
Hint 6

My submission — 285868260

2025E - Card Game

Hint 1
Hint 2
Hint 3
Hint 4
Hint 5
Bonus

My submission — 285892958

2025F - Choose Your Queries

Hint 1
Hint 2
Hint 3
Hint 4
Hint 5
Hint 6
Hint 7

My submission — 285887128

Full text and comments »

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

By aryanc403, 3 months ago, In English

2013A - Zhan's Blender

Idea

Submission — 282005858

2013B - Battle for Survive

Hint 1
Hint 2
Hint 3

Submission — 282011553

2013C - Password Cracking

Hint 1
Hint 2
Hint 3
Hint 3

Submission — 282024928

2013D - Minimize the Difference

Hint 1
Hint 2
Hint 3
Hint 4
Hint 5
Hint 6

Submission — 282029106

2013E - Prefix GCD

Hint 1
Hint 2
Hint 3
Hint 4

Submission — 282034547

2013F1 - Game in Tree (Easy Version)

Hint 1
Hint 2
Hint 3
Hint 4
Hint 5
Hint 6
Hint 7

Submission — 282075612

2013F2 - Game in Tree (Hard Version)

Full text and comments »

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

By aryanc403, 3 months ago, In English

I'm currently live discussing the problems. I will add problemwise timestamp after the discussion stream. You can join in if something in this blog is unclear or there are more questions.

2014A - Robin Helps

Idea

My submission — 282225317

Video Editorial

2014B - Robin Hood and the Major Oak

Hint 1
Hint 2
Hint 3

My submission — 282233711

Video Editorial

2014C - Robin Hood in Town

Hint 1
Hint 2
Hint 3
Hint 4

My submission — 282243282

Video Editorial

2014D - Robert Hood and Mrs Hood

Hint 1

My submission — 282252869

Video Editorial

2014E - Rendez-vous de Marian et Robin

Hint 1
Hint 1
Hint 3
Hint 3

My submission — 282288329

Video Editorial

2014F - Sheriff's Defense

Hint 2

My submission — 282298489

Video Editorial

2014G - Milky Days

Hint 1
Hint 2
Hint 3
Hint 4
Hint 5

My submission — 282316286

Video Editorial

2014H - Robin Hood Archery

Hint 1
Hint 2
Hint 3
Hint 4
Hint 5
Hint 6
Hint 7

My submission — 282302515

Video Editorial
Chat QnA

Full text and comments »

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

By aryanc403, 3 months ago, In English

Checkout Codeforces Month of Blog Posts Pt. II (Win $500+!)

Full video

2005A - Simple Palindrome

Hint 1
Hint 2
Hint 3
Hint 4
Hint 5

My submission — 281138271

Video Editorial

2005B1 - The Strict Teacher (Easy Version)

Hint

My submission — 281147180

Video Editorial

2005B2 - The Strict Teacher (Hard Version)

Hint 1
Hint 2

My submission — 281146462

Video Editorial

2005C - Lazy Narek

Hint 1
Hint 2
Hint 3
Hint 4

My submission — 281162411

Video Editorial

2005D - Alter the GCD

My solution has a bad time complexity. Anyways you can check what I did and what the reasoning was.

My submission — 281180437

TLE solution

2005E1 - Subtangle Game (Easy Version)

Hint 2
Hint 3
Hint 3

My submission — 281195816

Video Editorial

2005E2 - Subtangle Game (Hard Version)

Hint 1
Hint 2
Hint 3
Hint 4

My submission — 281209324

Video Editorial
Chat QnA

Full text and comments »

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

By aryanc403, 3 months ago, In English

I'm currently live discussing the problems. I will add problemwise timestamp after the discussion stream. You can join in if something in this blog is unclear or there are more questions.

2008A - Sakurako's Exam

Idea

My submission — 279068120

Video Editorial

2008B - Square or Not

Hint 1
Hint 2
Hint 3

My submission — 279071329

Video Editorial

2008C - Longest Good Array

Hint 1
Hint 2
Hint 3

My submission — 279077055

Video Editorial

2008D - Sakurako's Hobby

Hint 2

My submission — 279082914

Video Editorial

2008E - Alternating String

Hint 1
Hint 2
Hint 3
Hint 4

My submission — 279127640

Video Editorial

2008F - Sakurako's Box

Hint 1
Hint 2
Hint 3

My submission — 279089762

Video Editorial

2008G - Sakurako's Task

Hint 1
Hint 2
Hint 3
Hint 4
Hint 6
Hint 7
Hint 8
Pitfall

My submission — 279141273

Video Editorial

2008H - Sakurako's Test

Hint 1
Hint 2
Hint 3
Hint 4

My submission — 279103861

Video Editorial
Chat QnA

Full text and comments »

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

By aryanc403, 4 months ago, In English

Full video

2003A - Turtle and Good Strings

Hint 1

My submission — 278058173

Video Editorial

2003B - Turtle and Piggy Are Playing a Game 2

Hint 1

My submission — 278054761

Video Editorial

2003C - Turtle and Good Pairs

Hint 1
Hint 2
Hint 3

My submission — 278156003

Video Editorial

2003D1 - Turtle and a MEX Problem (Easy Version)

Hint 1
Hint 2
Hint 3
Hint 4

My submission — 278155964

Video Editorial

2003D2 - Turtle and a MEX Problem (Hard Version)

Hint 1
Hint 2

My submission — 278157539

Video Editorial

2003E1 - Turtle and Inversions (Easy Version)

Hint 1
Hint 2
Hint 3
Hint 4
Hint 5
Hint 6

My submission — 278160207

Video Editorial

2003E2 - Turtle and Inversions (Hard Version)

Hint 1
Hint 2
Hint 3

My submission — 278161293

Video Editorial
Chat QnA

Full text and comments »

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

By aryanc403, 4 months ago, In English

Full video

2001A - Make All Equal

Hint 1
Hint 2
Hint 3
Hint 4

My submission — 277424035

Video Editorial

2001B - Generate Permutation

Hint 1
Hint 2
Hint 3
Hint 4

My submission — 277339480

Video Editorial

2001C - Guess The Tree

Hint 1
Hint 2
Hint 3
Hint 4
Hint 5

My submission — 277423597

Video Editorial

2001D - Longest Max Min Subsequence

Hint 1
Hint 2
Hint 3
Hint 4

My submission — 277427421

Video Editorial

2001E1 - Deterministic Heap (Easy Version)

Idea

My submission — 277431412

Video Editorial
Chat QnA

Full text and comments »

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

By aryanc403, 4 months ago, In English

Full Video on youtube

2004A - Closest Point

Idea

My submission — 276684814

Video Editorial

2004B - Game with Doors

Idea

My submission — 276687609

Video Editorial

2004C - Splitting Items

Hint 1
Hint 2
Hint 3
Hint 4

My submission — 276689378

Video Editorial

2004D - Colored Portals

Hint 1
Hint 2

My submission — 276697311

Video Editorial

2004E - Not a Nim Problem

Hint 1

My submission — 276702173

Exercise find out the bug in 276586233. I'm not sure if its hackable or not.

Video Editorial

2004F - Make a Palindrome

Hint 1
Hint 2
Hint 3
Hint 4
Hint 4
Following solutions will be hacked

My submission — 276706737

Video Editorial

Full text and comments »

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

By aryanc403, 4 months ago, In English

I'm currently live discussion the problems.
I will add problemwise timestamp after the discussion stream.
You can join in if something in this blog is unclear or there are more questions.

2000A - Primary Task

Idea

My submission — 276111053

2000B - Seating in a Bus

Idea

My submission — 276114559

2000C - Numeric String Template

Hint 0
Hint 1
Hint 2

My submission — 276126482

2000D - Right Left Wrong

Hint 3

My submission — 276137058

2000E - Photoshoot for Gorillas

Hint 1
Hint 2

My submission — 276261729

2000F - Color Rows and Columns

Hint 1
Hint 2

2000G - Call During the Journey

Hint 2
Hint 3

My submission — 276211659

2000H - Ksyusha and the Loaded Set

Hint 1
Hint 2
Hint 2

My submission — 276196913

Full text and comments »

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

By aryanc403, 4 months ago, In English

1998A - Find K Distinct Points with Fixed Center

Idea

My submission — 275541733

Video editorial

1998B - Minimize Equal Sum Subarrays

Hint 1
Hint 2
Hint 3

My submission — 275547485

Video editorial

1998C - Perform Operations to Maximize Score

My solution is a bit overkill, check out neal submission 275613185

Hint 1
Hint 2

My submission — 275635373

Video editorial

1998E1 - Eliminating Balls With Merging (Easy Version)

Hint 1
Hint 2
Hint 3
Hint 4

My submission — 275608667

Video editorial

1998E2 - Eliminating Balls With Merging (Hard Version)

Hint 1
Hint 2
Hint 3
Hint 4

My submission — 275619707

Video editorial

Full text and comments »

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

By aryanc403, 4 months ago, In English

1999A - A+B Again?

Idea

My submission — 274717610

Video editorial

1999B - Card Game

Idea

My submission — 274958241

Video editorial

1999C - Showering

Idea

My submission — 274959892

Video editorial

1999D - Slavic's Exam

Hint 1
Hint 2

My submission — 274963318

Video editorial

1999E - Triple Operations

Hint 1
Hint 2
Hint 3
Hint 4
Hint 5
Hint 6

My submission — 274967855

Video editorial

1999F - Expected Median

Hint

My submission — 274970725

Video editorial

1999G1 - Ruler (easy version)

Hint 1
Hint 3
Hint 4
Hint 5

My submission — 274972155

Video editorial

1999G2 - Ruler (hard version)

Hint 1
Hint 2
Hint 3
Hint 4

My submission — 274973808

Video editorial
Chat QnA

Full text and comments »

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

By aryanc403, 4 months ago, In English

1993A - Question Marks

Video editorial

1993B - Parity and Sum

Hint 1
Hint 2
Hint 3
Video editorial

1993C - Light Switches

Hint 1
Hint 2
Video editorial

1993D - Med-imize

Hint 1
Hint 3
Hint 4
Hint 5
Video editorial

1993E - Xor-Grid Problem

Hint 1
Hint 2
Hint 3
Hint 4
Video editorial

1993F1 - Dyn-scripted Robot (Easy Version)

Hint 1
Hint 2
Video editorial

Full text and comments »

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

By aryanc403, 4 months ago, In English

1997A - Strong Password

Hint
Video editorial

1997B - Make Three Regions

Idea
Video editorial

1997C - Even Positions

Hint
Discussion

1997D - Maximize the Root

Video editorial

1997E - Level Up

Hint 1
Hint 2
Hint 3
Hint 4
Video editorial
Daily Chat QnA

Full text and comments »

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

By aryanc403, 4 months ago, In English

1991A - Максимизируйте оставшийся элемент

Video editorial

1991B - Восстановление И

Idea
Video editorial

1991C - Абсолютный ноль

Hint
Video editorial

1991D - Простая XOR раскраска

Hint 1
Hint 2
Video editorial
Bonus: How to write checker for D?

1991E - Игра с раскрасками

Hint 1
Hint 2
Hint 3
Hint 4
Hint 5
Video editorial

1991F - Образуйте треугольники

Hint
Video editorial
Daily Chat QnA

Full text and comments »

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

By aryanc403, 5 months ago, In English

1996A - Legs

Hint
Video editorial

1996B - Scale

Idea
Video editorial

1996C - Sort

Video editorial

1996D - Fun

Hint 1
Video editorial

1996E - Decode

Hint 1
Hint 2
Video editorial

1996F - Bomb

Hint 1
Hint 3
Video editorial

1996G - Penacony

Hint 1
Hint 2
Video editorial
Daily Chat QnA

Full text and comments »

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

By aryanc403, 5 months ago, In English

A follow-up on Topcoder and Competitive Programming.
TCO 2023 will be the last TCO?
(Virtual) TopCoder Open 2023 Finals cancelled as well.

I found the following announcement on topcoder discord.

Full text and comments »

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

By aryanc403, 8 months ago, In English

Hello everyone! I'm happy to announce the 27th stage of the 2nd Universal Cup. It will be held from April 6 to April 7. You can choose between one of seven possible time windows.

The problems were originally used in the ICPC Contests prepared by our team. Namely (ICPC India Online Round, Kanpur Regional, Chennai Regional, Amritapuri Regional, and Asia West Continent Final). If you participated, please refrain from participating in this stage of the Universal Cup.
We are planning to organise one more stage using the remaining contest problems.

Setters and Testers: kevinsogo Shisuko jtnydv25 IceKnight1093 aryanc403 Dragonado xennygrimmato ritul_kr_singh kshitij_sodani PraveenDhinwa Vichitr mexomerf JaySharma1048576 T1duS magga rivalq

We would like to give a special thanks to the CodeDrills teams (deepa_panwar Balajiganapathi Vichitr) for developing & sharing the contest with us. Thank you!

About Universal Cup

You will be able to participate in the UCup contest in the following time windows:

Time windows

Full text and comments »

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

By aryanc403, history, 10 months ago, In English

Hi Codeforces,

ICPC Amritapuri 2023 Regionals Round will happen this Sunday on CodeDrills.

Live commentary: We will be live on ICPCLive channel. We will start once the contest starts.

P.S. — All of the problems will be non-interactive, please read the guide of interactive problems before the contest.
P.P.S. — Some problems may have subtasks, so choose problem-solving order wisely.

Upd: We are live now. Sorry for the initial hiccups.
Upd 2: Closing ceremony and solution discussion stream — https://youtu.be/txbyFVl5kBg

Full text and comments »

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

By aryanc403, 11 months ago, In English

Hello everyone,

Upd: Livestream has been scheduled. Time in your timezone. You can tune in here. Upd2: We recorded it with live audience today. Audio was lagging at some places. I will edit it by next week and upload it.

I wanted to share some exciting news with you. Recently, I launched my YouTube channel and created a community Discord server. Up until now, I've mainly focused on hosting post-contest discussion streams on my channel. However, I have plans to diversify the content.

To kick things off, I'm thrilled to announce that I've invited my arch-rival, and my best friend, TheOneYouWant, to join me for an Ask Me Anything (AMA) session on my channel. We are planning to record this AMA sometime next month.

Shubham (aka TheOneYouWant) is one of my best friends I've met through CP. He started CP after taking a programming class at IITB, and soon became obsessed — he ended up qualifying for WF thrice! After graduating from IITB, he went to grad school at Stanford, and now works as a software developer at a quant firm in New York. He's enjoyed teaching through his years; he used to teach for math olympiads through undergrad, and was head TA for algorithms in grad school. In his free time, Shubham likes to read manga, play badminton, and write blogs. Often, he's thinking about the next random thing to get obsessed with...

Feel free to ask anything you're curious about, although he can't guarantee he'll answer every question. If you're interested in following TheOneYouWant on his journey/reading more about his thoughts, consider following him on Twitter here and his blog here.

Full text and comments »

Tags ama
  • Vote: I like it
  • +67
  • Vote: I do not like it

By aryanc403, history, 12 months ago, In English

Hi Codeforces,

ICPC Kanpur 2023 Regionals Round will happen this Saturday on CodeDrills.

Live commentary: We will be live on codedrills youtube channel. We will start once the contest starts.

P.S. — All of the problems will be non-interactive, please read the guide of interactive problems before the contest.
P.P.S. — Some problems may have subtasks, so choose problem-solving order wisely.

Full text and comments »

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

By aryanc403, history, 17 months ago, In English
#pragma GCC target ("sse4")
#include <bits/stdc++.h>

int main(void) {
    std::set<int> s;
    return 0;
}

It fails to compile with error
In file included from /usr/include/c++/13.1.1/string:43, from /usr/include/c++/13.1.1/bitset:52, from /usr/include/c++/13.1.1/x86_64-pc-linux-gnu/bits/stdc++.h:52, from a.cpp:2: /usr/include/c++/13.1.1/bits/allocator.h: In destructor ‘std::_Rb_tree<int, int, std::_Identity<int>, std::less<int>, std::allocator<int> >::_Rb_tree_impl<std::less<int>, true>::~_Rb_tree_impl()’: /usr/include/c++/13.1.1/bits/allocator.h:184:7: error: inlining failed in call to ‘always_inline’ ‘std::allocator< <template-parameter-1-1> >::~allocator() noexcept [with _Tp = std::_Rb_tree_node<int>]’: target specific option mismatch 184 | ~allocator() _GLIBCXX_NOTHROW { } | ^ In file included from /usr/include/c++/13.1.1/map:62, from /usr/include/c++/13.1.1/x86_64-pc-linux-gnu/bits/stdc++.h:152: /usr/include/c++/13.1.1/bits/stl_tree.h:662:16: note: called from here 662 | struct _Rb_tree_impl

Compilation command — time g++ -static -DONLINE_JUDGE -O2 -std=c++20 $$${file} -o $$${file}.exe

G++/GCC version g++ (GCC) 13.1.1 20230429 Copyright (C) 2023 Free Software Foundation, Inc. This is free software; see the source for copying conditions. There is NO warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

When, where and how to report it?

Update: GCC Bugzilla

Full text and comments »

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

By aryanc403, history, 19 months ago, In English

Hi Codeforces,

ICPC Asia West Continent Final Contest 2022 will happen ~10 hrs from now on CodeDrills.

Live commentary: We will be live on codedrills youtube channel. We will start once contest starts.

Contest Details

P.S. — All of the problems will be non-interactive, please read the guide of interactive problems before the contest.
P.P.S. — Some problems may have subtasks, so choose problem-solving order wisely.

Update: Live ranklist
We plan to start live commentary 1 hr into the contest. Commentry URL

Update 2 — Credits
Chief Judge: Jatin jtnydv25 Yadav
Setters: Jatin jtnydv25 Yadav, Nishank IceKnight1093 Suresh, Jeroen Op de jeroenodb Beek, Vsevolod sevlll777 Lepeshov, Arul flamestorm Kolla
Testers (excluding setters): Aryan aryanc403 Choudhary, Chaithanya Dragonado Shyam, Vaibhav xennygrimmato Tulsyan, Ritul Kumar ritul_kr_singh Singh, Kshitij kshitij_sodani Sodani, Praveen PraveenDhinwa Dhinwa, Siddhartha gravito12345 Srivastava, Konstantin miagkov Miagkov
Codedrills platform: Deepa deepa_panwar Panwar, Balajiganapathi Balajiganapathi S, Swati Panwar, Vichitr Vichitr Gandas
Rcd: Prof. Phalguni Gupta

Results
Final ranklist
1. facelessmen3.0 (IIT Kanpur) — satyam343 udhavvarma03 avi0000
2. Ab_Ki_Baar (IIT Kharagpur) — professor_flux harsh639 RahulChugh
3. Yorozuya Forever (IIT Madras) — Teja-Smart blitztage Nisanth

We will try to hold one universal cup stage based on Amritapuri (Regionals+Online), and Asia West Finals problems.

Full text and comments »

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

By aryanc403, history, 20 months ago, In English

Hi Codeforces,

ICPC Amritapuri 2022 Regionals Round is happening right now on Codedrills.

Live ranklist: https://icpc.codedrills.io/contests/icpc-amritapuri-2022-regional-round/scoreboard

Live commentary: We will be live on codedrills youtube channel. We will be starting soon.
Update: We are live now.

Contest Details
- Contest Link — ICPC Amritapuri 2022 Regionals Round
- Date & Time — 2 April 2023, Sunday, 9:00 IST
- Duration — 5 Hours
- There will be 12 problems to solve
- Will follow standard ICPC scoring system (20 minutes penalty and 1 point per problem)
- The questions may not be sorted by difficulty
- Contest link — https://icpc.codedrills.io/contests/icpc-amritapuri-2022-regional-round

Edit — Credits
Chief Judge: Jatin jtnydv25 Yadav
Setters: Janmansh janmansh Agarwal, Aryan aryanc403 Choudhary, Jatin jtnydv25 Yadav, Chaithanya Dragonado Shyam, Vaibhav xennygrimmato Tulsyan, Mukesh Kumar, Jatin rivalq Garg, Vaibhav gvaibhav21 Gosain, Harris gamegame Leung
Testers (excluding setters): Aswin aswinashok44 Ashok, Mayank katana_handler Pugalia, Nishank IceKnight1093 Suresh, Ritul Kumar ritul_kr_singh Singh, Kshitij kshitij_sodani Sodani, Abhay Pratap abhayps Singh, Mohan Raghu mohanraghug Garimella, Ankur ankurkayal Kayal, Praveen PraveenDhinwa Dhinwa, Sai sinus_070 Avinash, Siddhartha gravito12345 Srivastava, Osama ......-......... Saleh, Anil marksman_ Kumar, Masood Alam
Platform Coordinators: Deepa deepa_panwar Panwar, Balajiganapathi Balajiganapathi S, Swati Panwar, Vichitr Vichitr Gandas
RCD: Maheshwara anandoham Chaitanya

Edit 2: Results
1. Paradigm Shift (IIT Indore) — codebuster_10 s_jaskaran_s nishkarsh
2. AuditPass (IIT Delhi) — tamajitbuba islingr magga
3. :(){ :|:& };: (BITS Pilani, Hyderabad Campus) — ExplodingFreeze JeevanJyot the_hyp0cr1t3
4. Maanzar (IIT Patna) — 100gods AwakeAnay TimeWarp101

Full text and comments »

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

By aryanc403, 21 month(s) ago, In English

Hi everyone,

We are looking for problem-setters to join the ICPC Asia West Finals 2022-23 panel and contribute interesting tasks. If you or anyone you know is interested, please fill this form. You are also welcome to join the team to help in testing, task preparation etc.

Eligibility:

  • For Indians, you should have graduated in 2021 or before. School students, no longer eligible for ICPC (due to age limit, exhaust WFs/regionals attempts etc) and ICPC WF Egypt I qualified participants (if they are not participating again) can also contribute problems.
  • Preferably, should have a track record of participation in similar contests or good profiles on online competition platforms like Codeforces, AtCoder, CodeChef, etc.
  • For non-Indians, anyone not participating in Indian, Asia West Regionals.

Compensation

Problem setters would be paid with the following per-problem rates (difficulty determined by the contest admin)

  • Cakewalk: 1500 INR
  • Simple: 2250 INR
  • Easy: 3750 INR
  • Easy-Medium: 6000 INR
  • Medium: 9500 INR
  • Medium-Hard: 13000 INR
  • Hard: 19000 INR

For preparation, setting amount is split half-half between author and preparer.

Update: I removed tester compensation because I'm unsure how it will be distributed among multiple testers.
Update2: The judge does not have support for interactive problems, so we won't be able to accept those proposals either.

Full text and comments »

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

By aryanc403, 3 years ago, In English

Update 2 — Thanks adamant for his Subset convolution interpretation blog. It does simplifies a lot of things.

Update 1 -
Let's consider this problem -
We have a function subset_convolution(A,B) it gives us Subset Sum Convolution of two sets $$$A, B$$$.
Let's say we array $$$A$$$ with $$$A[0]=1$$$ and we want to find A^K defined as $$$A$$$ convoluted with itself $$$K$$$ times.
A^2 = subset_convolution(A,A)
A^3 = subset_convolution(A^2,A)
...
A^k = subset_convolution(A^{k-1},A)
The best I can think right now is using something on lines of fast exponential to achieve $$$O(log K*N^2*2^N)$$$ time where $$$2^N$$$ is the size of A. Also, there exist some solutions $$$O(N^3*2^N)$$$ using the fact that the majority of the multiplications will be with A[0] and permutations & combinations.
But it can be done in $$$O(N^2*2^N)$$$ using tricks well known at some places. Idk why it works tho.

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

TLDR — Just me rambling about the old ARC problem I was solving for the last 3 days. Something "set power series" similar to "power series for polynomials" I came across and I have an iota idea about it right now. Also amplifying some unanswered bugaboo related to it in the discussion of that ARC round. Spoiler is just very very briefly mention different solutions I had for ARC105F problem.

Me trying to solve ARC105 F

The logarithm of 'set power series' is a function $$$g(x)=\sum_{S} g_{S} x^{S}$$$ such that $$$f(x) = \sum_{S} (\sum_{\mathcal{P}} \prod_{P_i \in \mathcal{P}} g_{P_i}) x^{S}$$$, where the inner summation goes over all unordered partitions $$$P$$$ of $$$S$$$.

dario2994 submission on the same problem implements a small library for subsets with functions namely and/or/xor/subset convolutions along with log and exp of set power series.
(First to answer dario2994 comment — Yes, there does exist a clever way (and maroonrk's submission) to compute subset convolution.)

I did asked some of my friends and seniors doing MATH major — where can I read formal definitions of "set power series" since googling it just gave me useless results and none of them ever heard it.

Q1 — What exactly is the definition of exp of set power series? (One implemented by dario2994 and mentioned by mmaxio). Where can I read about more similar definitions?

mmaxio mentions Lu Kaifeng's report, googling about his report along with keywords such as "set power series" doesn't yield helpful results. But then I came across this blog. It has a code snippet and mentions For details, please refer to the 2015 Proceedings of the National Training Team Lu Kaifeng, "The Properties and Application of Set Power Series and Its Fast Algorithm".

It's a 17 page report published in 2015 in Chinese, I wasn't able to find an English version. Hence must be a well-known problem in China and hence a "trivial solution" by Elegia. I tried auto translating it using the method mentioned by z4120 in Auto-translated Chinese national IOI training team report papers but I messed up a step somewhere and ended up with just Chinese translated into Chinese, would really appreciate it if someone can translate it for me.

Q2 — mmaxio's comment looks like you can apply any function to the set power series by applying it to a "ranked" vector for each mask independently makes me much more interested in this. It opens the door to a hell of a lot of possibilities here (a reason for this blog here) integration, derivative, inverse, square root to name some among similar operations on polynomials and series.

I do remember the day when I learnt about the inverse and square root of a polynomial and was overwhelmed by it. On that day, I just concluded that "polynomials are just numbers". Later I have seen some problems which even used dp states as polynomials instead of integers. The observation "polynomials are just numbers" makes it easy for me to understand those editorials and those problems do excite me these days. Something similar for sets will for sure generalize it further.

Publishing this blog with the expectation that I would find more material to read about it since Google isn't my friend here.

Update 1 (solution) —

O(N^2*2^N) solution of initial problem

Full text and comments »

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